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!

One obvious question here is how often the map changes. When you check for passability, does this take into account mobile objects? If not, you could probably get away with only updating the partitions whenever the stationary objects on the map change (probably just building construction/destruction, but maybe terrain modification if you are planning on including something like that)

Hi RulerOfNothing,

So, when a mobile unit stops, I suddenly incorporate it into the pathfinding grid, and when it starts moving again, I remove it from the pathfinding grid. I use rudimentary steering to get units to navigate around each other when they bump each other, and units in the same formation are allowed to move through each other to their formation spots. Also, I allow the user to create terrains by hovering the mouse over a tile and typing "t" (to create) or "d" (to delete). So the map can be assumed to be constantly changing.

Well, it is logical that at some point your algorithm takes more time that you can spare. Especially if the amount of units isn't too limited.

So maybe you'll need to consider some options:

- run the algorithm only for certain milliseconds per frame - you wont get results instantly but most of the time it doesn't matter and the hit to the frame rate is more controllable

or

- run the path finding algorithm on a separated thread, or run multiple search algorithms in the same time on different threads. Of course, if the environment is dynamic, you'll need to stop the search while updating the structures, but that shouldn't be too difficult. Again, you won't get instant responses, but on a multicore system which as pretty standard these days, your frame rate hit can be close to zero. The modern C++ multithreading functions make this pretty easy.

ps. I'd also look into StarCraft 2 units systems - they move hundreds of units in same time.

Cheers!

Hi kauna,

Your second answer looks like it could work, but I have a few more questions. A part of the reason that my pathfinding is slow is that I am shipping texture data from the GPU to the CPU to give different fog of war visibility data to each player. Specifically, shipping 160000 doubles from GPU to CPU every frame. So part of the problem is that I am flood filling the map twice - once for each player.

One thing that I could do is just have fog of war be a graphical appearance phenomena for each player, rather than also have it influence the pathfinding. My question to you is, would the unrealistic pathfinding that results - units having pathfinding information that they're not supposed to have - be a deal breaker for the gaming experience. Specifically, I've heard that starcraft doesn't have fog of war influence pathfinding. Is this true? If it is, I guess I don't need to have fog of war influence pathfinding, because Starcraft 2 is de facto industry standard of rts quality?

After reading your second answer, I found that it may be possible for me to thread the search while I'm doing part of the rendering - it seems to be totally independent of the map during that phase, so if I could do those two things at the same time, that would work great. What do you think about all this?

Just to ask one thing : you say that you stream a lot of data from GPU to CPU - are you making sure that it isn't part of the bottle neck here? Let's say that you copy a GPU resource to a staging resource and you map the staging resource right away, the CPU must wait for the GPU to finish all other operations (ie. sync) which typically will slow down the program execution at least a bit. So typically you'll need to wait before accessing a resource used for data transfer (such as 1-2 frames).

I think that it is a bit of overkill to have a fog of war for each units - how about fog of war for each faction?

I'd try to implement the path finding in a way that it is more and less independent from the program execution.

Cheers!

Ok, so to address both of your questions - my pathfinding does check the current path and then recalculate the current path, only if the old path is invalidated. Also, lets keep in mind that the bottleneck I am addressing is the partitioning via flood-filling of the entrances of the 10x10 clusters. This game is very simple, so there are two players, but only one faction. Also, only one unit in the faction. kuana, you are correct in that I have a bottleneck in streaming from GPU to CPU, it is also a substantial bottleneck, just not as bad as the flood-fill partitioning one. SerialKicked, I have made my game logic system *partially* independent from my rendering system. For example, I have one cpp file for rendering and one for map pathfinding. The map pathfinding one is sort of "layered over" the graphics one. The graphics one does not include the h file for the map pathfinding one. Harming modularity, I have that extern array of 320000 doubles (sorry I said 160000 before but I forgot about it being for two players), and it gets accessed directly from both the map source file and the graphics source file. A bigger problem with modularity is a few callbacks I have that are basically a workaround for me to access higher layers from the graphics layer and violate modularity to "get stuff done". There aren't too many of these, but they exist.

Are there games where the pathfinding does not ignore fog of war? Is it really, really hard to get performant code if you incorporate fog of war into pathfinding? Do you have examples of games where each of say, 2 teams of n players, has pathfinding that is specific to their specific fog of war?

The reason I ask is that if I get rid of the pathfinding that takes information from fog of war (and just use pathfinding with perfect information) - then I immediately get a huge speedup because of the following reasons.

No streaming from GPU to CPU. Bottleneck completely eliminated.

Get rid of extern array of 320000 doubles - slightly improving code modularity, just a little bit, but everything helps.

Instead of needing to floodfill once for each player, I only need to flood fill once in total.

Since its been reduced, kaula's threading answer would reduce probably the bottleneck of flood-fill partitioning by an enormous amount maybe to 10% of currently what it is.

This new thread would be adding a 4th thread to the UI thread, the thread that I have to call IDXGISwapChain::Present for graphics purposes, and the thread that I have to process the pathfinding and fighting and then tell the GPU what to present. I have synchronization protection for IDXGISwapChain::Present, and the graphical portion of the game logic thread.

So now my question has sort of evolved to this:

Would it be a bad thing to keep fog of war as solely a graphical effect, and not influence pathfinding at all? So the AI cheats and sees everything. But mostly, it helps a lot with the frame rate.

Thanks guys and cheers!

Given that PF is the first thing players are going to complain about, giving it full vision has more pros than cons to be honest. Also, it doesn't mean that the AI doesn't take FoW into account for other matters. Yes it will know it can't go that way, but it still has no idea about what kind of forces are blocking the path, it doesn't see the enemy base, and so on. Giving full vision for pathing doesn't imply you'll give full vision for other logic systems.

So what this means is that I'll have to upload data from the GPU to CPU, in order to block non-Pathfinding knowledge from the AI. This is also necessary so that when a user selects a group of units and clicks in the fog-of-war region, it doesn't accidentally select a unit to attack when it shouldn't even know about that unit. kauna and SerialKicked, both your answers basically made the solution for me. Thanks to everyone who posted on this thread to help me.

On the upside, with this approach, i only have to partition the map once for all players, so the main bottleneck is reduced by a lot, especially when you factor in the threading. Also, if there are only two teams on the map, I only have to stream data from the GPU for two different perspectives, not 4 or 8 if there are 4 or 8 players. Well, that sounds good.

Im glad that I dont need to limit the pathfinding data - that was really destroying the frame rate.

Well, I think I basically have my answer for this question.