A while back, I found myself looking for a simple C# implementation of the A* (pronounced ‘A Star’) path-finding algorithm to use in 80 Days for finding routes between cities from the raw map route data used by the game.
If you’re not sure what the A* algorithm is or how it works then there’s a good introduction to it here. Alternatively, there are or some pretty nifty video tutorials about implementing it in Unity here.
I did find a few available implementations out there but wasn’t really happy with any of them. Some had a lot more code than I thought the algorithm justified – which I generally consider to be a warning sign. Some of the them required the graph to be specified ‘up front’ meaning that you couldn’t use lazy evaluation techniques to allow searching of non-finite graphs or to get good performance where there is a large overhead of looking up graph information. Others relied on an underlying grid pattern to the graph, which isn’t very useful for a lot of situations.
In the end I decided to implement my own and thought I would share it in case anyone else could benefit from it.
It took me a couple of attempts to get an implementation I was happy with (I didn’t get the LazyGraph definition quite right first time) though IMHO all the best code is implemented at least twice. I have now patched this improved version into the 80 Days desktop port and it is used pretty heavily in my next project.
Implementation Summary
This implementation represents the graph on which the AStar<GraphElement> search is to be performed using a generic struct AStar<GraphElement>.LazyGraph. By using the callbacks given in this struct it allows the graph to be specified procedurally, if necessary, and for non-finite graphs to be searched – without having to be fully specified in advance, which might take a while ;-).
The GraphElement type is for holding the data you want to store at each node. It is the type which is returned by searches so should be descriptive enough for you to interpret a path from a list of GraphElements. An example type for the GraphElement might be a Vector3 which is used to store the position of the node, though I usually find that a custom type with some extra data alongside the position is more useful. If your GraphElement type contains a lot of data then make sure it’s a class, as opposed to a struct, so it will be passed around by reference within the algorithm.
Once you’ve created a LazyGraph you can construct an AStar instance with it and then perform searches using the Calculate() method. Results are returned as an IList<GraphElement> specifying the GraphElements visited by the calculated path in the order in which they were visited.
Repeated searches with the same target entry will re-use cached data from previous searches where there is overlap.
If you’re searching an non-connected non-finite graph then be sure to specify a maxAcceptableRouteLength in your call to the Calculate() method or the algorithm may never terminate (as it can never be totally sure there isn’t a valid path that it just hasn’t found yet). If you are happy to settle for a partial route (where a complete route can’t be found) then you should pass allowPartialSolution = true to the Calculate() method as otherwise it just returns that no route was found.
Finally, notice that the LazyGraph allows you to specify directed graphs (where A being connected to B does not imply B is connected to A) if you want. However, if you just want a non-directed graph then you just need to ensure that you consistently pass connections in both directions from the getElementsConnectedToElementFunc callback.
It’s implemented to work with Unity but shouldn’t need much adjustment to work in a non-Unity C# project (It should just require swapping the using UnityEngine.Assertions code for your own assertion methods (or just removing all the Asserts if you prefer to shoot from the hip!)
The Code
Well, after all that, here’s the actual code:
Examples
The easiest way to show how it is used is the also show you the unit tests I wrote for the algorithm. They are written to work with Unity Test Tools (AKA ‘Editor Test Runner‘ in Unity 5.3+) but should be portable to any NUnit based testing suite.
Note: AStar_Tests.cs needs to be inside an Editor folder in your project to work. It does not need adding to a game object or anything else, just to be in the project.
This code has been tested quite thoroughly (It’s used in 80 Days and Ski Three) but is large enough to still probably contain a bug or two. So if you do notice any issues please let me know so I can fix it for the next person (and myself!). Also, if you do use it in your own project it would be fun to hear what you’re doing with it :-).