Various algorithms exist to find a path between 2 points. (A*, Theta *, ANYA, etc.)

Does anyone know of an optimization for the case when you do not care about path parameters and do not even need a path returned, but simply a boolean stating if a path between the two points exists?

In other words, are you aware of an optimization in execution time that will provide for if a path exists without going to the computational expense of finding a path for a dynamically changing map? (Static during the test.)

Hmm, I don’t think such a thing would exist. I can imagine some mathematician devoting his entire career to proving that such a thing exists or it doesn’t, but that person is not me, so I’m just going on gut hunch.

I think optimizations you could try would be to bucket out your map, say into 10x10 cells, and when a path comes into a square and back out, you could recycle the solution of that path as long as you know nothing changed in that 10x10 bucket. The amount of gain would be entirely dependent on how dynamic the map is and how often you hit the pathfinder, and how many different paths you’re trying to bore through.

1 Like

To know that a path exist does also mean you have to find (and calculate) it. How can you be sure otherwise? So I think you won’t come around the path calculation. Your best bet is to choose a method which finds a path quickly so which does not necessarily need to find the shortest path but any path. Or which prioritizes paths with a better chance to lead to the target.

Could you elaborate on what your use case is or what you try to achieve with this? Why do you need to know if a path exists when you don’t want to use it?

I don’t know this to be true, or untrue. Many things can be shown to exist without knowing what they are exactly.

An example could be a tower defense game where the map changes dynamically and you do not want to allow it to change in such a way that no path is left. If path verification was significantly less costly than path finding, one could perform that at each change while performing a path finding operation only when necessary.