Finding our way through pathfinding

One of the most common coding tasks in game is pathfinding – making sure that characters in the game can move towards their destination, picking appropriate routes, so that they don’t for example, get stuck in a corner or take a roundabout path.

Kristofer just implemented pathfinding in our game, an implementation of A-star. A-star is easily the most common game pathfinding algorithm. It allows mobile agents to plan an optimal path efficiently: rather than searching the entire space, A-star makes directed guesses about the most probable paths, and then narrows down the field step by step until a path is plotted.

What’s cool about Kristofer’s implementation is that he has created a visual instantiation of a unit’s thought process. This lets him visually debug his code by showing him how it is working. But it also makes it easy for anyone to understand.

Here’s how it works. First, the program generates our game’s procedural level architecture. (If you want more details about how that all works, see our last post about how the game creates procedural level geometry.)

Then we can run A-star, using Kristofer’s tool (that interface on the right). Running it now will make the program plot out the path from the red dot to the green dot on either end of the blue path:

The yellow tiles show the outer boundary of where the program searched for routes as it tried to find the optimal path.

The wider the “cone” of spatial range within which program seeks to find an optimal path, the better path it will find. However, the more that it looks, the more program cycles (and therefore time) it will take to complete the process. The Heuristic Distance slider lets us play with the breadth of the search relative to any path finding so we can see how changes in efficiency affect pathfinding.

Here is a different pair of points, with the Heuristic Distance set high so that it looks at less squares:

Notice the relative lack of yellow search squares. And here it is set much lower, so that it searches a wider range:

Not only is there much more yellow, but the program has found a more efficient path to take. (It goes underneath, instead of above, that last clump of obstacles.)

All of this leaves me with a couple conclusions. First, after some experimentation, it seems to me that Kristofer’s homebrew version of A-star works well even with a very narrow “cone” of search range. And in the heat of a real-time game, perhaps it is good that game characters don’t always take the optimal route. That gives me confidence that we can use a low-range, high-efficiency setting of this pathfinding that will not use up a lot of cycles and slow down the game.

The other conclusion is just that I am thankful to be working with such a visually oriented programmer! By making a quick visual debug tool, Kristofer not only makes his debugging work easier, but he can much more easily share this aspect of the code with the rest of the team for input and discussion.

Leave a Reply

Your email address will not be published. Required fields are marked *