Алгоритм поиска и динамические препятствия

Question

Я обеспокоен окружающей средой, содержащей только двери, ключи и стены. Двери могут быть пропущены, если ключ был "подобран" (то есть был посещен узел, содержащий ключ).

Задача состоит в том, чтобы найти путь между данной точкой A и B. Оптимальное решение не требуется.

Давайте представим дверь с "D", ключ с "K" и стену с "#", теперь рассмотрим окружающую среду ниже. Цель - B, происхождение - A. Мы представим пустые квадраты с "."

###..........K
#BD...A.......
###...........

Теперь, очевидно, в этом случае мы должны посетить узел, содержащий K, прежде чем двигаться к цели B. В настоящее время я использую AStar с эвристической скидкой на посещение "ключевых" узлов с манхэттенским расстоянием до цели, однако, когда K далеко, этот подход борется, так как он занимает слишком много памяти и времени.

Мне любопытно посмотреть, какие алгоритмы, по вашему мнению, лучше всего подходят для этой конкретной проблемы? Или мой выбор алгоритма правильный, но эвристический плохой? Пожалуйста, сообщите, и, поскольку я новичок, пожалуйста, будьте максимально объяснительными в ответ.

Приветствия.

Answer 1

Я бы подошел к этому как к двухэтапной проблеме. На первом этапе используйте алгоритмы автоматического планирования для определения возможных последовательностей событий, когда событие посещает ключ / дверь / точку B. Структура данных с непересекающимися наборами может быть полезной при определении того, соединены ли два местоположения через пустое пространство и незапертые двери. На втором этапе используйте A*, чтобы реализовать план.