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