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.

Answer 1

Take a look at https://github.com/stevennl/Snake, a project demonstrating a few AI algorithms for the game Snake. The project README has a very nice explanation of the algorithm.

The key is for the snake to follow a Hamiltonian circuit (a path that visits every square, and loops back on itself). Many such paths exist for a simple 2D grid, you just have to find one. So something like this:

Finding such a path is also known as the longest path problem. If you make your AI follow this circuit, it will never trap itself and will be able to grow to the largest size possible - filling the entire grid. If you're lazy you can stop here - your AI doesn't even need to care where the fruit is. Of course, this AI will be horribly slow, and maybe boring to watch.

To make the snake faster at eating fruit, you can make it take shortcuts within the Hamiltonian circuit, as long as taking such shortcuts won't make its head overlap its body after taking the shortcut. Here's an image covering the key points:

https://johnflux.com/2015/05/02/nokia-6110-part-3-algorithms/

This algorithm is much better, but still not the best, since it is still following the original Hamiltonian circuit. It's possible that finding other circuits will allow it to take better shortcuts.