Robię Tower Defense i potrzebuję do tego dobrego algorytmu ścieżki.
Myślałem o Dijkstrze, ale potrzebuję takiego, który może być dynamiczny; musi być w stanie aktualizować się, gdy jedna krawędź zostanie usunięta lub dodana bez pełnego ponownego obliczenia.
Koduję w C #, jeśli to pomaga.
Odpowiedzi:
Zazwyczaj będziesz chciał użyć A *, chyba że szukasz czegoś istotnie innego.
Musiałem rozwiązać podobny problem: znalezienie ścieżki na dużej siatce przypominającej labirynt ze stale zmieniającymi się „kosztami” i barierami.
Chodzi o to, że w grze typu tower defense liczba podmiotów, które muszą mieć dla nich rozwiązaną ścieżkę, jest zwykle znacznie większa niż liczba węzłów na wykresie. * Nie jest najodpowiedniejszym algorytmem do obsługi tego, ponieważ będziesz musiał go rozwiązać od nowa za każdym razem, gdy coś zostanie zmienione. Dobrze jest, jeśli chcesz znaleźć tylko jedną ścieżkę, ale w moim przypadku musiałem być w stanie obsłużyć byty, które mogą pojawiać się w różnych lokalizacjach, a każda z nich ma swoją własną ścieżkę.
Floyd-Warshall algorytm jest bardziej właściwe, choć na moim przypadku Napisałem algorytm niestandardowy że gdy zmiany węzłowe, to ponownie oblicza koszt dla tego węzła z wszystkimi sąsiadami, a następnie , jeśli sąsiedzi zostały zmienione to jest wywoływany rekurencyjnie na nich.
Tak więc na początku gry odpalam ten algorytm na wszystkich moich węzłach „celowych”. Następnie, za każdym razem, gdy zmienia się pojedynczy węzeł (na przykład staje się nie do przejścia), po prostu odpalam go w tym węźle, a zmiana jest propagowana do wszystkich węzłów, które zostaną zmienione, a następnie zatrzymana. Nie ma więc potrzeby globalnego ponownego obliczania, a algorytm jest całkowicie niezależny od liczby jednostek, które będą wymagać szukania ścieżki.
Mój algorytm był w zasadzie czymś w rodzaju (pseudo-kod):
update_node method in Node class:
$old <- $my_score
find $neighbor node among all neighbors such that
$neighbor.score + distance_to($neighbor) is minimal
$my_score <- $neighbor.score + distance_to($neighbor)
$next_node <- $neighbor
if ($my_score != $old)
for each $neighbor
$neighbor.update_node()Z początkowym wynikiem zależy od tego, czy węzeł jest celem, czy jakąś barierą.
Algorytm trasy, którego użyłem na moim niszczycielu czołgów, był cofnięty od normalnej ścieżki A * ze względu na liczbę jednostek, które miałem w grze. Zamiast kierować się od bramki do złych facetów, kierowałem od bramki do każdego pustego pola na planszy.
Nie trwa to długo, po prostu iterujesz planszę, dopóki nie znajdziesz swoich „kosztów”, i zapewnia dobrą informację zwrotną dla zablokowanych tras (jeśli je wykonujesz). Korzystanie z algorytmu Floyda jest szybkie i przyjazne dla pamięci podręcznej w porównaniu do A *, ponieważ nie wykonuje wyszukiwania zależnego od danych, po prostu ładuje i działa na danych w strumieniach.
Najpierw ustaw planszę na nieskończony koszt, następnie ustaw cel docelowy na zero, a następnie iteruj po planszy, aby sprawdzić, czy sąsiednia komórka kosztuje mniej niż aktualny koszt plus koszt podróży. Koszt podróży to miejsce, w którym umieszczasz swoją heurystykę (w moim przypadku koszt podróży po przekątnej był nieskończony, ale koszt podróży przez wieżę był wysoki, więc mogli jeść przez wieże, ale nie zrobili tego, chyba że nie mieli wybór)
Gdy już masz siatkę kosztów, możesz szybko zbudować siatkę „przepływową”, testując najbardziej stromy gradient kosztów na komórkach. Działa to naprawdę dobrze w przypadku ogromnej liczby złych facetów, ponieważ żaden z nich nigdy nie musi szukać ścieżki, po prostu podążają za wirtualnymi drogowskazami.
Kolejną zaletą jest to, że w ten sposób musisz wykonywać to zadanie za każdym razem, gdy dostosowujesz przeszkody (lub w mojej grze, gdy pełzanie zjada jedną z twoich wież). Nie za każdym razem, gdy pełzacz / mob wkracza na boisko (co przy tysiącach mobów i dziesiątkach na sekundę byłoby dość kłopotem).
Wyszukiwanie ścieżek jest szybkie i na czymś takim, jak w normalnej grze w obronę wieży, nie będziesz miał problemów z uruchomieniem pełnego podania A * lub Dijkstra, gdy coś się zmieni. Rozmawiamy dobrze w czasie krótszym niż milisekunda, aby uzyskać pełne odświeżenie. Wszelkie adaptacyjne wyszukiwanie ścieżek kończy się przerażająco skomplikowane. Po prostu zrób to w prosty sposób, chyba że tworzysz największą na świecie siatkę obrony wieży.
Jak działa wyszukiwanie ścieżek A *? może być dobrym miejscem do rozpoczęcia :-)
Może to być przesada dla twojego rozwiązania, ale pomyśl o routingu do tyłu zamiast do przodu.
W grze TD wrogowie zazwyczaj starają się dotrzeć do określonego celu. Kieruj się wstecz od tego celu do pierwszego wroga, a następnie buforuj tę ścieżkę. Podczas generowania ścieżki dla kolejnych wrogów użyj pierwszej ścieżki jako punktu początkowego i tak dalej. Jeśli masz wiele punktów wejścia wroga lub wiele celów, możesz zacząć od wielu wstępnie zbuforowanych ścieżek.
Odnajdywanie ścieżek waypointów byłoby prawdopodobnie najlepsze dla gry td, ponieważ ogólnie na podstawie poziomu ai podąża bezpośrednią ścieżką. Zasadniczo ustawiasz swoje węzły lub punkty drogi, a następnie masz punkt „ai” w kierunku trasy i podchodzisz do niego, gdy tylko zbliży się wystarczająco, aby przejść do następnego punktu drogi, skieruj go twarzą do niego i przejdź do niego.
Ponieważ ktoś zapytał, zwracasz się do dynamicznie zmieniających się środowisk, ponownie obliczając ścieżkę za każdym razem, gdy gracz umieszcza lub usuwa wieżę, i po prostu przechowujesz tę ścieżkę w pamięci w międzyczasie. Środowisko nie zmienia się w każdej klatce.
Pamiętaj, że niektóre gry TD mają ustaloną ścieżkę i nie pozwalają na umieszczanie na niej wież, więc rozwiązują łatwe znajdowanie ścieżek: wpisując ścieżkę na stałe i nie pozwalając jej zablokować :)
Prostym rozwiązaniem jest oszukiwanie.
Zaprojektuj mapę wcześniej, aby upewnić się, że nie ma ślepych uliczek. Następnie na każdym skrzyżowaniu dodaj wyzwalacz, który sprawia, że postać wybiera trasę (przykład: zawsze skręć w lewo, zawsze skręć w prawo lub losowo).