Jump to content

pathfinding optimization proposal


Recommended Posts

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

Hierarchical A* is more suited to "flat" topology, where neighbors are expected to be interconnected. In ONI, generally only left and right (and sometimes up and down) neighbors are connected - that is, long stretches of tiles and long stretches of ladders.

For ONI, a more topology-dependent pathfinding method would be better. For example, a long stretch of identical tiles with no obstacles or ladders can be treated as just two nodes on the graph - the first and the last one. You only ever need to care about the tiles in the middle if you want to reach (and not just pass) them.

Link to comment
Share on other sites

46 minutes ago, vonVile said:

I always thought the best solution was assigning a number to movement per tile.

walk = 0

ladder = 1

climb = 2

Whatever the lowest number computed to reach a destination would be the path taken.

You are still computing for the entire map. If you split the map into sub grids instead of computing lets say 1024 x 1024, you are computing 64 x 64 or whatever size you decide the sub grid should be since how to get to that sub grid would have been pre computed.

46 minutes ago, Coolthulhu said:

Hierarchical A* is more suited to "flat" topology, where neighbors are expected to be interconnected. In ONI, generally only left and right (and sometimes up and down) neighbors are connected - that is, long stretches of tiles and long stretches of ladders.

For ONI, a more topology-dependent pathfinding method would be better. For example, a long stretch of identical tiles with no obstacles or ladders can be treated as just two nodes on the graph - the first and the last one. You only ever need to care about the tiles in the middle if you want to reach (and not just pass) them.

Well I didn't specifically say to use Hierarchical A*, just the idea of splitting the map into sub grids. If they did dynamic sub grid generation then it would be possible to have a long hallway as one sub grid. But I'm not sure about the performance of doing so, but since it's not generating too often it might be fine. Also if you store which neighbours are reachable then you don't have the problem of expecting all 4 to be connected.

Link to comment
Share on other sites

Archived

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.

×
  • Create New...