Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 25 Apr 2013
Offline Last Active May 29 2014 07:58 PM

Posts I've Made

In Topic: Partitioning an A* 400x400 map every frame

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.

In Topic: Partitioning an A* 400x400 map every frame

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.

In Topic: Partitioning an A* 400x400 map every frame

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!

In Topic: Partitioning an A* 400x400 map every frame

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?

In Topic: Partitioning an A* 400x400 map every frame

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.