@そら Have you checked out D* (Dynamic A* search) - Initially plans using the Dijkstra’s algorithm and allows intelligently caching intermediate data for speedy replanning

https://www.cs.cmu.edu/~motionplanning/lecture/AppH-astar-dstar_howie.pdf​

I don't understand why a large wall is a problem though? It's just an obstacle and would be ignored. You don't really need that much information to run A* and there are speed optimizations everywhere if it really is a problem. Some sort of grid/map layout, start node and end node.

LedMar said:
Some sort of grid/map layout, start node and end node.

Except the OP has many possible end nodes.

@Alberth I guess I don't understand because of the game? You can use the heuristic to make paths more of a priority. You could assign an end node to multiple targets and just have them randomly select one. How many is “many”? I think the OP needs to give more information for the best response? I read it as “a giant obstacle in the way” yet it being the closest, which wouldn't be a problem with A* unless it was implemented wrong?