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

Vote in HexoSearch