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.Continue Reading