A* (Звезда) Поиск пути замедляет все, когда нет пути

В моей игре RTS я использовал BFS, она очень медленная.

Итак, я использую A* сейчас, очень быстро найти путь, но если нет никакого возможного пути, он заставляет все повеситься.

Чтобы решить эту проблему, я попытался выйти из цикла, если потребуется много, учитывая линейное расстояние между src & dst. Но в некоторых случаях, когда линейное расстояние очень короткое, а путь длинный, он терпит неудачу.