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