Częściowo obserwowalna mapa gry - czy A * jest odpowiedni?

16

Bardzo mało wiem o tworzeniu gier i staram się owijać w głowie algorytmy wyszukiwania ścieżek.

Rozważ tę konfigurację: agent znajduje się na mapie 2D i musi znaleźć najkrótszą drogę do znanego na całym świecie obiektu, ale ma tylko informacje o przeszkodach w swoim zasięgu widzenia lokalnego (tzn. Znane są tylko przeszkody bezpośrednie, ogólny układ mapy jest nieznany ).

Ponadto każdy ruch do sąsiedniego kwadratu jest kosztowny, a algorytm wyszukiwania ścieżki powinien minimalizować liczbę ruchów.

Wydajność obliczeniowa jest również niezwykle ważna i ważniejsza niż dokładność.

Czy A * jest odpowiednie dla tego przypadku użycia?

algorithm path-finding maps David Chouinard
źródło

Odpowiedzi:

19

Należy użyć algorytmu D * , który został zaprojektowany dla tego właśnie scenariusza. W szczególności implementacja D * Lite jest najbardziej wydajnym i prostym wariantem.

jmegaffin
źródło
2
Bardzo istotne . Zrozumienie D * -lite jest proste, gdy zrozumiesz LPA * (opiera się na algorytmie D * -lite) , ale sam LPA * jest dość złożony. Więc jeśli planujesz faktycznie wdrożyć D * -lite, zacznij od opracowania na LPA * (zakładając, że już rozumiesz A *, to znaczy)
BlueRaja - Danny Pflughoeft
3

Wiele implementacji sztucznej inteligencji w tej sytuacji decyduje się oszukiwać i zapewnia sobie pełną wiedzę na temat mapy, na której ich przeciwnik nie ma. Następnie możesz po prostu zastosować A * do pełnej mapy.

To, jak rozsądne będzie to wyglądanie jednostek sterowanych komputerowo, będzie zależeć od takich rzeczy, jak labirynt, taki jak mapy, oraz od tego, czy gracz prawdopodobnie nauczy się układów map z czasem.

Jeśli dotyczy to jednostek kontrolowanych przez gracza, możesz również uniemożliwić graczowi wybranie miejsca docelowego, którego jeszcze nie zbadali, aby zmusić je do ręcznej eksploracji.

Adam
źródło
2
Dobre sugestie, nieodpowiednie dla mojego przypadku użycia, ale mogą być przydatne dla innych. (Rozwijam sztuczną inteligencję do współzawodnictwa w symulacji gry)
David Chouinard,
istnieją również gry wykorzystujące implementację wyszukiwania ścieżek, które zakładają, że niezbadane obszary są krzyżowalne, podczas gdy obszary wcześniej odwiedzone nie miały żadnych zmian w krzyżowalności od ostatniej wizyty (tj. nie wiedziałby, że ściana mogła zostać zniszczona lub zbudowana, dopóki nie odwiedzi obszaru jeszcze raz).
Lie Ryan,