# 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 target

this.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 distance`

calcGCost(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 Distance

euclid(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 fCost`

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

}