Pathing Algorithms. The Good, The Bad, The Ugly.
Hi, how are you? Welcome back to my blog post. I hope it is changing your life.
Let’s talk about something I had A LOT of fun with this past week. Pathing Algorithms. More specifically A* Pathing (pronounced a star). I played around with it only because I was making Pac-Man using javascript, css, and html and the ghosts were super dumb. So I made them very smart.
Pathing Algortithms
Why?
As always, the first question is why are pathing algorithms important. Pathing algorithms are almost the pinnacle of computer science. Before I start, let me say that pathing algorithms weren’t made with video games in mind but have been adapted to be used with video games. So I will take it back to before they were used in video games. They were originally made for graph traversal and finding the shortest path from one point to another. It’s more than that though, because you have to take into account obstacles.
I want you to just stop for a minute and think about this. If you have a graph with a single obstacle that you aren’t allowed to go through how would you find the shortest path? As a human you can probably look at it and just ‘eyeball’ it. As a computer though, how would you decide? Would you go a random direction and hope for the best? Find all possible paths and choose the shortest one? Now imagine there are more obstacles. How would you find the shortest path then as a computer? This is where pathing algorithms come in. So let’s dive into it.
Pathing Algorithms Examples
Before we start with the different algorithms let’s talk about why we have more than one. It is very simple. It has to do with accuracy vs. execution time. Some algorithms are costly but are extremely accurate, others are light-weight but inaccurate.
Djikstra’s Algorithm
The first algorithm I would like to talk about is Djikstra’s Algorithm. His algorithm begins with a start node and an ‘open set’ of candidate nodes. With each step, the node in the open set with lowest distance to the start is examined. Once examined the node is marked closed but all adjacent nodes that aren’t an obstacle and haven’t already been closed are marked open. This process will repeat until it reaches the target destination. Since the lowest distance nodes are examined first, the first time the destination is found, the path to it will be the shortest.
Djikstra’s Algorithm in action
A* Algorithm
The second is the algorithm I will talk more about today and show an example of, and that is A*. While it is a variant of Djikstra’s algorithm it is very different in the way it searches for the next node. A* assigns a ‘weight’ to each open node. The ‘weight’ is broken into two parts. The distance from the start node to the current node, and the distance from the current node to the destination. The approximate distance is found by the “heuristic”, and represents a minimum possible distance between that node and the end. This is a lot of jargon but basically what I’m saying is it finds the shortest path by checking the shortest path of the open nodes.
A* Algorithm in action
Pac-Man
As I said earlier me and another guy made Pac-Man with javascript. Once I got to the ghosts I made a really dumb AI where the ghost was just trying to get to the same point as Pac-Man but couldn’t get around walls unless you made Pac-Man guide the ghost around the wall. Very dumb, right?
Well this is where the A* algorithm came into play. So, each ghost has there own ‘personality’ for how they should get to the next destination wether it is Pac-Man or a random spot on the map. Here is a cool article on the different ghost behaviors.
Anyways, I was able to adapt the pseudocode for A* algorithm to be used in Pac-Man. I’m going to try and explain it here.
Here is the pseudocode from Wikipedia:
function A*(start, goal)
// The set of nodes already evaluated
closedSet := {}
// The set of currently discovered nodes that are not evaluated yet.
// Initially, only the start node is known.
openSet := {start}
// For each node, which node it can most efficiently be reached from.
// If a node can be reached from many nodes, cameFrom will eventually contain the
// most efficient previous step.
cameFrom := an empty map
// For each node, the cost of getting from the start node to that node.
gScore := map with default value of Infinity
// The cost of going from start to start is zero.
gScore[start] := 0
// For each node, the total cost of getting from the start node to the goal
// by passing by that node. That value is partly known, partly heuristic.
fScore := map with default value of Infinity
// For the first node, that value is completely heuristic.
fScore[start] := heuristic_cost_estimate(start, goal)
while openSet is not empty
current := the node in openSet having the lowest fScore[] value
if current = goal
return reconstruct_path(cameFrom, current)
openSet.Remove(current)
closedSet.Add(current)
for each neighbor of current
if neighbor in closedSet
continue // Ignore the neighbor which is already evaluated.
if neighbor not in openSet // Discover a new node
openSet.Add(neighbor)
// The distance from start to a neighbor.
// The "dist_between" function may vary as per the solution requirements.
tentative_gScore := gScore[current] + dist_between(current, neighbor)
if tentative_gScore >= gScore[neighbor]
continue // This is not a better path.
// This path is the best until now. Record it!
cameFrom[neighbor] := current
gScore[neighbor] := tentative_gScore
fScore[neighbor] := gScore[neighbor] + heuristic_cost_estimate(neighbor, goal)
return failure
function reconstruct_path(cameFrom, current)
total_path := {current}
while current in cameFrom.Keys:
current := cameFrom[current]
total_path.append(current)
return total_path
It’s a lot to parse through so I’m going to demonstrate how I used this in Pac-Man. My code will be in javascript but can be translated into other languages.
I broke the code into 4 functions for ease of use and readability; makeNode, distance, reconstructPath, and the main portion I just called aStar. Let me also go through a little bit of terminology that is used. When I talk about gScore and fScore I am talking about the cost of going from the start to this node and the cost of going from the start to this node to the destination respectively.
So inside the makeNode function I am doing just that. I am making a node that will have an x and y position, a gScore, and an fScore. The gScore and fScore are set to infinity until they are set in the astar function.
this.makeNode = function(xPos, yPos, nodeCameFrom) {
this.xPos = xPos;
this.yPos = yPos;
// For each node, the cost of getting from the start node to that node.
// gScore := map with default value of Infinity
this.gScore = Infinity;
// For each node, which node it can most efficiently be reached from.
// If a node can be reached from many nodes, cameFrom will eventually contain the
// most efficient previous step.
// cameFrom := an empty map
this.nodeCameFrom = nodeCameFrom;
this.fScore = Infinity;
}
The distance function is calculating the distance between two points for instance, the start point to the current node.
// calculate distance from the destination to the current query
this.distance = function(destX, destY, curX, curY)
{
return Math.sqrt(Math.pow((destX - curX), 2) + Math.pow((destY - curY), 2));
}
Here we are in the meat and potatoes of this algorithm. This function is thick but it is pretty simple. It intializes the closed and open sets where closed is the set of nodes that have already been checked and open is the set that has yet to have been evaluated. Then we initialize a set for the neighbors of the current node. From there we will go through a while loop that will evaluate each neighbor node and put them in open set while the current is put in the closed. We will evaluate the open set of nodes to find the lowest fScore to check the next node. Once they all have been checked we can finally reconstruct the path.
this.aStar = function(goToX, goToY) {
// The set of nodes already evaluated
// closedSet := {}
var closedSet = [];
// The set of currently discovered nodes that are not evaluated yet.
// Initially, only the start node is known.
// openSet := {start}
var openSet = [];
let firstNode = new this.makeNode(this.ghostPos[0], this.ghostPos[1], null);
firstNode.gScore = 0;
openSet.push(firstNode);
// For each node, the total cost of getting from the start node to the goal
// by passing by that node. That value is partly known, partly heuristic.
// while openSet is not empty
var lowest = firstNode.fScore;
var saveNum = 0;
var current;
var neighbors = [];
while (openSet.length != 0)
{
// current := the node in openSet having the lowest fScore[] value
var lowest = firstNode.fScore;
var saveNum = 0;
for (var i = 0; i < openSet.length; i++) {
if (openSet[i].fScore < lowest) {
lowest = openSet[i].fScore;
saveNum = i;
}
}
current = openSet[saveNum];
// if current == goal
if (openSet[saveNum].xPos == goToX && openSet[saveNum].yPos == goToY) {
return this.reconstructPath(goToX, goToY, current);
}
neighbors = [];
for (var i = -1; i < 2; i += 2) {
if (map.getTileId(openSet[saveNum].yPos + i, openSet[saveNum].xPos) == 99 ||
map.getTileId(openSet[saveNum].yPos + i, openSet[saveNum].xPos) == 10) {
neighbors.push([openSet[saveNum].xPos, openSet[saveNum].yPos + i]);
}
if (map.getTileId(openSet[saveNum].yPos, openSet[saveNum].xPos + i) == 99 ||
map.getTileId(openSet[saveNum].yPos, openSet[saveNum].xPos + i) == 10) {
neighbors.push([openSet[saveNum].xPos + i, openSet[saveNum].yPos]);
}
}
// if neighbor in closedSet
// continue, take neighbor out // Ignore the neighbor which is already evaluated.
for (var i = 0; i < closedSet.length; i++) {
for (var j = 0; j < neighbors.length; j++) {
if (neighbors[j][0] == closedSet[i].xPos && neighbors[j][1] == closedSet[i].yPos) {
neighbors.splice(j, 1);
}
}
}
// openSet.Remove(current)
closedSet.push(openSet[saveNum]);
openSet.splice(saveNum, 1);
// closedSet.Add(current)
// for each neighbor of current
for (var i = 0; i < neighbors.length; i++) {
// if neighbor not in openSet // Discover a new node
// openSet.Add(neighbor)
openSet.push(new this.makeNode(neighbors[i][0], neighbors[i][1], current));
// The distance from start to a neighbor
//the "dist_between" function may vary as per the solution requirements.
// tentative_gScore := gScore[current] + dist_between(current, neighbor)
var tentative_gScore = current.gScore + this.distance(current.xPos, current.yPos, neighbors[i][0], neighbors[i][1]);
//console.log(tentative_gScore + ', ' + openSet[openSet.length - 1].gScore)
// if tentative_gScore >= gScore[neighbor]
if (tentative_gScore < openSet[openSet.length - 1].gScore) {
// This path is the best until now. Record it!
// cameFrom[neighbor] := current
// gScore[neighbor] := tentative_gScore
// fScore[neighbor] := gScore[neighbor] + heuristic_cost_estimate(neighbor, goal)
cameFrom.push(current);
openSet[openSet.length - 1].gScore = tentative_gScore;
openSet[openSet.length - 1].fScore = tentative_gScore + this.distance(neighbors[i][0], neighbors[i][1], goToX, goToY);
}
}
}
}
This part is the most fun. It makes the path into an array and returns that array all the way back to the function that called it. It’s cool because there is some clever programming that I was able to take advantage of. Whenever I made a new node I would save the node it just came from. So once you get to the very end you just keep looking back at the previous node all the way back to the beginning and voila, you have your shortest path!
// function reconstructPath(cameFrom, current)
this.reconstructPath = function(goToX, goToY, current)
{
// totalPath := {current}
var totalPath = [current];
// while current in cameFrom.Keys:
while (current.xPos != this.ghostPos[0] || current.yPos != this.ghostPos[1])
{
totalPath.push(current.nodeCameFrom);
current = current.nodeCameFrom;
}
return totalPath
}
That is basically it for the Pac-Man version of A*! It looks like a lot but trust me, it is actually very easy and extremely clever. So let’s go through it one more time just for understanding’s sake. First you choose the node with the shortest distance from the beginning and the end, then you save the node with a map to where it came from, then you do it again until you get to your destination. Very cool.
In conclusion
Okay, so I haven’t been completely honest. I tricked you into reading this entire blog to make a point. I needed something, I researched it, and then made it. At times it was daunting because I needed to wrap my head around it but in the end it was really cool to figure and play with. What I’m trying to say is as a programmer you should never be afraid to challenge yourself and take risks with things you don’t understand. So take it from me, if there is something scary that you don’t understand but know you need, don’t be afraid to, as my father would always say, “punch the wall ‘til you break through”.
That’s all I’ve got to say this week so y’all be good now and remember, you be careful out among them English.