- Run A* on the optimistic pathfinding graph (no obstacles on the unknown cells). - Follow the path found (if there's none, that's it) - As you follow the pat

- Run A* on the optimistic pathfinding graph (no obstacles on the unknown cells). - Follow the path found (if there's none, that's it) - As you follow the path, sense the world and take note of new obstacles. - If there's an action you can't make because of a new obstacle, re-run A. There's ways of re-using the state from previous A runs (as long as the goal is still the same) that becomes handy on complex maps where the path you wanted to follow is blocked deeply. BTW, if you tie-break nodes on lower heuristic value (h-value), then you'll be more likely to search deeper paths, which makes optimizations like trying to follow a straight line kind of useless, but as always, run benchmarks before guessing. Also, if you have a tight deadlines for the search algorithm, like having to make another tick on the game happen, there's some real-time variants of A* that have a bound for how many nodes A* can expand on each run. I don't think you'll need real-time A* though, I remember that this approach using Dijkstra was fast enough for a project back in Uni on now 15yo hardware, so newer hardware using A* must be good enough ever for large graphs.