2d gridbased Pathfinding: самый дешевый способ/алгоритм, чтобы выяснить, доступно ли местоположение

Question

Мое главное отслеживание выполняется с помощью реализации алгоритма aStar. Производительность великолепна, пока есть доступный путь.

Однако, если их нет, тогда потенциально все доступные узлы будут проанализированы до тех пор, пока вы не придете к выводу, что пути нет.

В худшем случае я могу придумать очень мало препятствий относительно близко к месту назначения, окружающему его.

Некоторых идей, которые я придумал до сих пор, что может увеличить общую производительность:

• найти и выполнить недорогой поиск пути algorithmn, который запускается только выяснить, если цель достижима, если она есть, запустите aStar, чтобы получить реальный путь.

• соберите все неоспоримые узлы вокруг целевого узла в указанном радиусе и посмотрите, все ли они связаны. Если они есть, цель «недоступна» и не может быть достигнута. Выполнение эквивалента для начального значения не обязательно, так как это делает способ сбора узлов.

Так что я прошу здесь, если есть кто-то там, что есть некоторые bulletpoints/идеи, которые я мог бы добавить в список, или указать меня в сторону более дешевого алгоритма поиска пути, который я могу использовать чтобы убедиться, что есть путь

Answer 1

Первая идея, следует уточнить!

Из-за вашей эвристики, A * потратит большую часть времени на цель, , создав вокруг себя «посещенную» стену.

поэтому я думаю, что вы можете проверить продолжение «стены» посещенных площадей, , если вы найдете закрытый непрерывный путь, содержащий цель, но не источник, вам нечего искать дальше.

Вторая идея, не полный, но, вероятно, уменьшить «LOST» время,
Использование Bi-Directional A *, источник работает до пункта назначения, но в то же время назначения найти свой путь к Источнику.

Посмотрите на https://qiao.github.io/PathFinding.js/visual/, чтобы получить представление о том, как он будет себя вести.