Pathfinding. A*, Djikstra, got some questions.

Got a game similar to rimworld.

Was thinking of dividing the world into chunks so I don't have to regularly update world data (not pathfinding).

Every time I place a building, A* updates the routes of all units not in that chunk or going through that chunk.

-----

So far so good.

My question is, every time a unit needs to perform a new task or is sent to a new location, and the chunks haven't been updated, should they realistically be re-running A* that frame to find the shortest distance, or should I be sort of 'baking' every possible path to every possible location they can look up to save time?

For instance, let's say I let the pawns do their thing, navigating to food, navigating to recreation, navigating to other pawns, etc. If I didn't change the world for ten minutes, wouldn't it be more efficient to just have some static map with the best possible location from every point in the map to every other point? Or at least within a certain vicinity of the last active pawns? Provided the map doesn't update often?

If this is indeed a good solution, How often is too often in this case?

If I did this, would my algorithm of choice change? Is there a different pathfinding algorithm that would work better for this (like djikstra or breadth first?). I don't have any experience outside of A*.

Thank you.

 

Caching paths can be very helpful for maps that don't change frequently... it comes at the overhead of having to store them somewhere, having to write an algorithm to lookup which stored path is best, and adding complexity to your pathfinding system since you now have 2 distinct parts to it... pathfinding, and cached pathfinding.

As for changing algorithms because you're now caching is inconsequential in my opinion. These are independent tasks. If you are caching known paths into some collection, how those paths were generated doesn't matter. They were generated, and that's all the cached lookup algorithm cares about. You could easily replace the dynamic pahtfinding (the A*) with anything and the cache lookup algorithm wouldn't change for the better or worse. The quality of the paths in the cache collection is the only thing that changes... and if A* gives the quality of paths you like, then that's what you want.

 

Just a suggestion for more realistic looking paths, you may want to have a look at Theta*, or Strict Theta* if you have the computational time.