Jump to content
  • Advertisement
Sign in to follow this  
polyfrag

RTS lockstep multithreaded pathfinding

This topic is 2230 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

This might belong in Multiplayer.

I want to use a separate thread for pathfinding, updating game logic, and rendering. For pathfinding, each unit will have a "needpath" and "haspath" variable, set true when a goal has been defined and when a path is ready respectively. However this might cause synchronization problems with the game logic loop in multiplayer. What if one client processes the pathfinding thread faster resulting in a unit doing damage to a unit that gets in range in a certain lockstep turn while another client doesn't?

Basically how would you allow the benefits of multithreading while maintaining RTS lockstep? Have a certain counter for the lockstep frame for each thread? And then require the pathfinding thread to process all requested paths before advancing the frame counter?

Share this post


Link to post
Share on other sites
Advertisement
Also, I was thinking, since a jump resulting from an if statement would flush the CPU and result in a slowdown, would it be better instead of using boolean variables for "needpath" and "havepath" to use a function pointer and set it accordingly to a function that either does nothing on the pathfinding thread (needpath=false) or calculated a path (for needpath=true), and a function that either does nothing (for havepath=false) or does movement or whatever else is necessary like compare the distance to a previously obtained path (havepath=true), and have an appropriately set "afterpath" function pointer for each unit that does the appropriate action after the path is obtained?

Share this post


Link to post
Share on other sites
If one lock-step client computes a path, then both clients have to wait until the other client does computes the same path.

I wouldn't say that the main benefit of multithreading is that operations become asynchronous and result timeframes unpredictable. I'd say the main benefit is the ability to utilize multi-core CPUs. I'd still make the path finding operation predictable (will find a result in exactly n frames) in a multi-core implementation.

Share this post


Link to post
Share on other sites
Also, if I use an unsigned int to count frames, will it reset to 0 once it overflows? Need to increment a frame counter without using if.

Share this post


Link to post
Share on other sites
Or instead of function pointers i coupd have an int that references a function array. I could have FIVE pathfinding threads and an array with an int for each pathing thread for each unit. Won't this cause the CPU to flush too since it has to predict the value the int will have?

Share this post


Link to post
Share on other sites
Guest Hiwas

This is a bit more complicated than you might be thinking.   Does it include avoiding buildings? (Or worse, trying to avoid other units which might 'take' an area.  I.e. mega units.)  If you process the path over a number of time steps where buildings can be added, bad things happen.  As to the caching, having a thread per path is generally a bad idea for multiple reasons beyond just the cache.  I remember there being a hell of a lot of problems with implementing this properly in a threaded manner and per path threading is not a good solution in general, it's almost always "slower" than many other ways to approach it.

 

Your other question tends to suggest a worry about trivialities which are not needed.  Updating a uint which overflows is such a trivial item that it's just silly to worry about.  I use uint32_t counters where they mark 0 as invalid, so everytime I update one I have to check for zero and do a ++ on it if it wraps.  So what, it is such a trivial performance issue as to be a non-issue.

 

NOTE: as a suggestion, when you add continual small comments, you might just want to update a prior message instead of adding more posts.  Condensed information is easier for others to process and reply to.  Just a suggestion. :)

Edited by Hiwas

Share this post


Link to post
Share on other sites

polyfrag, on 05 Jun 2013 - 21:51, said:
Also, if I use an unsigned int to count frames, will it reset to 0 once it overflows? Need to increment a frame counter without using if.


the possibilty exists, but if your only updating that counter 60 times a sedond, then it'd take days to hit 2^32. ane yes, if arthmitic goes over the size of the type, it simply drops the bits, in essence it looks like it wraps around.

polyfrag, on 05 Jun 2013 - 22:22, said:
Utilizing multi-core CPUs is exactly what I'm after.


writing parrelized code for pathfinding of a network game is likely to be more of a problem, then a benefit. you want predictability of when things will finish, if the rts is solely single-player, you might be able to get away with it being not very pridictable in terms when it finshes.

polyfrag, on 05 Jun 2013 - 21:43, said:
Also, I was thinking, since a jump resulting from an if statement would flush the CPU and result in a slowdown, would it be better instead of using boolean variables for "needpath" and "havepath" to use a function pointer and set it accordingly to a function that either does nothing on the pathfinding thread (needpath=false) or calculated a path (for needpath=true), and a function that either does nothing (for havepath=false) or does movement or whatever else is necessary like compare the distance to a previously obtained path (havepath=true), and have an appropriately set "afterpath" function pointer for each unit that does the appropriate action after the path is obtained?


this all sounds like alot of pre-optimizations, and alot of unnecessay complexity.

polyfrag, on 05 Jun 2013 - 23:53, said:
Never mind about 5 threads, I thought core i7 has 8 cores.

an i7 utilizes hyperthreading, which essentiallty means each core has 2 threads.

polyfrag, on 05 Jun 2013 - 21:34, said:
This might belong in Multiplayer.

I want to use a separate thread for pathfinding, updating game logic, and rendering. For pathfinding, each unit will have a "needpath" and "haspath" variable, set true when a goal has been defined and when a path is ready respectively. However this might cause synchronization problems with the game logic loop in multiplayer. What if one client processes the pathfinding thread faster resulting in a unit doing damage to a unit that gets in range in a certain lockstep turn while another client doesn't?

Basically how would you allow the benefits of multithreading while maintaining RTS lockstep? Have a certain counter for the lockstep frame for each thread? And then require the pathfinding thread to process all requested paths before advancing the frame counter?


in a network game, you want predictability, otherwise you sending more data over the network to fix the clients simulation. the nsture of multi-threading means you don't know exactly when the path is going to finish compared to your game logic. it's defiantly possible(and recommended) to decouple your rendering, and game logic, but trying to decouple game logic from game logic can be very ticky to make things work, and sync correctly. combined with the overhead of networking makes it damn near impossible without utilizing tons of network bandwidth. i'd make sure it's actually a problem, and that I can't optimize the game logic before I go and look at adding more threading overhead to "maybe" get a performance boost.

edit: however if I had to do this, i'd set aside a point in my a thread that deals with finding unit paths, at this point, i'd have a pool of threads to do the pathing, and lock my main threaad until the pools finsh. it's really the only way I could see it working without have serious problems. Edited by slicer4ever

Share this post


Link to post
Share on other sites

Also, if I use an unsigned int to count frames, will it reset to 0 once it overflows? Need to increment a frame counter without using if.

If you have to ask that question, you're definitely not ready to talk about multithreading. Sorry to be this harsh, but multithreading is an extremely advanced topic, even more so if determinism and lockstep is involved; and you are not familiar with the basics of two's complement integer arithmetic. That is, a beginner question.

Start your first game single threaded, and possibly of smaller scope.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • 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!