# Creating a modular game in JavaScript, part 2: Implementing Pathfinding

Last week I wrote about writing a pathfinding algorithm in javascript, so now we’ll be implementing it into our game. See part 1 of this series here.

Since we’re using pathfinding now, the collision code is only going to get in the way, so we’ll get rid of the collision call in the draw function of the skeleton object:

`draw() { //   Wall.all.forEach(b => { //   collide(this, b); //   }) //   Skeleton.all.forEach(s => { //     collide(this,s); //   })    this.animate();    this.changeMoving();    this.drawFrame(); }`

The skeleton needs to be initialized with a few more attributes now since we need to know the goal target and the path target. The skeleton will be walking along a path to reach the mouse, so it needs to walk towards the next step of the path.

`this.pathXD = 0;this.pathYD = 0;this.pathAngle = 0;this.pathVector = 1;//path targetthis.pathTarget = [0,0];`

In updateVectors we’ll add calculations for the path vector

`updateVectors() {   //base movement off of offset character coordinates to center of      feet of character   this.xD = this.target[0] - (this.centerX);   this.yD = this.target[1] - (this.centerY);   //get the angle of the mouse relative to the character   this.angle = Math.atan2(this.yD, this.xD)*180/Math.PI;   this.vector = Math.hypot(this.xD,this.yD);   //base movement off of offset character coordinates to center of   feet of character   this.pathXD = this.pathTarget[0] - (this.centerX);   this.pathYD = this.pathTarget[1] - (this.centerY);   //get the angle of the mouse relative to the character   this.pathAngle = Math.atan2(this.pathYD,this.pathXD)*180/Math.PI;   this.pathVector = Math.hypot(this.pathXD,this.pathYD);}`

For an A* algorithm, for each node that it checks for a path you need a gCost which is the cost of the path so far, and an hCost, which is the estimated remaining path (ignoring walls).

`//Calc path distancecalcGCost(node) {    let curr = node;    let cost = 0;    while(curr.parent) {        let step = Math.floor(this.euclid(curr,curr.parent)*this.decPlace)/this.decPlace;        cost += step;        curr = curr.parent;       }    cost = Math.floor(cost*this.decPlace)/this.decPlace;    return cost;}//Calc heuristic distance (octile distance)calcHCost(currNode, endNode) {    let a = Math.abs(currNode.x - endNode.x);    let b = Math.abs(currNode.y - endNode.y);    function leastSide() {        if (a > b) {return b;} else {return a;}    }    let diagonalCost = leastSide()*Math.sqrt(2);    let horizontalCost = Math.abs(b-a);    let sum = diagonalCost+horizontalCost;    return Math.floor(sum*this.decPlace)/this.decPlace;}//Euclidean Distanceeuclid(node1, node2) {    let distance = Math.hypot(node1.x - node2.x,node1.y - node2.y);    return Math.floor(distance*this.decPlace)/this.decPlace;}`

decPlace is just a variable for keeping precision in rounding consistent. To see which node should be priority for checking for a new path, we add the g and h costs. This is called the fCost.

`//Calc fCostcalcFCost(g, h) {    return Math.floor((g + h)*this.decPlace)/this.decPlace;}//Rank by fCost, then hCost if equal.compareFCost(obj1,obj2) {    if (obj1.fCost === obj2.fCost) {        if (obj1.hCost > obj2.hCost) {            return 1;        } else {            return -1;        }    } else if (obj1.fCost > obj2.fCost) {        return 1;    } else if (obj1.fCost < obj2.fCost) {        return -1;    }    return 0;}`

Each skeleton needs to make changes to its own grid so unfortunately we have to make the grid inside the skeleton object or else they would interfere with other skeletons’ paths.

`makeGrid() {    //Make the 2D array to hold all objects    let self = this;    let grid = [];    for (let i=0; i<offScreenCVS.height; i++) {        grid[i] = [];        for (let j=0; j<offScreenCVS.width; j++) {            let checkWalls = w => w.gridX===j&&w.gridY===i;            let others = Skeleton.all.filter(s => s != self);            if (Wall.all.some(checkWalls)) {                grid[i][j] = {parent: null, type: "wall", x: j, y: i, gCost: 0, hCost: 0, fCost: 0}            } else if (others.some(checkWalls)) {                grid[i][j] = {parent: null, type: "wall", x: j, y: i, gCost: 0, hCost: 0, fCost: 0}            } else {                grid[i][j] = {parent: null, type: "free", x: j, y: i, gCost: 0, hCost: 0, fCost: 0}            }        }    }    return grid;}`

Finally, the findPath function. First we’ll initialize a few key values we need to run the algorithm:

`findPath() {    let self = this;    let gameGrid = self.makeGrid();    //Start    let start = gameGrid[self.gridY][self.gridX];    start.type = "start";        //Goal    let goalX = Math.floor(self.target[0]/32);    let goalY = Math.floor(self.target[1]/32);        //Account for edge of canvas    if (goalY<0) {goalY = 0};    if (goalY>9) {goalY = 9};    if (goalX<0) {goalX = 0};    if (goalX>15) {goalX = 15};    let goal = gameGrid[goalY][goalX];    if (goal.type === "wall") {        self.moving = false;        return [goal];    }    //Priority queue    let open = new Set();    open.add(start);    start.gCost = 0;    start.hCost = self.calcHCost(start, goal);    start.fCost = self.calcFCost(start.gCost, start.hCost);    //Set empty closed set    let closed = new Set();    let current = start;`

While the open set isn’t empty, first remove the current node from the open set and add it to closed. Check if the current node is the end node and if it is, return the path by pushing each node’s parent into an array in order. If it isn’t, get the neighboring nodes:

`    while (open.size>0) {            //Remove current from open and add it to closed            open.delete(current);            closed.add(current);            //End case            if (current === goal) {                let curr = current;                let tempPath = [];                while(curr.parent) {                    tempPath.push(curr);                    curr = curr.parent;                }                // tempPath.push(curr);                let truePath = tempPath.reverse();                return truePath;            }            //Eight neighbors            let neighbors = [];            let east,west,south,north,northeast,northwest,southeast,southwest;            if (gameGrid[current.y][current.x+1]) {                //east                east = gameGrid[current.y][current.x+1];                neighbors.push(east);            }            if (gameGrid[current.y][current.x-1]) {                //west                west = gameGrid[current.y][current.x-1];                neighbors.push(west);            }            if (gameGrid[current.y+1]) {                //south                south = gameGrid[current.y+1][current.x];                neighbors.push(south);                if (gameGrid[current.y+1][current.x-1]) {                    //southwest                    southwest = gameGrid[current.y+1][current.x-1];                    neighbors.push(southwest);                }                if (gameGrid[current.y+1][current.x+1]) {                    //southeast                    southeast = gameGrid[current.y+1][current.x+1];                    neighbors.push(southeast);                }            }            if (gameGrid[current.y-1]) {                //north                north = gameGrid[current.y-1][current.x];                neighbors.push(north);                if (gameGrid[current.y-1][current.x-1]) {                    //northwest                    northwest = gameGrid[current.y-1][current.x-1];                    neighbors.push(northwest);                }                if (gameGrid[current.y-1][current.x+1]) {                    //northeast                    northeast = gameGrid[current.y-1][current.x+1];                    neighbors.push(northeast);                }            }`

Iterate through the neighbors and check if they should be added to open. If it’s a wall, closed or around a corner, don’t add it. If it’s a valid node, add it to open and calculate it’s costs:

`for (let i=0; i<neighbors.length; i++) {    let neighbor = neighbors[i];    if (neighbor.type === "wall" || closed.has(neighbor)) {        continue;    }    //Check corners    if (neighbor === northeast) {        if ((north.type === "wall")&&(east.type === "wall")) {             continue;        }        if (self.cornerBuffer) {            if ((east.type === "wall")) {                continue;            }            if ((north.type === "wall")) {                continue;            }        }                        }    if (neighbor === northwest) {        if ((north.type === "wall")&&(west.type === "wall")) {            continue;        }        if (self.cornerBuffer) {            if ((west.type === "wall")) {                 continue;            }            if ((north.type === "wall")) {                 continue;            }        }    }    if (neighbor === southeast) {        if ((south.type === "wall")&&(east.type === "wall")) {            continue;        }        if (self.cornerBuffer) {            if ((east.type === "wall")) {                 continue;            }            if ((south.type === "wall")) {                 continue;            }        }    }    if (neighbor === southwest) {        if ((south.type === "wall")&&(west.type === "wall")) {            continue;        }        if (self.cornerBuffer) {            if ((west.type === "wall")) {                 continue;            }            if ((south.type === "wall")) {                 continue;            }        }    }    let tCost = self.euclid(neighbor,current);        //For new tiles        if (!(open.has(neighbor)||closed.has(neighbor))) {             if (neighbor!=start) {neighbor.parent = current;}                 open.add(neighbor);                 //Round the costs to take care of floating point errors.                 neighbor.gCost = self.calcGCost(neighbor);                 neighbor.hCost = self.calcHCost(neighbor, goal);                 neighbor.fCost = self.calcFCost(neighbor.gCost, neighbor.hCost);             } else if (open.has(neighbor)&&neighbor.gCost > current.gCost+tCost) {                 if (neighbor!=start) {neighbor.parent = current;}                 neighbor.gCost = self.calcGCost(neighbor);                 neighbor.fCost = self.calcFCost(neighbor.gCost, neighbor.hCost);             }         }`

Finish the while loop by sorting an array of remaining open nodes and making the current node the one with the lowest estimated cost. If the loop checks every node, don’t move the skeleton and only return the goal node as the path.

`    //make current lowest fCost        let arr = [...open];        arr.sort(self.compareFCost);        current = arr[0];    }    //This makes skeletons stop moving if there's something blocking the path. Behavior should be to go to nearest available tile to the site of the blockage.    self.moving = false;    return [goal];}`

Finally rewrite the draw function to get the path first:

`draw() {    let path = this.findPath();    if (path[0]) {        this.pathTarget = [path[0].x*32+16,path[0].y*32+16]    }      this.animate();    this.changeMoving();    this.drawFrame();}`