Debugging A* Pathfinding in Unity

I needed fast, efficient, … but powerful, adaptable … pathfinding for my hobby project. My minions have to fly, walk, crawl, teleport, tunnel their way across a procedural landscape. Getting to that point has been tricky, but the journey’s been interesting.

We want something that intelligently routes creatures around obstacles, and picks “shallow” routes instead of scaling cliffs (or vice versa for Giant Spiders etc). Something like this:

Step 1: Unity Asset Store

With anything in Unity, this should always be your first stop.

I researched a handful of the top Pathfinding assets, and directly tested those that had WebPlayer demos and/or free “demo” versions for you to test.

There was some nice stuff there, but overall I was disappointed. Performance was fine, and most of them were using Co-routines or background threads to control the CPU usage. This is a great thing! (relatively easy to do yourself, to be honest – it’s one of A*’s top 2 features).

… but the user-interfaces were crummy (I couldn’t understand them), or … features had hardcoded limits that blocked the algorithm, or … the feature-set was missing core elements of A-Star (e.g. dynamic edge-costs: the other main reason for using it in games) … or … etc.

For ultra-simple uses, most of them are fine. Or for derivative games. And there was one in a 24 hour Asset sale that looked promising, with a big team behind it – but they were cagey on too many details (documentation was only available AFTER you purchase!), and it appeared relatively hardcoded / hard to customize.

In the end, I gave up. And it occurred to me:

Maybe … every innovative game requires you to re-implement A* to support/enable your game’s specific novel features?

(A* is not hard to implement. And there are so many performance choices to make that this might be a case where reinventing the wheel is actually a good thing. Maybe)

What is A*, how does it work, how to implement it?

Here I hand you over to the esteemed Amit Patel …

• 2014: AmitP’s interactive A-star explanation — easier to understand, only covers page 1 of the next item
• 2009: AmitP’s original A-star explanation (non-interactive) — used as reference by a lot of people for implementing themselves, has many pages of info

This leaves us with a base algorithm:

OPEN = priority queue containing START
CLOSED = empty set
while lowest rank in OPEN is not the GOAL:
  current = remove lowest rank item from OPEN
  add current to CLOSED
  for neighbors of current:
    cost = g(current) + movementcost(current, neighbor)
    if neighbor in OPEN and cost less than g(neighbor):
      remove neighbor from OPEN, because new path is better
    if neighbor in CLOSED and cost less than g(neighbor): **
      remove neighbor from CLOSED
    if neighbor not in OPEN and neighbor not in CLOSED:
      set g(neighbor) to cost
      add neighbor to OPEN
      set priority queue rank to g(neighbor) + h(neighbor)
      set neighbor's parent to current

reconstruct reverse path from goal to start
by following parent pointers

Implementing this in C# … in Unity

First of all: Unity is broken in how it uses some of the C# syntax. Without going into detail, some valid C# will corrupt when used in Unity – most obviously here: multi-dimensional arrays. You can patch Unity to fix this yourself, but it’s non-trivial. Instead, simply re-implement with crappier, lower-level structures (sad, but practical).

Secondly: Microsoft’s C#/.NET standard library has a “SortedList” built-in, but IMHO it’s misnamed: you can only have one element for each position (that’s a sorted Map, or a Set-sorted List, not a sorted List). It’s the wrong structure for our case here, although you CAN customize it to work, by making each “item” a List, and moving nodes from list to list. Ugh. Complicated. Again: sad, but practical. Personally I made my own SortedList that does what it pretends to do ;).

Make a Node class

Probably something you already have in your game, e.g.:

[csharp]
public class Node
{
public int x, int y;
}
[/csharp]

And a graph / grid class

e.g.

[csharp]
public class Grid
{
public Node[] allNodes;
public int nodesAcross, nodesDown; // needed to workaround Unity bugs
public Node NodeAt( int x, int y ) // needed to workaround Unity bugs
{
return allNodes[ x + y*nodesAcross];
}
public void SetNodeAt( int x, int y, Node n ) // needed to workaround Unity bugs
{
allNodes[ x + y*nodesAcross] = n;
}
[/csharp]

Make your own SortedList

Fairly easy, but I screwed this up first time around, because I was unfamiliar with some neat tricks C# does internally with foreach loops. I doubt you’ll have problems. For A*, you only need to make a class with these methods:

[csharp]
public class MySortedList<T> where T: class
{
public MySortedList();
public int Count();
public T GetFirst();
public T RemoveFirst();
public void RemoveItem( T victimItem );
public bool Contains( T searchItem );
public int AddWithValue( T newItem, float newValue );
}
[/csharp]

Sanity-checking your algorithm

This is a data-sensitive algorithm, and we’ve created some custom data-structures (OK, not dangerous), and … a custom container (hmm: dangerous! Easy to get wrong in subtle ways).

I strongly recommend you write unit tests for MySortedList. I didn’t (fool! I haven’t adopted a good UnitTesting framework in Unity yet), and regretted it. In particular, focus on:

1. Testing the “Contains” check is accurate
2. Testing the “Remove” methods actually remove items

…miss either of those and A-star will go into an infinite loop, because it keeps adding more nodes to the list. Especially subtle (and an obvious gotcha): the Contains check, and how it checks for equality — make sure you implemented Equals and GetHashcode on your custom classes!

Debugging your algorithm

Now to the fun stuff. This is a DATA HEAVY algorithm: in real-game use, it will be processing many thousands of nodes on each run, and up to tens of thousands of edges. Debugging that is hell. Don’t do it.

Instead, your first thought should be:

How can I make a visualization for this, so that debugging vast datasets becomes quick and easy?

My route:

1. Make a Component for “Calculate A Path”
   1. Put start node in there, end node
   2. Write an Editor / CustomEditor class for this that adds a button “Calculate Path”
2. A* outputs a “Path” object
3. My “Calculate Path” takes the output
   1. creates a new GameObject
   2. Adds that as a child
   3. Attaches a “PathVisualizer” script/component
4. PathVisualizer has an OnGizmos() implementation that:
   1. Draws a cube at every node in the path
   2. Draws a different coloured cube at start and end nodes
   3. Draws lines between each node showing the order / direction of travel along the path

Things to note here:

• Because each path is added to a GameObject, you can tweak your A* implementation, re-run it in Editor, and compare the two output paths, see how well it’s changed from your previous attempt. Awesome!
• I didn’t want the overhead of making my Nodes or Paths be Unity MonoBehaviours; no need: I made a visualization-behaviour instead that holds a reference to “Path that you want me to visualize”

See image at top of post for my first-draft simple visualization.

Visualize the Graph, and the Costs

I also did some work on visualizing the graph itself:

And the Costs (note: I have implemented my Costs to be bidirectional: it is “cheap” to move downhill, and “expensive” to move uphill. Not by same amount! So each edge has two colours, one for uphill cost, one for downhill):

Making it less painful to run

Unoptimized, your A* algorithm should run in a small fraction of a second, for any grid up to a few thousand nodes. It’s practically instant.

HOWEVER … when you’ve got bugs, A* tends to go into infinite loops and hang Unity (Unity sadly has ZERO PROTECTION against scripts doing this).

So, for practical purposes, you want to turn your calculation into a Co-Routine, and put some in-editor info that lets you see if its gone wrong. I decided to add progress bars for how large the Open list and Closed list were. I knew the total number of nodes, and that the two lists couldn’t get larger than that, so I could fill these up:

Co-routines in Editor

Sadly, although Unity allows co-routines in the Editor (Unity’s staff have used them for the recent Editor features in 4.5), you’re not allowed to use them yourself.

…but the coroutine implementation in Unity is super-simple, and quite easy to write yourself. So, using something like this short class that is a full implementation you add that feature for yourself.

I used the same idea (add your own callback to the “update” list, and run the IEnumerator manually), but added some bits about repainting the GUI frequently (not too frequently) and finessed some other minor features.

Assertions and Exceptions

Let me revisit an earlier point:

This is a DATA HEAVY algorithm: in real-game use, it will be processing many thousands of nodes on each run, and up to tens of thousands of edges. Debugging that is hell. Don’t do it.

Assertions are your friend. Most AAA pro game developers love them, especially on Console (they’re great for saving you from writing Unit Tests for a machine that doesn’t have spare memory/performance to run Unit Tests).

I screwed up my implementation. With a little help from Amit, I added the following assertions to my code:

1. Never accept a negative Cost to move from one node to another
   1. This should be impossible. Even if you are doing “weird and cool things” with your Costs in your game, you do NOT want this.
   2. …because A* can and will abuse this, running back and forth over your “negative” edge, getting “free energy!” to reduce its total path cost
   3. You MIGHT want to allow zero-cost edges, sometimes – e.g. a teleporter – but be very careful: they can allow the same ping-ponging, infinite-loop problem
   4. In general: Assert whenever you read an edge-cost and it’s “<= 0f"
2. Last line of Amit’s core loop marks the “current node” as the neighbour’s predecessor. DO NOT ALLOW THIS IF that node is already pointing to the neighbour!
   1. Again: this should never happen, if the algorithm is running correctly. It’s absolutely wrong!
   2. (zero or negative costs would allow it to happen)
   3. But worse: don’t allow a chain of links, where one item in the chain is repeated: this becomes an infinite loop later on when you try to process the path
   4. I added a brutal “when adding a node to end of chain, check it’s not anywhere in preceding links in chain” assertion
3. Never allow the open list to have more than the total number of nodes
   1. Shouldn’t be possible! Can’t have duplicate nodes!
4. Ditto with the closed list (I actually implemented closed list as a Set. But if you have a bug in your .Equals method, you could still break the standard-library’s Set implementation!)