Jump to content

  • Log In with Google      Sign In   
  • Create Account

Partitioning an A* 400x400 map every frame


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
12 replies to this topic

#1 occams_razor   Members   -  Reputation: 135

Like
0Likes
Like

Posted 03 May 2014 - 07:47 PM

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!



Sponsor:

#2 RulerOfNothing   Members   -  Reputation: 1160

Like
1Likes
Like

Posted 03 May 2014 - 08:33 PM

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)



#3 occams_razor   Members   -  Reputation: 135

Like
0Likes
Like

Posted 03 May 2014 - 08:59 PM

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.



#4 kauna   Crossbones+   -  Reputation: 2501

Like
1Likes
Like

Posted 04 May 2014 - 06:56 AM

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!



#5 occams_razor   Members   -  Reputation: 135

Like
0Likes
Like

Posted 04 May 2014 - 11:58 AM

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?



#6 SerialKicked   Members   -  Reputation: 576

Like
1Likes
Like

Posted 04 May 2014 - 12:28 PM

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?

 

 

It's true. SC2 Pathfinder ignore fog of war. It's fairly easy to spot when you send a worker scout a terran/protoss base, as soon as the opponent wall off his entrance, the unit will change path toward another position it can access. That's usually why good players will put a waypoint just before where the wall off would be so he can actually see the buildings blocking his exploration.

 

As a general advice, apart from a case where you terrain is changing all the time (and even so) there's no reason why you'd want to recalculate the PF every frame. I tend to calculate my path one time and only request another call to A* when the unit detect an issue (path blocked by other units or some rocks for example).

 

I don't know your code but I am guessing that you have not made your game logic system(s) independent of your rendering system and that's why you're requesting too much of your CPU every frame.



#7 kauna   Crossbones+   -  Reputation: 2501

Like
1Likes
Like

Posted 04 May 2014 - 12:31 PM

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!



#8 occams_razor   Members   -  Reputation: 135

Like
0Likes
Like

Posted 04 May 2014 - 01:19 PM

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!



#9 SerialKicked   Members   -  Reputation: 576

Like
1Likes
Like

Posted 04 May 2014 - 02:07 PM

Talking about the pathfinder only, I have no expertise in the CPU/GPU operations you're describing, so my apologies if my post is irrelevant.

 

I played plenty of RTS, from the venerable Siege to current gen games like SC2, I don't really recall any of them not ignoring FoW, but I may be wrong on that matter. 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. In layman terms: what the players want is that the AI doesn't know they are building 200 nukes, they don't care how the AI units will move around maze of nuke silos.

 

What i find weird is that you do need to recalculate your path that often. I find myself unable to find a case that would cause that kind of behavior. I guess that 2 of your units can't use the same "square" of your map and that problem arise when you are moving groups. But it doesn't usually require to recalculate the whole path, there's tricks to avoid that that doesn't rely on using A*. And even so, your individual unit AI system should only be called at semi regular intervals (let's say 100ms) instead of every frame.

 

 

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.

 

 

I am not talking about how you put your code into different files. I am talking about having a (or multiple) thread(s) handling the AI / path-finding and another one rendering a frame at regular intervals. Or at least, if you're not multi-threading, having a mechanism that allow you to skip GameLogic or Rendering steps whenever needed (like calling AI logic every 10 frames). And if you're actually using threads, as suggested earlier by someone else, having 2 or 3 worker threads to "solve" pathfinder questions is a good idea.

 

Cheers,

SK.


Edited by SerialKicked, 04 May 2014 - 02:11 PM.


#10 occams_razor   Members   -  Reputation: 135

Like
0Likes
Like

Posted 04 May 2014 - 07:09 PM


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.



#11 wodinoneeye   Members   -  Reputation: 818

Like
1Likes
Like

Posted 04 May 2014 - 08:44 PM

You might want to consider beyond 'fog of war' if the units should make their path 'optimistic' when the full length is frequently out of sight.  Nearby the need for correction (recalc path) might be normal when the situation IS visible, but is the nature of the game such that further away the units cant see and just assume their current best path  (and that also ignoring dynamic blockage even for midranged visible paths - assuming the blockage might clear itself in the interim...).

 

This would allow keeping to the original planned 'coarse' path until closer proximity causes replanning (and employing the costly repathing)   - thius lowering the number of times the long pathing needs to be recalculated.

 

Real units, if they couldnt see a blockage (do these units have radio or something or full view of the whole map ???) would go as far as possible THEN find a detour path ... but only when really needed.  Perfect knowledge doesnt have to exist.

 

If by doing this you could eliminate alot of recalculation it might give you some significant improvement for your desired  fast cycling.

 

You may have to try it and see if their is a significant improvement - and watch that there isnt excessive backtracking/wasted movement and tune it some (or figure that with YOUR game mechanics it doesnt get you anything and abandon this 'unit waits to see' method.


Edited by wodinoneeye, 04 May 2014 - 08:49 PM.

--------------------------------------------Ratings are Opinion, not Fact

#12 occams_razor   Members   -  Reputation: 135

Like
0Likes
Like

Posted 05 May 2014 - 01:14 AM

Hey wodinoneeye,

 

Yeah I noticed that in my game, I would tell a unit or group of units to go around a wall that it didn't completely see, and the path it took, constantly readjusting, was dramatically different than pathfinding with perfect knowledge (which is how I used to do it, and how I'm going to go back to doing it). When I switch to pathfinding with full visibility, I'll probably get a speed boost from the lack of constant readjusting too.



#13 ferrous   Members   -  Reputation: 1997

Like
2Likes
Like

Posted 05 May 2014 - 08:57 AM

How is the GPU tied to your pathfinding implementation?  You have fog of war, but that could be done without any knowledge of what's being rendered.  






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS