Hi everyone,
So basically, in my game, im trying to maintain an even frame rate that is about 1/30 second for my 3D rts game.
I used this algorithm for my pathfinding - http://aigamedev.com/open/review/near-optimal-hierarchical-pathfinding/ .
So basically, I have this higher level map of 10 x 10 clusters of tiles with edge entrances that I use for the pathfinding.
When someone tells a unit to go somewhere, I need a quick way to see if the path is possible at all. So what I do is a flood-fill of the entrances of the 10 x 10 clusters every single frame, to partition the map entrances into global partitions. Then if a unit is commanded to go to a partition that its not already in, I already know that there will be no solution to the A* problem. This is a lot faster than doing a flood fill of the individual tiles of the map. However, the flood fill takes up 1/4 to 1/3 of my processing time each frame (I profiled it), resulting in the battle simulation being just barely fast enough for a small battle involving 60 - 80 active units while the rest of the units just stand there. Any more unit activity, and the frame rate gradually starts to degrade. This is also just for an AI player and a human player managing the two sides.
I've considered the following options to solve my quandary:
1. Dont flood fill and just wait for the A* search to fail, to see if a particular destination is unavailable. If people tell units to go to a place that is unavailable, the A* search will search the *ENTIRE* accessible map from that location, only to finally fail. That will be a slow search that I would expect to degrade the frame rate even more than it's already degraded. But, people can only click so fast, so - it might be better to just bite the bullet for one slow search when the player clicks every two seconds than to be flood-filling the map every 1/30th of a second.
2. Wait until the A* search searches a certain number of nodes, then pick the one with the smallest f cost and pretend it is the destination for now and just go in that path. The thing I can think of wrong with this is that if there is a really wide obstacle in the way (e.g. a wall or mazelike series of walls), the pathfinder will probably just get stuck on the wall. Otherwise, this would work ok.
3. Keep doing things the way I have been doing them. Works ok for 60-80 units in a battle (30 - 40) on each side. If i want larger maps appropriate for more than 2 players, the frame rate will be unplayable.
Also, my game has other scalability issues, but this is probably enough for one post. I'm definitely open to better ideas than the three I just mentioned!