Building a better pathfinder

A while back I was working on a project called “Meander”. It was to be a 2D point-and-click adventure game, and later, a versatile engine for my personal use. One of the things I was most proud of was its pathfinding algorithm. It was my single greatest accomplishment, and even though it had its fair share of problems and design shortcomings, it did its job.

Looking back on the code now, I can see that it’s a huge mess. The code for accessing a given node in the grid is convoluted and only works with specific parameters, and there are many places where I iterate through the entire grid just to check if a single node is valid. I’ve thought about refactoring it lots of times, but the problems are rooted deeply in the design.

Over the past nine days I’ve been teaching myself HaXe. I’m a big believer in learning languages by using them, so I took the opportunity to write an experimental game framework called Astral for HTML5, Neko and Flash Player; three of HaXe’s compiler targets. One of the classes I wanted to implement was a pathfinder that met a few specific requirements:

  • Operated with any dimensions. Meander’s pathfinder only worked with a grid 40 * 30 nodes.
  • Be completely standalone. Meander’s pathfinder had a renderer built in, and returned destinations by pixel.
  • Be fast. No matter how poorly optimized Meander’s pathfinder was, it was written in C++, which is orders of magnitude faster than any of the languages I target with Astral.

Here’s how it went down.

Algorithm structure

An A* or Dijkstra pathfinder is really not a very complicated algorithm. The process is explained here, which was invaluable during my first implementation. The basic idea is to simulate a flood of water from node to node until the end node is reached, then follow it backwards to find the path. Essentially, the flow looks like this:

  • Check if the start node is the same as the destination node. If it is, the path is already solved.
  • Check if both the start and end nodes are in valid positions on the grid. If not, the path can never be solved.
  • Create a new grid to keep track of nodes that have been flooded.
  • Add the start node to the flooded grid. Each time you add a node to the flooded list, keep track of how far many iterations you’ve gone through and set a “cost” variable in that node.
  • Add the start node to a “parent” list.
  • Until the flood reaches the end node, do the following:
    • For each node in the parent list, do the following:
      • Check in each direction around the node to see if the node there is a valid move.
        • If it is, check to see if it has been flooded yet.
          • If it has, ignore it.
          • If it hasn’t, add it to a “next-parents” list, and add it to the flooded list.
    • If the next-parents list is empty, there are no more valid moves and the path cannot be solved.
    • Otherwise, set the next-parents list as the parent list.
  • If the flood reaches the end node,  do the following:
    • Create a FILO stack or queue to use as the path.
    • Add the end node to the path.
    • Until the start node is added to the path, do the following:
      • Check in each orthogonal direction around the node at the front of the path to see if the node there has been flooded.
        • If it has, check to see if its cost is less than the front node’s cost
          • If it is, add it to the path and return to the beginning of the loop, skipping the next step.
      • (Optional) Check in each diagonal direction around the node at the front of the path to see if the node there has been flooded.
        • If it has, check to see if its cost is less than the front node’s cost
          • If it is, add it to the path and return to the beginning of the loop.

That’s all there is to it.

So, how’d I do?

  • I tested the grid with a number of different size configurations, and all of them worked without a problem. Since this was a concern coming into the project, I was able to plan ahead and make sure nothing was hard-coded in.
  • There isn’t one line of code in the whole pathfinding system that deals with any sort of graphics device.
  • Obviously it’s not a good idea to run this solver every frame, but the speed at which it calculates a path surprised me. It’ll never beat a pure C implementation, but for most purposes it should be more than adequate.

Don’t take my word for it though, the source is all available over at the Bitbucket project.