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

untrusted-lvl12-solution.js

/*
 * robotNav.js
 *
 * The green key is located in a slightly more
 * complicated room. You'll need to get the robot
 * past these obstacles.
 */

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

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

    map.defineObject('robot', {
        'type': 'dynamic',
        'symbol': 'R',
        'color': 'gray',
        'onCollision': function (player, me) {
            me.giveItemTo(player, 'greenKey');
        },
        'behavior': function (me) {
          
          var TARGET_OBJECT_TYPE = 'greenKey'
          
          
          /**
           * A* SEARCH 
           ***********************************************************/
          function findRoute (targetObject) {
            var route
          	var cellsData = {}
            
          	function h(x, y) {
              var deltaX = Math.abs(x - targetObject.x)
                , deltaY = Math.abs(y - targetObject.y)
              return deltaX + deltaY
            }
            
            function coordToKey(x,y) { 
              return x + ':' + y 
            }
            
            function keyToCoord(key) {
              var splitKey = key.split(':')
              return { x : +splitKey[0], y : +splitKey[1] }
            }
            
            function isGoal(key) {
              var coord = keyToCoord(key);
              return coord.x == targetObject.x && coord.y == targetObject.y
            }
            
            
            function getNextCell() {
              var unvisitedCells = []
              
              for (var key in cellsData) {
              	if (!cellsData[key].visited)
                  unvisitedCells.push(cellsData[key])
              }
              
              var nextCell = unvisitedCells.sort(function (a, b) {
                return a.distance - b.distance
              })[0]
              
              return nextCell ? nextCell.key : null
            }
            
            function getCellData(cellKey) {
              return cellsData[cellKey] || null
            }
            
            function setCellData(cellKey, newData) {
              var cellData = getCellData(cellKey) || {}
              for (var key in newData) cellData[key] = newData[key]
              cellData['key'] = cellKey
              cellsData[cellKey] = cellData
            }
                        
            function getNeighbours(cellKey) {
              var cellCoords = keyToCoord(cellKey)
              var moves = [[0,-1], [1,0], [0,1], [-1,0]];
              var neighbours = []
              moves.forEach(function (move) {
                var nX = move[0] + cellCoords.x
                  , nY = move[1] + cellCoords.y
                try {
                  if (map.getObjectTypeAt(nX, nY) != 'block')
                    neighbours.push(coordToKey(nX, nY))
                }
                catch (e) {}
              })
              
              return neighbours
            }
            
            function buildCellPath(cellKey, acc) {
              if (!acc) acc = []
              
              var cellData = getCellData(cellKey)
              
              if (cellData.prevCell) {
                buildCellPath(cellData.prevCell, acc)
                acc.push(getMoveToCell(cellData.prevCell, cellKey))
               }
              
              return acc
            }
            
            function getMoveToCell(start, dest) {
              var startCoord = keyToCoord(start)
                , destCoord  = keyToCoord(dest)
              
              if (destCoord.x - startCoord.x == 1) return 'right'
              else if (destCoord.x - startCoord.x == -1) return 'left'
              else if (destCoord.y - startCoord.y == 1) return 'down'
              else if (destCoord.y - startCoord.y == -1) return 'up'
            }
            
            function checkNextCell() {
              var cell = getNextCell()
              
              if (!cell) { return false }
              
              if (isGoal(cell)) { 
                route = buildCellPath(cell)
                return false
              }
              
              setCellData(cell, { visited : true })
              
              var cellData = getCellData(cell)
              
              var neighbours = getNeighbours(cell)
              neighbours.forEach(function (nKey) {
                var nData = getCellData(nKey)
                
                if (nData && nData.visited) return
                
                var nCoord = keyToCoord(nKey)
                var nFromStart = cellData.fromStart + 1
                var tentativeToGoal = nFromStart + h(nCoord.x, nCoord.y)
                if (!nData || nData.toGoal > tentativeToGoal)
                  setCellData(nKey, { 
                      fromStart : nFromStart
                    , toGoal    : tentativeToGoal
                    , prevCell  : cell
                  })
              })
              
              return true
            }
            
            setCellData(coordToKey(me.getX(), me.getY()), {
              	visited	  : false
              , fromStart : 0
              , toGoal    : h(me.getX(), me.getY())
            })
            
            while(checkNextCell());
            
            return route
          }
          /***********************************************************/
          /***********************************************************/
          
          if (!me.keyRoute) 
             me.keyRoute = findRoute(me.findNearest(TARGET_OBJECT_TYPE))
      
          if (me.keyRoute.length) me.move(me.keyRoute.shift())
          else if (!me.playerRoute)
            me.playerRoute = findRoute({x : player.getX(), y : player.getY()})
          
          if (me.playerRoute && me.playerRoute.length)
              me.move(me.playerRoute.shift())
        }
    });

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

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

    for (var x = 0; x < map.getWidth(); x++) {
        map.placeObject(x, 0, 'block');
        if (x != map.getWidth() - 2) {
            map.placeObject(x, 9, 'block');
        }
    }

    for (var y = 1; y < 9; y++) {
        map.placeObject(0, y, 'block');
        map.placeObject(map.getWidth() - 1, y, 'block');
    }

    for (var i = 0; i < 4; i++) {
        map.placeObject(20 - i, i + 1, 'block');
        map.placeObject(35 - i, 8 - i, 'block');
    }
}

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

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