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.