Maze and Pledge algorithm

Javascript ES6

2018


After reading this article witch give a detailled explaination of the Pledge algorithm ; I’ve implemented it as a test in my brand new (still in progress) JS-ES6 version of my blankTemplate.

Pledge algorithm solve this problem with the “i put my left hand on the wall and i follow it” strategy

Here an history that track the Agent movement and “turn counter” with my test map

My main screen

class Pledge extends BaseScreen
{
constructor() {
super();
}

start() {
this._nextScreen = Game;
super.start();
this.visible = true;

EventBroker.subscribe(MessageEvent.MY_CUSTOM_MESSAGE_EVENT, this.kill);

this.maze = new Maze();
this.bot = new Bot(11, 11, this.maze, Bot.PLEDGE); // start position xy, maze ref, Bot behavior

BT.stage.addChild(this.maze.container);

this.intervalID = setInterval(() => {
this.bot.move();
this.maze.draw();
}, 200 );
}

kill(me) {
clearInterval(this._currentScreen.intervalID);
BT.dc.message("E x i t !!!");
}
}

The Agent, here i have implemented 4 differents behaviors. It’s interesting to see that Pledge method is an improvement of the famous “i put my left hand on the wall and i follow it” strategy (check line 96-120 below to spot the difference)

class Bot
{
constructor(pL, pC, pMazeRef, pBehavior = Bot.RANDOM_MICE) {

this.l = pL;
this.c = pC;

this.mazeTileWidth = pMazeRef.MAZE_TILE_WIDTH;
this.maze = pMazeRef.mazeTiles;
this.EMPTY = 0;
this.EXIT = 3;

this.UP = 0;
this.RIGHT = 1;
this.DOWN = 2;
this.LEFT = 3;
this.orientation = this.UP;
this.turnCounter = 0;

this.behavior = pBehavior;
this.move = this.moveForward; // default movement behavior
this.leftHandFlag = false;
this.pledgeFlag = false;
}
move()
{}

moveForward() {
if(this.canAdvance)
{
let k = (this.mazeTileWidth * this.l) + this.c;
this.maze[k] = 0;

if(this.orientation == this.UP)
{
this.l = this.l - 1;
}
else if(this.orientation == this.RIGHT)
{
this.c = this.c + 1;
}
else if(this.orientation == this.DOWN)
{
this.l = this.l + 1;
}
else if(this.orientation == this.LEFT)
{
this.c = this.c - 1;
}

k = (this.mazeTileWidth * this.l) + this.c;

if(this.maze[k] == 3) {
let me = new MessageEvent(MessageEvent.MY_CUSTOM_MESSAGE_EVENT, this);
EventBroker.broadcast(me);
}

this.maze[k] = 2;

} else {
this.changeOrientation();
}
}

changeOrientation() {
if(this.behavior == Bot.RANDOM_MICE) {
const ran = Math.random();
if(ran < 1/3)
{
this.turnRight();
}else if(ran > 1/3 && ran < 2/3)
{
this.turnLeft();
}else{
this.turnBack();
}
} else if(this.behavior == Bot.ALWAYS_TURN_LEFT) {
this.turnLeft();
} else if(this.behavior == Bot.LEFT_HAND) {
if(this.leftHandFlag == false)
{
this.leftHandFlag = true;
this.turnRight(); // in order to put his left hand on the wall
this.move = this.followLeftWall; // replace the move method by the follow left wall logic
}
} else if(this.behavior == Bot.PLEDGE) {
if(this.leftHandFlag == false)
{
this.leftHandFlag = true;
this.turnRight(); // in order to put his left hand on the wall
this.move = this.pledge; // replace the move method by the follow left wall logic
}
}
}

pledge() {
if(this.turnCounter < 0 && this.canGoLeft) {
this.turnLeft();
}

if(this.canAdvance) {
this.moveForward();
}else{
this.leftHandFlag = false;
this.changeOrientation();
}
}

followLeftWall() {
if(this.canGoLeft) {
this.turnLeft();
}

if(this.canAdvance) {
this.moveForward();
}else{
this.leftHandFlag = false;
this.changeOrientation();
}
}

turnBack() {
switch(this.orientation)
{
case this.UP:
this.orientation = this.DOWN;
break;

case this.RIGHT:
this.orientation = this.LEFT;
break;

case this.DOWN:
this.orientation = this.UP;
break;

case this.LEFT:
this.orientation = this.RIGHT;
break;

default:
}
}

get canAdvance() {
let nextL = this.l;
let nextC = this.c;

if(this.orientation == this.UP)
{
nextL = this.l - 1;
}
else if(this.orientation == this.RIGHT)
{
nextC = this.c + 1;
}
else if(this.orientation == this.DOWN)
{
nextL = this.l + 1;
}
else if(this.orientation == this.LEFT)
{
nextC = this.c - 1;
}

let nextTile = this.maze[(this.mazeTileWidth * nextL) + nextC];
if( nextTile == this.EMPTY || nextTile == this.EXIT) {
return true;
}

return false;
}

get canGoLeft() {
if(this.orientation == this.UP)
{
// on regarde vers le haut on check la col de gauche
let k = (this.mazeTileWidth * this.l) + (this.c - 1);
return this.maze[k] == this.EMPTY || this.maze[k] == this.EXIT;
}
else if(this.orientation == this.RIGHT)
{
// on regarde vers la droite on check la ligne du haut
let k = (this.mazeTileWidth * (this.l-1)) + (this.c);
return this.maze[k] == this.EMPTY || this.maze[k] == this.EXIT;
}
else if(this.orientation == this.DOWN)
{
// on regarde vers le bas on check la col de droite
let k = (this.mazeTileWidth * (this.l)) + (this.c + 1);
return this.maze[k] == this.EMPTY || this.maze[k] == this.EXIT;
}
else if(this.orientation == this.LEFT)
{
// on regarde vers la gauche on check la col du bas
let k = (this.mazeTileWidth * (this.l+1)) + (this.c);
return this.maze[k] == this.EMPTY || this.maze[k] == this.EXIT;
}
}

turnLeft() {
this.turnCounter += 1;
if(this.orientation == this.UP) {
this.orientation = this.LEFT;
}else{
this.orientation = this.orientation - 1;
}
BT.dc.message("turnCounter : " + this.turnCounter);
}

get canGoRight() {
if(this.orientation == this.UP)
{
// on regarde vers le haut on check la col de droite
let k = (this.mazeTileWidth * this.l) + (this.c + 1);
return this.maze[k] == this.EMPTY || this.maze[k] == this.EXIT;
}
else if(this.orientation == this.RIGHT)
{
// on regarde vers la droite on check la ligne du bas
let k = (this.mazeTileWidth * (this.l+1)) + (this.c);
return this.maze[k] == this.EMPTY || this.maze[k] == this.EXIT;
}
else if(this.orientation == this.DOWN)
{
// on regarde vers le bas on check la col de droite
let k = (this.mazeTileWidth * (this.l)) + (this.c - 1);
return this.maze[k] == this.EMPTY || this.maze[k] == this.EXIT;
}
else if(this.orientation == this.LEFT)
{
// on regarde vers la gauche on check la col du bas
let k = (this.mazeTileWidth * (this.l-1)) + (this.c);
return this.maze[k] == this.EMPTY || this.maze[k] == this.EXIT;
}
}

turnRight() {
this.turnCounter -= 1;
if(this.orientation == this.LEFT) {
this.orientation = this.UP;
}else{
this.orientation = this.orientation + 1;
}
BT.dc.message("turnCounter : " + this.turnCounter);
}
}

// Behaviors
Bot.RANDOM_MICE         = "bot::randommice";
Bot.ALWAYS_TURN_LEFT    = "bot::alwaysturnleft";
Bot.LEFT_HAND           = "bot::lefthand";
Bot.PLEDGE              = "bot::pledge";

And finally the Maze, as you can see for the moment the Bot is part of the maze (2), wall are (1) and exit is (3)

class Maze
{
constructor()
{
this.tiles = [];
this.mazeContainer = null;
this.colors = [0xFFFFFF, 0x0, 0x00CC00, 0xCC00CC];

this.MAZE_TILE_SIZE     = 28; // 40
this.MAZE_TILE_WIDTH    = 24; // 10
this.MAZE_TILE_HEIGHT   = 14; // 10

this.mazeTiles = [
1,1,1,1,1,1,1,1,1,1,
1,0,0,0,0,0,0,0,0,1,
1,0,0,0,1,0,0,0,0,1,
1,0,0,1,1,1,1,0,0,1,
1,0,0,1,1,1,1,0,0,1,
1,0,0,0,0,0,0,0,0,1,
1,0,0,0,0,0,0,0,1,1,
1,0,0,0,2,0,0,0,0,1,
1,0,0,0,0,0,1,0,0,3,
1,1,1,1,1,1,1,1,1,1
];

this.mazeTiles = [
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
1,0,0,0,1,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,1,
1,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,1,
1,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,1,
1,0,0,0,1,0,0,0,0,1,0,0,0,1,0,0,0,0,1,0,0,0,0,1,
1,0,0,0,1,0,0,0,0,1,0,0,0,1,0,0,0,0,1,0,0,0,0,1,
1,0,0,0,1,0,0,0,0,1,0,0,0,1,1,1,1,1,1,0,0,0,0,1,
1,0,0,0,1,0,0,0,0,1,0,2,0,0,0,0,0,0,0,0,0,0,0,1,
1,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
1,3,3,3,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
];

let mazeContainer = this.mazeContainer = new Container();

for (let l = 0; l < this.MAZE_TILE_HEIGHT ; l++)
{
for (let c = 0; c < this.MAZE_TILE_WIDTH ; c++)
{
let tile = new Graphics();
tile.idx = ( l * this.MAZE_TILE_WIDTH ) + c;
tile.x = c * this.MAZE_TILE_SIZE;
tile.y = l * this.MAZE_TILE_SIZE;
this.tiles[tile.idx] = tile;
mazeContainer.addChild(tile);
}
}

mazeContainer.x = (Config.STAGEWIDTH - mazeContainer.width) >> 1;
mazeContainer.y = (Config.STAGEHEIGHT - mazeContainer.height) >> 1;

this.draw();
}

get container()
{
return this.mazeContainer;
}

draw()
{
let tileColor;

for (let l = 0; l < this.MAZE_TILE_HEIGHT ; l++)
{
for (let c = 0; c < this.MAZE_TILE_WIDTH ; c++)
{
let k = ( l * this.MAZE_TILE_WIDTH ) + c;
let tile = this.tiles[k];
tileColor = this.colors[this.mazeTiles[k]];
tile.beginFill(tileColor);
tile.drawRect(0, 0, this.MAZE_TILE_SIZE, this.MAZE_TILE_SIZE);
tile.endFill();
}
}
}
}