Skuteczne wyszukiwanie ścieżek w wolnej przestrzeni


12

Mam grę w przestrzeni kosmicznej i chciałbym wydawać rozkazy ruchu, które wymagają szukania ścieżki. Rozumiem teraz, że A * i tym podobne dotyczą głównie drzew, a nie pustej przestrzeni, która nie ma węzłów szukających ścieżki. Mam pewne przeszkody, które obecnie są wyrażone jako stałe AABB - to znaczy, że nie ma nieograniczonej przeszkody „terenowej”. Ponadto oczekuję, że większość przeszkód będzie dość zbliżona do siebie w postaci kostek lub kulek.

Zastanawiałem się więc nad zastosowaniem znacznie prostszego algorytmu wyszukiwania ścieżki - po prostu rzuć promień z aktualnej pozycji do pozycji docelowej, a następnie mogę stosunkowo szybko uzyskać listę przeszkód przy użyciu podziału przestrzennego. Nie jestem pewien, jak ustalić, w której części zamówiona jednostka manewruje wokół przeszkód.

Do tej pory myślałem, że po prostu użyję potencjalnych pól - to znaczy, wszystkie jednostki odczują silną siłę odpychającą od siebie i umiarkowaną siłę w kierunku pożądanego punktu. Ma to również tę zaletę, że do wydawania zamówień grupowych mogę po prostu zamówić siłę średniego poziomu w stosunku do innego bytu. Ale to oczywiście nie osiągnie optymalnego rozwiązania.

Czy potencjalne pola osiągną rozsądne przybliżenie, biorąc pod uwagę moje parametry, czy też potrzebuję innego rozwiązania?

Odpowiedzi:


7

Chociaż potencjalne pola mogą działać, wyobrażam sobie, że będziesz mieć problemy z nieoptymalnymi ścieżkami i „lokalnymi minimum”, w których twoje jednostki zostaną uwięzione przez otaczające przeszkody. Znak * jest odpowiedni dla środowisk otwartej przestrzeni 3D. Staje się to po prostu problemem z generowaniem siatki nawigacyjnej, która odpowiada Twoim potrzebom. Możesz nawet używać struktur takich jak Octrees dla węzłów nawigacyjnych. Im mniejszy maksymalny rozmiar każdej oktany, tym gładsza ścieżka. Sprawdź ten artykuł z gier twarzą w twarz (teraz nieczynny, dodano link powrotny). A * w połączeniu z optymalizacją ścieżki (jak skróty linii wzroku) i zachowaniami kierowania, a będziesz gotowy! Zobacz obraz poniżej jako przykład użycia oktetu dla węzłów ścieżki:


Jak to się skaluje do większych map? Gdybym miał mapę, która była dwa razy większa w każdym wymiarze, potrzebowałbym ośmiokrotnie większej liczby węzłów, co byłoby problematyczne.
DeadMG

Niekoniecznie. Możesz zachować duży rozmiar węzła, dopóki wyszukiwanie nie zbliży się do niego. Pozwala to zachować węzły, które nie są zainteresowane, raczej duże i nieliczne.
MichaelHouse

Ładną właściwością pustych siatek nawigacji kosmicznej jest równość kosztów podróży; możesz być w stanie użyć A * JPS
Czy

@Will: Zrobiłem trochę googlingu, ale tak naprawdę nie zrozumiałem jedynego algorytmu znajdowania ścieżek, który się pojawił. Chcesz opublikować odpowiedź?
DeadMG

@DeadMG jest to definitywne wyjaśnienie: harablog.wordpress.com/2011/09/07/jump-point-search <br/> Jeśli możesz wdrożyć A *, możesz później dość prosto zmodernizować JPS. Najpierw wykonaj A * i dodaj JPS jako optymalizację.
Czy
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.