A* for Artists

PATHFINDERRR

Pathfinding is often classified under AI, but I think maybe it belongs more under procedural generation, or level design, or something. Pathfinding is basically a bunch of algorithms for dynamically determining a path between point A and point B within a playspace. You can then distill waypoints from that path, which your game objects can use to navigate the environment. All in all, useful stuff!

However, traditionally these algorithms are not presented in a practical, simple manner. For example, from Wikipedia's entry on A* (a well-known and useful pathfinding algo):

"Starting with the initial node, it maintains a priority queue of nodes to be traversed, known as the open set (not to be confused with open sets in topology). The lower f(x) for a given node x, the higher its priority. At each step of the algorithm, the node with the lowest f(x) value is removed from the queue, the f and h values of its neighbors are updated accordingly, and these neighbors are added to the BLA BLA BLA BLA BLA BLA BLA BLA"

So I dutifully avoided pathfinding for most of my programming career, until I started working on a racing game with a level editor. Suddenly, both for the AI rivals and for the "autopilot" powerup, being able to dynamically generate waypoints based on any track configuration sounded pretty useful, as it would be able to save me a lot of time and effort throughout the entire development if I didn't have to manually place waypoints for every track design.

However, I was pretty sure that digging into traditional computer science pathfinding would be kind of a bust, at least psychologically, so I started looking for something simpler, more puzzle-oriented; something like maze navigation techniques.  Heartened by the relatively plain english, I started looking through the Maze Solving Algorithms section, until I read this:

"...this algorithm finds the shortest solution, picking one if there are multiple shortest solutions. It focuses on you multiple times, is fast for all types of Mazes, and requires quite a bit of extra memory proportional to the size of the Maze. Like the collision solver, this basically floods the Maze with "water", such that all distances from the start are filled in at the same time (a breadth first search in Computer Science terms) however each "drop" or pixel remembers which pixel it was filled in by. Once the solution is hit by a "drop", trace backwards from it to the beginning and that's a shortest path. This algorithm works well given any input, because unlike most of the others, this doesn't require the Maze to have any one pixel wide passages that can be followed. Note: this is basically the A* path finding algorithm without a heuristic so all movement is given equal weight."

What a relief; an A* description that actually makes sense! To make things even simpler, I have made some diagrams illustrating how the algorithm works:

This is our initial maze.  Pretty simple!  You start at the green box and end at the red box.

So, this is the "flood the maze with water" stuff that the Maze page was talking about.  You just start filling up every empty square around the current one.  I've changed the algorithm a little bit here; instead of keeping track of which square filled which, I'm just increasing the number we store each time by 1.  This is like storing the distance from the start, and simplifies things a bit.  In this case, there is only one empty square. so we've marked a '2' in the correct place.

Then, you repeat the process, but starting from '2' instead of the start.  Find all the neighbors, mark them with the incremented number, and advance. Again, there is only one possible neighbor, so we just write in a '3'.

All neighbors, even diagonal/kitty-corner are fair game, so mark 'em off and keep going!

Ok now hopefully we are starting to see a nice easy pattern here.  As the "water" floods the maze, we're just keeping track of how many square away it is from the source, or the start.  Now we are going to fill up the rest of the maze pretty quickly:

That'll do it! The code to accomplish this "flooding" process is very simple, and there are a variety of ways to accomplish it, but I think a while loop and a stack (or vector used as a stack) is the easiest, most obvious way.

Now that we have a maze that is completely filled, we can start figuring out what is the fastest, most efficient route to completing it.  This is a very easy process now that we have all of our distances safely recorded.

All we are doing is counting down from the highest number, and preferring straight paths over diagonals where possible.  So for the first step of our path, we're going to count down from 32 to 31, but we're going to choose the orthogonal or straight path instead of the diagonal one.

Same thing - 31 down to 30, straight path over diagonal. 30 down to 29, straight path over diagonal. Easy stuff! Let's fill in the rest:

NOTE: updated April 1st, path was off between squares '3' and '9'.

So we went 29 down to 28, and on a diagonal as there was no good straight path available.  Then 28 to 27 on diagonal, then 27 to 26 back on the straight path, etc, all the way back to 1.  Now we have a perfect optimal path through the maze!

Finally, you can optimize the path you get back by removing redundant straight sections:

This is easier to store and will allow your game objects to drift realistically from the path during long boring sections.

Well, that's all there is to it. A* is an algorithm that is fast enough for real-time use and is easy enough to understand that even artists can do it.  I think. Have fun!