AI: Fastest algorithm to find if path exists?

Question

I am looking for a pathfinding algorithm to use for an AI controlling an entity in a 2D grid that needs to find a path from A to B. It does not have to be the shortest path but it needs to be calculated very fast. The grid is static (never changes) and some grid cells are occupied by obstacles.

I'm currently using A* but it is too slow for my purposes because it always tries to calculate the fastest path. The main performance problem occurs when the path does not exist, in which case A* will try to explore too many cells.

Is there a different algorithm I could use that could find a path faster than A* if the path doesn't have to be the shortest path?

Thanks,

Luminal

Answer 1

Assuming your grid is static and doesn't change. You can calculate the connected components of your graph once after building the grid.

Then you can easily check if source and target vertex are within a component or not. If yes, then execute A*, if not then don't as there can't be a path between the components.

You can get the connected components of a graph using BFS or DFS.