Скачать или смотреть [Unity3D Hex Map Game Dev] 41: Path Finding on a Parallel Thread

Hello Unity fans and welcome back to my game development series. We’re currently busy with a mini-series on optimization and threading, and today we’ll continue on that journey. If we can find a path! Path finding is a part of the game that can be responsible for frequent, annoying temporary reductions in frame rate. This is especially true if you want to implement some kind of intelligent path finding, where you may have to check a few paths for each unit before deciding which units are best suited to perform which tasks. Let’s see how we can have complex path finding and task optimization without it causing stutters in the frame rate.

➤ Subreddit:   / world_turtles  
➤ Patreon:   / recogmission  

Music:
Aretes by Kevin MacLeod is licensed under a Creative Commons Attribution license (https://creativecommons.org/licenses/...)
Source: http://incompetech.com/music/royalty-...
Artist: http://incompetech.com/

A Robust Crew by Darren Curtis

If you want to implement complex path finding in the main thread, all other game and visual updates need to wait for the path optimization to complete. This causes variances in the frame rate, or stutters, which is annoying. To get rid of these, we move our path finding and other optimization to a separate thread, let it continue in the background, while the main thread continues running and updating frames. As soon as the path finding has completed, we need to incorporate its results into the main game. It actually isn’t too difficult to do, but there are a few very important considerations to get right, or it could lead to data races. And we all know how that eventually leads to the decline of civilization…

If you’d like to brush up on how we perform pathfinding, feel free to first watch the video linked to in the top-right. However, it’s not required, since I will briefly revisit the parts most applicable to the threading process now. As part of the search process, we had to keep track of segments already visited by the search algorithm, so that it doesn’t revisit segments unnecessarily and go into infinite loops. We handled this by using a search frontier phase. Each time a new search is started, an overall search frontier phase is increased, and a search phase for the starting segment is set equal to it. Then, we increase the search phase for each segment visited during the particular search, and only allow a segment to be visited if its search phase is not higher than the current search frontier phase.
We could let the path finding thread use these variables as is, but there’s another consideration. We still want the option of performing some pathfinding on a separate thread. I’ve actually implemented a separate pathfinding thread to handle the exploration of the map, since it requires a surprising amount of effort to calculate which hexes can be seen by many units moving around on a largely unexplored initial map, especially if you want the terrain to influence visibility. If the different path finding processes use the same search frontier, they’ll mess each other up. So, we create arrays of search frontiers and search phases, to allow each thread to use its own. When searching, you now have to specify which thread is handling the specific search, and the corresponding set of search frontier data will be accessed. We also need arrays for the distances of the paths, and for storing the links between steps of the paths so that these can be retraced to find the complete actual best path. Even so, it’s really not too much of an adjustment to make. Of course, we also need to specify a thread to which we’ll pass our parallel tasks.

So, now that we are able to search for paths on a separate thread, how do we separate the tasks and their path finding from the main thread, and how do we incorporate it back into the main thread when the parallel running has completed? Again, I’m linking a previous video on my task system in the top-right if you’d like to brush up on that, but the main points to understand are the following...