Tweaking AStar, чтобы найти ближайшее местоположение к недоступному месту назначения

11

Я реализовал AStar в Java, и он работает нормально для области с препятствиями, где выбранный пункт назначения доступен.

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

Есть ли реальный способ настроить AStar, чтобы найти путь к ближайшему местоположению к недоступному месту назначения?

path-finding Дракон Шиван
источник

Ответы:

20

Следите за узлом с самым низким EstimatedDistanceToEnd(т. h(x)Е. Самым низким ), и, если нет конечного узла, от которого можно было бы вернуться, можно вернуться назад с этого узла.

BlueRaja - Дэнни Пфлугхофт
источник
Просто. Я люблю это!
Джон Макдональд
Я просто ударил себя по голове и сказал "до", когда прочитал твой ответ. Спасибо!
Шиван Дракон
1

Это на самом деле не вопрос *. A * - это поиск пути от точки A к точке B. Несмотря на то, что он может быть расширен, результаты могут быть беспорядочными и непредсказуемыми. Вместо этого вам нужен алгоритм, который выбирает ближайший достижимый пункт назначения.

Вот один из способов сделать это: если A * возвращает допустимый путь (начальные / конечные узлы в путях совпадают с входными узлами), вернуть путь. В противном случае...

  • Начать поиск с начального узла
  • Пройдите по всем связанным узлам (не забудьте пометить посещенные, чтобы избежать бесконечной рекурсии)
  • Сравните расстояния до пункта назначения, чтобы найти ближайший узел
snake5
источник
Что - то вроде Заливка кажется наши правила en.wikipedia.org/wiki/Flood_fill к сведению , что вы по- прежнему необходимо A * от начального узла к узлу с наименьшим расстоянием. Также обратите внимание, что это всегда включает проверку всех подключенных узлов и, таким образом, может быть очень медленным.
Рой Т.
Да, это может быть медленно. Но медлительность, скорее всего, будет связана с тем, что узлы разбросаны по всей памяти; это можно легко исправить. Кроме того, можно ускорить его, пожертвовав некоторой точностью - просто пропустите ссылки, которые находятся слишком далеко или указывают в неправильном направлении.
snake5
1
@Roy: A *, BFS, и все подобные алгоритмы Pathfinding будут точно так медленно , как наводнения наполнитель, потому что они все нужно проверять каждый подключенный узел , чтобы убедиться , что нет никакого пути к концу. Однако есть способы облегчить эту проблему; см здесь .
BlueRaja - Дэнни Пфлюгофт