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