# How can I get this robot to finish the maze?

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?

• I didn't bother having it run the maze; I just redefined `ROT.Map.DividedMaze` so `create` wouldn't do anything. No maze, no problem. – user2357112 supports Monica Apr 10 '14 at 5:09

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

var dif = diffs[dir];
return [pos + dif, pos + dif];
}
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) {

if (me.floodPath[nextPos]) return;
if (map.getObjectTypeAt(nextPos, nextPos) != 'empty') return;

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

});
});
}

console.log(me.floodPath);
}

me.move(getMove(me));
``````
• Fantastic, and shorter than @MagRoader's code. Also, I did not notice any calculation lag on the first move, so maybe that depends on the map. – Batophobia Apr 10 '14 at 14:30

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.

• This also works for the previous level – Canadian Luke Apr 8 '14 at 22:40
• @CanadianLuke It would also work on the level before that, and pretty much any Robot level. – Batophobia Apr 9 '14 at 14:03
• cool Idea, much easier than my "follow the wall"-strategy – mbx Apr 21 '14 at 12:41

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.

• This was my original plan but i got lazy :) – Batophobia Apr 10 '14 at 1:40

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 == p2 && p1 == p2; }
var curPoint = [me.getX(), me.getY()];
var targetPoint = [x, y];

var marks = {};
var pointString = function(p) { return p.toString() + ',' + p.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 + offset, p + offset];
if (map.getObjectTypeAt(movePoint, movePoint) != '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;
moveStack.shift();
if (pointsEqual(move, targetPoint))
{
return move;
}
else
{
moveStack = moveStack.concat(getUnmarkedMoves(move, move));
}
}
return null;
}

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

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.

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

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

`````` player.hasItem = function(item) { return true; } ;
``````
• Clever! But doesn't actually answer the question. – Mag Roader Apr 12 '14 at 17:39
• The game now has tamper detection on the core methods. – Qwerky May 4 '16 at 22:00

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

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

• The game now has tamper detection on the core methods. – Qwerky May 4 '16 at 22:00

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.

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!

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];
y = me.getY()+me.dir[me.g];
if(map.getObjectTypeAt(x, y)!='block')me.g=(me.g+1)%4;
else if(!me.canMove(me.dir[me.g]))me.g=(me.g+3)%4;
me.move(me.dir[me.g]);
}
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');
``````

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");
}
``````