Pathfinding

If you've read the previous post then you'll know that I'm building an RTS game in my spare time, the area I've chosen to initial focus on is one that will unfortunately probably be replaced when we finally make the move to Unity Pro as it has this feature built in. This however is a good starting point as its an interesting subject that is far more difficult than you'd first expect it to be.

I chose to start with basic pathfinding, we'd already decided that the easiest way to allow placement / movement of units and buildings around the map area would be to use a grid system, after some research into how pathfinding should work we discovered the generally accepted way of doing this was using an algorithm called "A*" (Pronounced "A Star").

I found a fantastic website (written in 2005!) on how the algorithm works by Patrick Lester, I'll paraphrase a lot of what he's put here so you can get the jist of it, however if you're interested in learning about it in-depth then I'd highly recommend you give his page a read.

The basic theory of the A* Algorithm is that we score the potential moves from the initial location in relation to the direction we need to move. Essentially this process repeats over and over (totalling up the score), until we finally reach the point we're looking to reach. This may take several passes sometimes but the lowest total scored path found should be shortest route. The scoring works by the score being significantly higher if you're moving in the opposite direction to the point you're trying to reach, and as the algorithm will look for the lowest scored node to move to from its current position you should be getting closer to the target point each move you make, however if you encounter a bottleneck in the map you might have to double back on yourself. The algorithm will take this into consideration though, and won't include the incorrect portion of this path in the final value.

As you might imagine this particular search is quite intensive on the CPU due to finding multiple paths at any one time, so should be done as infrequently as possible. If you need to move lots of units at once, then the best way to deal with this is to queue up the path finding into different frames. If your game is running at 30-60FPS a 1-2 frame delay in calculating the paths for various units shouldn't matter too much in the grand scheme of things. Another way of coping with this is storing the calculated paths in memory once done, then if another unit can re-use the same path (or extend it, or even use just part of it) to get to the point they're going to, that should save on processor time significantly.

Writing the actual A* algorithm in c# wasn't too bad, however to sort the chosen paths we need to use what is called a 'binary heap', this allows us to very quickly get the lowest value in a particular group of values. While you might wish to use arrays / collections to achieve the same result you'll find that once you're running lots of these path finding algorithms at once it'll get very slow, hence why the binary heap method is prefered. Again theres a brilliant article by Patrick Lester on binary heaps and why they're so useful in the A* algorithm which is a bit in depth, but well worth a read if you're interested in implementing this yourself.

Once I'd got the binary heap class working along with the A* class then tests of the pathfinding function worked as expected, it was very fast to search through the map grid, and work out the most efficient route to a particular square. To make something impassable (such as when a building is placed) we just remove it from the usable grid squares, meaning that units walk 'around' the buildings on the map.

So while this implementation is basic and will eventually (probably) be removed when we upgrade to unity pro, it will work as a stop gap, and currently seems to work quite well. At least now we have basic unit movement when we implement units in the game.