RTS lockstep multithreaded pathfinding
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?
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.
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. :)
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.
an i7 utilizes hyperthreading, which essentiallty means each core has 2 threads.polyfrag, on 05 Jun 2013 - 23:53, said:
Never mind about 5 threads, I thought core i7 has 8 cores.
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.
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.