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

У меня возникли проблемы с адаптацией алгоритма A* для обработки меняющихся сред. В качестве минимального примера рассмотрим эту мошенническую карту:

######
#!   #
###  #
#S   #
##+###
##F###
######

Цель состоит в том, чтобы добраться из S в F, но для этого игрок должен наступить на !, чтобы открыть дверь. Проблема, с которой я сталкиваюсь, заключается в том, что в A * после посещения точки сетки она становится «закрытой» и не может быть повторно введена. Как я могу изменить алгоритм, чтобы решить эту головоломку?


algorithm path-finding a-star
person John F. Miller    schedule 14.07.2012    source источник
comment
Игрок знает, что нажатие на ! открывает дверь +? Потому что, если есть несколько переключателей без указания, какую дверь они открывают, предположение A* о полной информации не работает, и алгоритм не может решить проблему. (Кроме того, vanilla A* довольно плохо справляется с лабиринтами.)   -  person Fred Foo    schedule 14.07.2012

Ответы (2)


arrow_upward
2
arrow_downward

В вашей задаче неверно, что в A *, когда вы посещаете точку (x, y шнур), вы не будете снова посещать ту же точку.

Причина в том, что в вашей задаче состояние — это позиция в сетке, а для каждой двери — ее состояние (открыто или закрыто). Итак, вначале в вашем примере начальное состояние (3,1, {false}). (false означает, что дверь закрыта).

Когда вы достигаете '!' position, новое состояние будет (1,1,{true}), так что теперь, когда вы дойдете до двери, вы пройдете мимо двери.

person barak1412    schedule 14.07.2012

arrow_upward
3
arrow_downward

Вы можете запустить A * дважды:

  1. Сначала найдите кратчайший путь к выключателю (!), где дверь похожа на стену.
  2. Затем найдите кратчайший путь до конца от переключателя, где дверь представляет собой пустую плитку.

Кратчайшим путем будет комбинация этих двух путей.

person amit    schedule 14.07.2012