The next topic is path finding. It’s a tricky subject with an RTS as I’ve found, as ultimately it’s the most complex system each individual unit must perform, therefore it is directly affecting how many RTS units the game can have at a time. The faster the algorithm, the higher the theoretical unit count on the same system. I’m pretty lenient here with my unit count since I’m not asking for a huge Planetary Annihilation / Supreme Commander style RTS, neither am I asking for the precision systems of the Men of War series. I’m going to go with a target count of 100, so I’ should have plenty of CPU utilization room for pathfinding, assuming of course I don’t create a horrible algorithm.
Technical talk aside, I’ve recorded two videos that demonstrate two different versions of pathfinding. Both use Unity’s inbuilt nav-mesh to an extent, which from what I’ve read is a very fast pathfinding system. It didn’t take me long to figure out why, considering there is absolutely no collision avoidance built in which makes it a little less useful. The actual pathfinding itself however is good, and the agent system isn’t bad. The videos will be from a week old built, but it was a good time to record them as I was phasing out the old temporary system.
The only thing I didn’t like about the nav agents is the fact they rotate and move on the spot, giving a very weird sliding behaviour if your agent is meant to be a vehicle, so I’ve designed vehicle units to stop and rotate to a 15 degree zone of their target direction giving it a more natural approach.
Of course, the more important aspect was collision avoidance. RTS buildings can be placed at any time, in addition there’s lots of potential units all moving in different directions. My initial approach was to create a simply temporary system that paths around objects using cross products. This worked alright for pathing around single objects, but with multiple objects, the generated pathing started to become undesirable. I would simply set a temporary destination 90 degrees off a cross product from the unit position and the obstacle position.
The second method, a little less temporary was to implement an A* grid, and use this on top of the nav mesh. The avoidance path is currently not pathed all the way to the destination, meaning that after one obstacle a unit may have to figure a way past another in the distance. It makes sense to a degree as the pathing a long distance may be very processor intensive and may be wasteful considering obstacles can appear, disappear as well as move around.
At the moment the pathfinding works quite well with the avoidance system actually being more complete than the rest. The immediate change I can think of is sending a group move order without the units trying to pass around each other at the destination – setting a group destination pattern based on the relative position of other group units. At the moment, ordering a dozer to construct a building will set the destination to one of the four sides of the building – whichever is closest, after which construction begins.
There’s been quite a few nice additions since the videos, a big one being fog of war which will be fun to talk about, as well as a refinery/harvester/gold combination, of course relying heavily on the pathfinding. Another one being buildings now require a bulldozer to built them!