Correct way to handle A* no pathing?

Question

I'm developing a little game for fun and I wrote a pathfinding system based on the A* algorithm. What is the best or correct way to deal with unavailable paths?

A* by default will go through every node on the grid until it either finds the target node or it has exhausted all of them. This can become problematic if certain areas are cut off into "islands" and A* tries to find a path there.

The obvious solution might be to flood fill regions and check in advance, but the problem is that I plan for my world to be a bit dynamic - new areas might appear, some areas which are accessable at one point might not be later, etc.

Another solution I've read about is that I can limit the amount of nodes it's allowed to search before it gives up, but this sounds a bit hacky and something I'd like to avoid if possible if there are better ways, because it means that there could be a very long and complex path to the target but it'll still not find it just because of this limit.

So how should I do it? I appreciate any help here, fellow devs!

Answer 1

Normally, if it is possible for there to be isolated sections of your graph, you would want to have an extra parameter for what "set" each node belongs to. All nodes that are connected in the graph have the same set value. Nodes which are not connected in the graph have a different set value. That lets you perform an immediate out by checking if start set != end set.

To add a dynamic connection, you could store a data structure that defines what two sets a particular node connects and its location, as well as if it is active or not. If start set != end set, then you can search for a dynamic connection in your list that connects the two sets and is active.

Answer 2

Having a node limit for your pathfinding is actually a very common thing to have.

If a* is not good enough for your game, then there are some more advanced solutions you can try, like hierarchical pathfinding or precalculated navigation meshes.