Частично наблюдаемая игровая карта - уместна ли A *?

16

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

Рассмотрим эту настройку: агент находится на 2D-карте и должен найти кратчайший путь к глобально известному объекту, но у него есть только информация о препятствиях в его локальном поле зрения (т. Е. Известны только непосредственные препятствия, общий макет карты неизвестен ).

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

Вычислительная эффективность также имеет первостепенное значение и важнее точности.

Подходит ли A * для этого варианта использования?

algorithm path-finding maps Дэвид Шуинар
источник

Ответы:

19

Вы должны использовать алгоритм D * , который разработан для этого точного сценария. В частности, реализация D * Lite является наиболее эффективным и простым вариантом.

jmegaffin
источник
2
Очень актуально . Понимание D * -lite становится простым, если вы понимаете LPA * (алгоритм D * -Lite основан на) , но сам LPA * довольно сложен. Итак, если вы планируете на самом деле реализовать D * -lite, то вам следует начать с документа о LPA * (если вы уже понимаете, что такое A *)
BlueRaja - Danny Pflughoeft
3

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

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

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

Адам
источник
2
Хорошие предложения, не подходящие для моего варианта использования, но могут быть полезны для других. (Я разрабатываю ИИ, чтобы соревноваться в игровом симуляции)
Дэвид Шуинар
Существуют также игры, в которых используется реализация поиска пути, предполагающая, что неисследованные области являются пересекаемыми, в то время как ранее посещенные области не имели каких-либо изменений в проходимости с момента последнего посещения (т.е. он не будет знать, что стена может быть разрушена или построена до тех пор, пока она не посетит область опять таки).
Ли Райан