AlexRou Posted July 4, 2017 Share Posted July 4, 2017 So people have been complaining about dupes taking long times to decide where to go and other issues relating to pathfinding time as the explored area and colony size grows. Assuming this technique is not in use as restricting dupe movement helps ... In RTS games with rediculously large maps like Planetary Annihilation (only one I found that publicly talks about using it), how they got around the pathfinding delay is instead of finding the path of a single large grid, they split that grid into multiple smaller grids. And then precompute the path to go from every grid to its neighbouring grids. So when finding the path for a unit, they first A* (or some other algo) through the subgrids and use the precomputed paths to get to the goal subgrid. Upon arrival or while on the way (over many frames with low priority) it calculates the path to the actual goal within that subgrid. This technique reduces real time computation to only finding which subgrid to go through and the pathing within the goal subgrid. However when blocks are added/removed the affected subgrids need to be recomputed but since it is relatively small it shouldn't take up too much time. Also since calculating the paths to the subgrid neighbours is not a single starting point to a single goal problem algos like A* will not provide any benefit and may actually be worse, using a algo like a modified breadth-first would mean it just needs to be run 4 times and each run will calculate all possible paths to a specific neighbor. Having multiple smaller grids may also provide additional benefit to the AI figuring out which task to take as it now can get a rough distance (to tasks in another subgrid) by pathfinding the subgrids which would now be a relatively inexpensive operation. Link to comment Share on other sites More sharing options...
This topic is now archived and is closed to further replies.
Please be aware that the content of this thread may be outdated and no longer applicable.