Solution to level 13 in Untrusted: http://alex.nisnevich.com/untrusted/

untrusted-lvl13-solution.js

/*
 * robotMaze.js
 *
 * The blue key is inside a labyrinth, and extracting
 * it will not be easy.
 *
 * It's a good thing that you're a AI expert, or
 * we would have to leave empty-handed.
 */

function startLevel(map) {
    // Hint: you can press R or 5 to "rest" and not move the
    // player, while the robot moves around.

    map.getRandomInt = function(min, max) {
        return Math.floor(Math.random() * (max - min + 1)) + min;
    }

    map.placePlayer(map.getWidth()-1, map.getHeight()-1);
    var player = map.getPlayer();

    map.defineObject('robot', {
        'type': 'dynamic',
        'symbol': 'R',
        'color': 'gray',
        'onCollision': function (player, me) {
            me.giveItemTo(player, 'blueKey');
        },
        'behavior': function (me) {

            if (me._path !== undefined) {
                if (me._path.length <= 0) {
                    me.move("down");
                    return;
                }
                var x = me._path.shift();
                me.move(x.d);
                return;
            }

            const move_id = (m) => (m.x + " " + m.y);
        
            const explore_around = (f, h, m) => {
                const moves = f(m.x, m.y);
                var r = [];
                for (var i = 0; i < moves.length; ++i) {
                    const neo = {
                        x: moves[i][0][0],
                        y: moves[i][0][1],
                        d: moves[i][1]
                    };
                    if (h[move_id(neo)] === true) {
                        continue;
                    }
                    r.push(neo);
                }
                return r;
            };

            const initial_move = () => {
                return [[{
                      x: me.getX(),
                    y: me.getY(),
                    d: ""
                  }]];
            };
            
            /*
             * Like getAdjacentEmptyCells() but also moves
             * on the blueKey cell so we can visit it.
             */
            const enumerate_nearby_cells = (x, y) => {     
                const doit = (r, d, x, y) => {
                    const type = map.getObjectTypeAt(x, y);
                    if (type === "blueKey" || type === "empty") {
                        r.push([
                            [x, y], d
                        ]);
                    }
                };
                var cells = [];
                doit(cells, "left", x - 1, y);
                doit(cells, "right", x + 1, y);
                doit(cells, "up", x, y - 1);
                doit(cells, "down", x, y + 1);
                return cells;                
            };
            
            const make_move = (f, h, s) => {
                if (s.length <= 0) {
                    return [];
                }
                const t = s[0];
                while (t.length > 0) {
                    const m = t[0],
                        mid = move_id(m);
                    map.setSquareColor(m.x, m.y, '#ffff');
                    h[mid] = true;
                    if (map.getObjectTypeAt(m.x, m.y) === "blueKey") {
                        /* Our search has succeeded!!! */
                        h["__done__"] = true;
                        return s;
                    }
                    e = explore_around(f, h, m);
                    if (e.length <= 0) {
                        t.shift();
                        continue;
                    }
                    s.unshift(e);
                    return s;
                }
                s.shift();
                return s;
            };  
                        
            var h = {},
                s = initial_move();
            while (s.length > 0 && h["__done__"] !== true) {
                s = make_move(enumerate_nearby_cells, h, s);
            }
            
            var path = [];
            for (i = 0; i < s.length; ++i) {
                const m = s[i][0];
                path.unshift(m);
                map.setSquareColor(m.x, m.y, 'purple');
            }
            
            me._path = path;
        }
    });

    map.defineObject('barrier', {
        'symbol': '░',
        'color': 'purple',
        'impassable': true,
        'passableFor': ['robot']
    });

    map.placeObject(0, map.getHeight() - 1, 'exit');
    map.placeObject(1, 1, 'robot');
    map.placeObject(map.getWidth() - 2, 8, 'blueKey');
    map.placeObject(map.getWidth() - 2, 9, 'barrier');

    var autoGeneratedMaze = new ROT.Map.DividedMaze(map.getWidth(), 10);
    autoGeneratedMaze.create( function (x, y, mapValue) {
        // don't write maze over robot or barrier
        if ((x == 1 && y == 1) || (x == map.getWidth() - 2 && y >= 8)) {
            return 0;
        } else if (mapValue === 1) { //0 is empty space 1 is wall
            map.placeObject(x,y, 'block');
        } else {
            map.placeObject(x,y,'empty');
        }
    });
}

function validateLevel(map) {
    map.validateExactlyXManyObjects(1, 'exit');
    map.validateExactlyXManyObjects(1, 'robot');
    map.validateAtMostXObjects(1, 'blueKey');
}

function onExit(map) {
    if (!map.getPlayer().hasItem('blueKey')) {
        map.writeStatus("We need to get that key!");
        return false;
    } else {
        return true;
    }
}