How can I get this robot to finish the maze?

Solution 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));

Solution 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.

Solution 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.