Jump to content
  • Advertisement


  • Content Count

  • Joined

  • Last visited

Community Reputation

135 Neutral

About occams_razor

  • Rank
  1. occams_razor

    Partitioning an A* 400x400 map every frame

    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.
  2. occams_razor

    Partitioning an A* 400x400 map every frame

      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.
  3. occams_razor

    Partitioning an A* 400x400 map every frame

    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!
  4. occams_razor

    Partitioning an A* 400x400 map every frame

    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?
  5. occams_razor

    Partitioning an A* 400x400 map every frame

    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.
  6. 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!
  7. occams_razor

    2D Health Bars for Units in 3D Environment

    Ok guys, I think billboards are basically going to work for me. But I appreciate all of your answers, they were all good. I also don't mind the health bars getting smaller in the distance, so thats the reason I went with billboards. Thanks.
  8. occams_razor

    2D Health Bars for Units in 3D Environment

    This satisfies my requirements. Thanks. Is there a way to mark your answer as the correct one?
  9. Hi guys,   I am making a 3D RTS game with Direct3D. Basically, I want to make 2D health bars hovering over my units that show how many hitpoints they have left after receiving wounds. I'm not sure what a good way to go about this would be because the thing is, the health bars have to always face the camera, no matter what angle they are at from the center of the viewport. I also want them to look as close to perfectly rectangular as possible, but I want them to look smaller if they are farther away.   I don't want to post code, so I'm just looking for a "general concept" type of answer.   Thanks
  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!