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.route) {
                if (me.route.length > 0) {
                    me.move(me.route.shift());
                } else {
                    me.move('down');
                }
                return;
            }

            function createNode(x, y, prnt) {
                return {
                    x: x,
                    y: y,
                    p: prnt
                };
            };
            
             var key = me.findNearest('blueKey');
            var allCells = {};
            
            function buildTree(prnt) {
                var child = null;
                var cells = map.getAdjacentEmptyCells(prnt.x, prnt.y);
                for (var i=0; i<cells.length; i++) {
                    var cell = cells[i][0];
                    var hash = '' + cell[0] + ':' + cell[1];
                    
                    if (allCells[hash]) continue;
                    allCells[hash] = 1;
                    
                    var node = createNode(cell[0], cell[1], prnt);
                    var diffX = Math.abs(node.x - key.x);
                    var diffY = Math.abs(node.y - key.y);
                    if (diffX + diffY == 1) {
                        console.info('found a key');
                        return createNode(key.x, key.y, node);
                    }
                    child = buildTree(node);
                    if (child) break;
                }
                return child;
            }
            
            me.route = [];
            var root = createNode(me.getX(), me.getY(), null);
            
            var node = buildTree(root);
            var direction;
            while (node.p) {
                if (node.p.x < node.x) direction = 'right';
                else if (node.p.x > node.x) direction = 'left';
                else if (node.p.y < node.y) direction = 'down';
                else direction = 'up';
                //console.log(node.x, node.y);
                node = node.p;
                me.route.unshift(direction);
            }
            
            console.log(me.route);
            
            
            /*
            
            // move randomly
            var moves = map.getAdjacentEmptyCells(me.getX(), me.getY());
            // getAdjacentEmptyCells gives array of ((x, y), direction) pairs
            me.move(moves[map.getRandomInt(0, moves.length - 1)][1]);
            */
            
            
            
            
            
            
            
            
    
        }
    });

    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;
    }
}