Custom A* Pathfinding (Part 1: The Algorithm)
So, I’m revamping this blog as a kind of intermediate location for my articles before I start my own site. And today, I’m going to talk about Unity, and more specifically the A* Pathfinding algorithm (pronounced “A Star”). In case you didn’t know pathfinding is a system that helps determine the “fastest” way to a target destination without running into obstacles.
So there are plenty of good pathfinding algorithms available for Unity. Including their very nice built-in NavMesh system. You could also go with the very nice Aron Granberg A* Pathfinding Project, which offers you many different ways to implement the pathfinding algorithm. But, alas, I needed a custom solution. Why? Because in the game I’m working on, Guns, Guts, & Glory, the level is more-or-less a dynamic system. And because I have NO capital. What do I mean “dynamic”? In my game not every room is open, and not every level is the same. Now with Unity’s own NavMesh system this instantly becomes a problem, because I need to treat each room as it’s own pathfinding graph, where the NavMesh system limits you to 1. Graph being a fancy word for the way-points and obstacle data. And Aron Granberg’s solution doesn’t help much either without purchasing the pro version. So to illustrate this, here’s a top down example scene:
The enemy (red) needs to get to the player (green). The player will move of course. But even more so, what do we do when a player opens a door (black)? Seems simple, but it’s actually a fairly complicated process if your using a standard implementation. To explain a bit better, the Unity NavMesh system can be very quick and offers the ability to use a mesh to define the areas, BUT only allows one single registered NavMesh. So if your level geometry is static and un-changing then this is a perfect system, but as soon as you need to connect meshes your stuck. Aron Granberg’s system will allow a grid based graph that will scan your level for you! Very neat if you have a open terrain style. He also offers a NavMesh solution that seems like it might work but I don’t really need that much, I just need to get the enemies through rooms. Plus the whole turning NavMeshes on or off poses a problem. We can’t afford a graph recalculation just because a door was opened. There is also a Point Graph, which still has the whole recalculation problems and toggling rooms. But it does have a low footprint so I like the concept. So, to sum up our requirements!
- Point style graph so the footprint is low.
- Toggle style way-points so things can be turned on/off.
- No re-scanning when something changes (if we can help it).
The Pathfinding Algorithm
Now that I’ve explained what we need, and why we need to make it. I’m going to take a moment to explain the A* Pathfinding Algorithm. It’s really known as the A* Search Algorithm. It uses whats called a best-first approach, or a greedy search. Meaning, it kind of builds the path as it goes using the best option first and continuing that way. In contrast, you could iterate through ALL possible paths and pick the best one that way, but just as it sounds, that makes it expensive. To calculate which “node” it should pick next it uses a cost (or commonly referred to as “weight”) formula. This is simply:
f = d + h
Hopefully that didn’t scare you too much. In this formula, “d” is distance traveled, in other words, how far we have traveled so far. In common 2D grid based systems this just increments 1 by 1 as the path is built. Now the “h” variable is a bit more complicated. It represents the returned value of a “heuristic” method. That’s a scary word for a function that guesses how far we need to go. Once again, in common 2D grid based systems this is a simple Manhattan Distance formula, or Euclidean Distance formula. And if that just sounds even more complicated, in reality it is just: how far away is the target if we where to draw a straight line to it. If you have ever calculated how far away an object is, you have used this formula.
Now, I’m going to explain this in a 2D aspect for now, just to simplify the calculations. Adding another dimension is easy. Here is our example 2D scene.
Now lets get our green circle guy to the red X. Or at least find a way to. Now we are going to treat each grid square as a node. In this case our green circle is located at 2,4. And our red X is at 14,5. So the algorithm starts by creating an Open List, and a Closed List. The closed list represents the places we have been, and the open list is places we can consider. So the starting point, instantly goes in the closed list, because well, we have been there. Once we have this point, we look at all the nodes around the point. We add each one of these to the open list for consideration. With each one we calculate its cost/weight. If you remember the formula from earlier that formula now becomes:
cost = 1 + Heuristic(a, b)
Heuritic(Point A, Point B) = SqrRoot( (A.x - B.x)^2 + (A.y - B.y)^2 )
Now this formula is starting to take shape. Here the “1” is just me placing the distance traveled so far. Since this is the first check, and we haven’t gone anywhere, this equals 1. Now the heuristic function takes two parameters, and calculates the distance between them. In this example, “a” should be the current nodes location, and “b” should be the destination. So once we run this calculation on each node that surrounds the current one, the algorithm now picks the one with the lowest cost. This new low cost node gets removed from the open list and added to the closed list. If this makes sense, you should be able to see where I’m going with this. Using the chosen node as the new current node we repeat the process until we have arrived at our destination. Here’s a lovely picture showing this:
You can see from this, that it should choose the bottom right corner as the next stage. In case you where wondering, if two squares have the same cost, then the chosen one is random. As well as if there is an obstacle in the way, just don’t add that as a node. Repeating this process with leave you with a path saved in the closed list. I am not going to solve for this entire example since it isn’t what we are going to use anyways. We will be created a modified version of this that should hopefully have some speed tweeks and other nifty features. Join me next time for the 3D portions!