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) {
// We'll implement the A-Star algorithm to find the path
if (!this.path) {

    var nodesEqual = function (node1, node2) {
        return (node1.posX === node2.posX &&
                node1.posY === node2.posY);
    };

    var i = 0;

    // Create the start and end nodes
    var startNode = {
        posX: me.getX(),
        posY: me.getY(),
        direction: null,
        parent: null,
        f: 0, g: 0, h: 0
    };
    var endNode = {
        posX: map.getWidth() - 3,
        posY: 8,
        direction: null,
        parent: null,
        f: 0, g: 0, h: 0
    };

    // Create the open and closed lists
    var openList = [];
    var closedList = [];

    // Add the start node to the open list
    openList.push(startNode);

    // Loop until the open list is empty
    while (openList.length > 0) {

        // Put the node with the lowest f in the closed list
        currentNode = openList[0];
        currentIndex = 0;
        for (i = 0; i < openList.length; i++) {
            if (openList[i].f < currentNode.f) {
                currentNode = openList[i];
                currentIndex = i;
            }
        }
        openList.splice(currentIndex, 1);
        closedList.push(currentNode);
        // Color the closed nodes on the map (for fun)
        map.setSquareColor(currentNode.posX,
            currentNode.posY, '#0f0');

        // Check if we found the goal
        if (nodesEqual(currentNode, endNode)) {
            this.path = [];
            var current = currentNode;
            // We climb up the tree from the goal to the start
            while (current !== null) {
                this.path.push(current);
                current = current.parent;
            }
            // We reverse the path (start -> end)
            this.path.reverse();
            // We remove the start tile
            this.path.shift();
            // Finally, we add 3 dummy nodes to pick-up the key and exit
            this.path.push({
                posX: this.path[this.path.length - 1].posX + 1,
                posY: this.path[this.path.length - 1].posY,
                direction: 'right'
            });
            this.path.push({
                posX: this.path[this.path.length - 1].posX,
                posY: this.path[this.path.length - 1].posY + 1,
                direction: 'down'
            });
            this.path.push({
                posX: this.path[this.path.length - 1].posX,
                posY: this.path[this.path.length - 1].posY + 1,
                direction: 'down'
            });
            this.pathindex = 0;

            // Color the path on the map (for fun)
            for (i = 0; i < this.path.length; i++) {
                map.setSquareColor(this.path[i].posX, this.path[i].posY,
 '#f00');
            }

            return
        }

        // Look for the walkable adjacent squares to add to the open list
        var moves = map.getAdjacentEmptyCells(currentNode.posX,
 currentNode.posY);
        moves.forEach(function (move) {
            var newNode = {
                posX: move[0][0],
                posY: move[0][1],
                direction: move[1],
                parent: currentNode,
                f: 0, g: 0, h: 0
            };

            // Make sure the new node is not on the closed list already
            for (i = 0; i < closedList.length; i++) {
                if (nodesEqual(newNode, closedList[i])) {
                    return
                }
            }

            // Calculate the nodes' costs
            newNode.g = currentNode.g + 1;
            newNode.h = ((newNode.posX - endNode.posX) ** 2) +
              ((newNode.posY - endNode.posY) ** 2);
            newNode.f = newNode.g + newNode.h;

            // Make sure that a better version of the new node is not
            // already on the open list
            for (i = 0; i < openList.length; i++) {
                if (nodesEqual(newNode, openList[i]) &&
                  newNode.g > openList[i].g) {
                    return
                }
            }

            // Finally, add the new node to the open list
            openList.push(newNode);
            // Color the open nodes on the map (for fun)
            map.setSquareColor(newNode.posX,
                newNode.posY, '#00f');
        })
    }
} else {
    // Now we just need to play the moves
    if (this.pathindex < this.path.length) {
        me.move(this.path[this.pathindex].direction);
        this.pathindex++;
    }
}
        }
    });

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