How can I get this robot to finish the maze?

Question

On level 13, the Robot is set in the top left of a randomly generated maze. How can I make him get the blue key and give it to me?

Answer 1

My solution was yet another one - I created a flood-fill map on the first run mapping positions to the direction towards the exit.

This way, you only get calculation lag on the first move and all subsequent moves are fast, and the robot is guaranteed to make it without having to regenerate the maze.

function getMove(me) {
   if (me.getY() > 9) return '';
   return me.floodPath[[me.getX(), me.getY()]];
}

if (!me.floodPath) {
   me.floodPath = {};

   var rcol = map.getWidth() - 2;

   var directions = ['up', 'down', 'left', 'right'];
   var opposites = {
      up: 'down',
      down: 'up',
      left: 'right',
      right: 'left'
   };
   var diffs = {
      up: [0, -1],
      down: [0, 1],
      left: [-1, 0],
      right: [1, 0]
   };

   // Init floodPath with a path across the barrier

   me.floodPath[[rcol, 10]] = 'down';
   me.floodPath[[rcol, 9]] = 'down';
   me.floodPath[[rcol, 8]] = 'down';
   var iterEdges;
   // Init edges with the key
   var edges = [[rcol, 8]];

   function addDiff(pos, dir) {
      var dif = diffs[dir];
      return [pos[0] + dif[0], pos[1] + dif[1]];
   }
   console.log('hi');

   // This will terminate as soon as the flood-fill reaches the starting position
   while (!getMove(me)) {
      iterEdges = edges.slice(0); // edges.clone();
      edges = edges.slice(edges.length); // edges.clear();
      iterEdges.forEach(function(pos) {
         directions.forEach(function(dir) {

            var nextPos = addDiff(pos, dir);
            if (me.floodPath[nextPos]) return;
            if (map.getObjectTypeAt(nextPos[0], nextPos[1]) != 'empty') return;

            edges.push(nextPos);
            me.floodPath[nextPos] = opposites[dir];

         });
      });
   }

   console.log(me.floodPath);
}

me.move(getMove(me));

Answer 2

Rather than make a simple AI, it is much easier to have the Robot mirror your movements using the following code:

if(me.getY()>map.getPlayer().getY()-9)
    me.move('up');
else if(me.getY()<map.getPlayer().getY()-9)
    me.move('down');
else if(me.getX()>map.getPlayer().getX())
    me.move('left');
else if(me.getX()<map.getPlayer().getX())
    me.move('right');

Then move up and left until the Robot is mirroring your movements. Guide him through the maze as if you are controlling him. Once he has the key and is out, move right one, and go all the way up to collide with the R and get the key.

*

*Note your maze will likely be different, but guiding the robot is simple when his controls match yours.

Answer 3

You don't need a fancy AI to solve the problem. Just use a simple "hug the wall to your right" strategy, and you can escape any maze. It simply takes a little longer.

        var dirs = ['left', 'up', 'right', 'down'];

        if(map.rdir === undefined)
            map.rdir = 0;

        // The good old hug-the-wall-to-your-right algorithm
        var trythese = [map.rdir + 1, map.rdir, map.rdir - 1, map.rdir + 2];
        for(var i=0; i<4; i++) {
            var d = (trythese[i] + 4) % 4;
            if(me.canMove(dirs[d])) {
                me.move(dirs[d])
                map.rdir = d;
                break;
            }
        }

Note that I am storing an extra property on map (map.rdir) to do this. This is totally permissible since JavaScript allows the use of arbitrary properties on objects.

Answer 4

Disclaimer: This is most probably very far from the intended solution, but it is still one.

Take advantage of the fact that a maze is randomly generated.

Thanks to the way the maze is generated, there is a very reliable chance that by restarting the maze just a few times, in one of those mazes, the simple code

if(me.canMove('down')) me.move('down');
else me.move('right');

is enough to get the robot out of the maze.

Answer 5

I thought it would be way more fun to write a fancier AI, so I did. Here's a simple pathfinding algorithm that will complete all the robot mazes.

var getMoveToward = function(x, y)
{
  var pointsEqual = function(p1, p2) { return p1[0] == p2[0] && p1[1] == p2[1]; } 
  var curPoint = [me.getX(), me.getY()];
  var targetPoint = [x, y];

  var marks = {};
  var pointString = function(p) { return p[0].toString() + ',' + p[1].toString(); }
  var markPoint = function(p) { marks[pointString(p)] = true; }
  var isPointMarked = function(p) { return marks[pointString(p)] == true; } 
  var getUnmarkedMoves = function(d, p)
  {
    var offsetList = {
      'left' : [-1, 0],
      'right' : [1, 0],
      'up' : [0, -1],
      'down' : [0, 1]
    }
    var unmarkedMoves = []
    for (var dir in offsetList)
    {
      var offset = offsetList[dir];
      var movePoint = [p[0] + offset[0], p[1] + offset[1]];
      if (map.getObjectTypeAt(movePoint[0], movePoint[1]) != 'block'
          && !isPointMarked(movePoint))
      {
        unmarkedMoves.push([d == null ? dir : d, movePoint]);
        markPoint(movePoint);
      }
    }
    return unmarkedMoves;
  }

  markPoint(curPoint);
  var moveStack = [[null, curPoint]];
  while (moveStack.length > 0)
  {  
    var move = moveStack[0];
    moveStack.shift();    
    if (pointsEqual(move[1], targetPoint))
    {
      return move[0];
    }
    else
    {
      moveStack = moveStack.concat(getUnmarkedMoves(move[0], move[1]));
    }
  }
  return null;
}

var move = getMoveToward(map.getWidth()-2, 10);
if (move != null)
{
  me.move(move);
}

Answer 6

I'd done pretty much the same solution as nneonneo, just a little different in formatting:

// Implement the right-hand rule for maze solving.
if (me.facing === undefined)
    me.facing = 'right';

var dirs = {
    'right' : ['down', 'right', 'up', 'left'],
    'down'  : ['left', 'down', 'right', 'up'],
    'left'  : ['up', 'left', 'down', 'right'],
    'up'    : ['right', 'up', 'left', 'down']
}

var choices = dirs[me.facing];
for (var i = 0; i < 4; i++)
    if (me.canMove(choices[i])) {
        me.move(choices[i]);
        me.facing = choices[i];
}

Answer 7

Instead of running the maze, why not get rid of it entirely? I closed the defineObject call, then redefined ROT.Map.DividedMaze so create wouldn't do anything.

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

ROT.Map.DividedMaze = function() {
    this.create = function(){}
};
(function () {{
// end of user code
    }
});

Answer 8

Let's hack and don't bother the maze...

 player.hasItem = function(item) { return true; } ;

Answer 9

I used the field as a controller

if(player.atLocation(1, 24)) {
            me.move('down');
            } if(player.atLocation(1, 23)) {
            me.move('up');
            } if(player.atLocation(1,22)) {
            me.move('right');
            }

just go to the exit and the to the right. 3rd from bottom is righ, 2nd is up and lowest one is down.

Answer 10

AI? Ha!

    'behavior': function (me) {
        me.move(robodir);
}
});

var robodir = "right"

player.setPhoneCallback( function () {
    if (robodir=="right") {
        robodir="down";
    } else if (robodir=="down") {
        robodir="left";
    } else if (robodir=="left") {
        robodir="up";
    } else if (robodir=="up") {
        robodir="right";
    }
})

map.defineObject('null', {
    'behavior' : function () {

The robot's behiavor now makes it move along the direction stored in robodir every tick. Activating the phone changes that direction. Trivial!

Answer 11

You can also redefine defineObject to make the barrier passable before calling the original, then go get the key yourself.

Answer 12

simply, just have the robot find it, you can always evaluate the path first and then walk but this only walks the robot:

if(!me.g){
me.g=0;
me.dir=[['right',0,-1],['up',-1,0],['left',0,1],['down',1,0]];
}
move=function(){
x = me.getX()+me.dir[me.g][1];
y = me.getY()+me.dir[me.g][2];
if(map.getObjectTypeAt(x, y)!='block')me.g=(me.g+1)%4;
else if(!me.canMove(me.dir[me.g][0]))me.g=(me.g+3)%4;
me.move(me.dir[me.g][0]);
}
if(me.getY()<10)move();

funny thing is you can run any method even the locked ones just use this, this will probably be fixed in the future but for now it seems like they left a backdoor for everyone:

map._display.game._setPlayerCodeRunning(false);
map._display.game.map._removeItemFromMap(map.getWidth() - 2, 9,'barrier');

Answer 13

HAHAHA

'behavior': function (me) {

        player.setPhoneCallback(function() {
            color = player.getColor();
            if (color == "#0f0") {
                player.setColor("#f00");
            } else if (color == "#f00") {
                player.setColor("#00f");
            } else if (color == "#00f") {
                player.setColor("#ff0");
            } else if (color == "#ff0") {
                player.setColor("#0f0");
            }
        });

        color = player.getColor();
        if (color == "#0f0") {
            me.move("right");
        } else if (color == "#f00") {
            me.move("left");
        } else if (color == "#00f") {
            me.move("up");
        } else if (color == "#ff0") {
            me.move("down");
        }