Więc nauczyłem się, jak używać A * do wyszukiwania ścieżek i jestem w stanie używać go na siatce. Jednak mój świat gry jest ogromny i mam wielu wrogów zbliżających się do gracza, który jest ruchomym celem, więc system siatki jest zbyt wolny, aby znaleźć ścieżkę. Muszę uprościć wykres węzłów za pomocą siatki nawigacyjnej.
Rozumiem pojęcie „jak” działa siatka (znajdowanie ścieżki przez węzły na wierzchołkach i / lub środkach krawędzi wielokątów).
Moja gra wykorzystuje dynamiczne przeszkody, które są generowane proceduralnie w czasie wykonywania.
Nie mogę całkowicie owinąć głowy, jak wziąć samolot, który ma wiele przeszkód i programowo podzielić obszar, na którym można chodzić, na wielokąty dla siatki nawigacyjnej, jak na poniższym obrazku.
Gdzie zaczynam? Skąd mam wiedzieć, kiedy segment obszaru, na którym można chodzić, jest już zdefiniowany lub, co gorsza, kiedy zdaję sobie sprawę, że muszę podzielić wcześniej zdefiniowany obszar na spacery, gdy algorytm „przechodzi” przez mapę?
Używam javascript w nodejs, jeśli to ma znaczenie.
źródło
Odpowiedzi:
@Stephen - Długi komentarz - Ten artykuł wygląda, że warto go przeczytać, gdy mam trochę czasu. Zasadniczo sugerowałbym coś podobnego do algorytmu Hertela-Mehlhorna, o którym mowa w artykule (odniesienie do tego konkretnego algorytmu można znaleźć tutaj http://www.bringyou.to/compgeom/ ) z dodatkiem dzielenia boków mapy (poza granicą obszaru gry) pewną ilość czasu, aby zmniejszyć występowanie wielu małych trójkątów utworzonych w narożnikach. Te małe trójkąty mogą być problematyczne, ponieważ mogą być mniejsze niż to, co robisz, szukając ścieżki. Hertel-Mehlhorn służy do redukcji wielokątów wytwarzanych przez trójkątne partycjonowanie, jeśli interesuje Cię tutaj więcej na temat triangulacji:http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/PolyPart/polyPartition.htm .
Ponadto, jeśli wolisz nie wymyślać koła na nowo, myślę, że ta biblioteka zrobi wszystko, czego potrzebujesz: http://code.google.com/p/polypartition/ . Wykonuje triangulacje i redukcje za pomocą jednej z wielu różnych opcji, w tym Hertel-Mehlhorn. Jest to licencja MIT, co oznacza, że może być używana do projektów zamkniętych i komercyjnych, jeśli jest to problem.
Jeśli zdecydujesz się kontynuować pracę nad własną implementacją, chciałbym zobaczyć, co wymyślisz.
źródło
Zamiast siatki możesz rozważyć hierarchiczne podejście A *. Największą zaletą siatki jest radzenie sobie ze światami gry, które nie są wyrównane względem siatki, niż zmniejszanie złożoności siatki.
Dzięki podejściu hierarchicznemu wielokrotnie dzielisz swój świat (podobnie jak drzewo quadów) i generujesz informacje o łączności między węzłami. Następnie możesz szybko wygenerować ścieżkę między dużymi fragmentami świata i użyć siatki o wysokiej rozdzielczości tylko do znalezienia ścieżki w większej części.
Podejście hierarchiczne zapewni lepszą wydajność rzędów wielkości, podczas gdy siatka w najlepszym razie zapewni jedynie niewielką liniową poprawę.
Naiwnym podejściem jest po prostu podzielenie świata na X przez X większych fragmentów ułożonych w siatkę, wygenerowanie informacji o łączności między nimi (np. Czy istnieje ścieżka między fragmentem 2x1 od 3x1 do 2x2 i jaka jest odległość średniej ścieżki) .
Pamiętaj, że w niektórych przypadkach nie zawsze można uzyskać idealne ścieżki dzięki takiemu podejściu. Generowanie warstw kawałków o zmiennej wielkości łagodzi problem, ale szczerze mówiąc, zwykle jest to po prostu o wiele łatwiejsze, aby uniknąć zawsze tworzących się marek z problematycznymi ścieżkami i polegać na tym, że gracz jest bardzo mało prawdopodobne, aby zauważyć wrogów, którzy podążają ścieżkami nieoptymalnymi, z wyjątkiem najbardziej zdegenerowane przypadki.
źródło
Myślę, że komplikujesz to. Prawdopodobnie nie musisz generować siatek nawigacyjnych w locie. Zamiast tego użyj statycznej siatki nawigacyjnej dla swojego podstawowego świata.
Ścieżkę wokół przeszkód można rozwiązać za pomocą zachowań kierowniczych (unikaj przeszkód). Jeśli przy przypadkowej przeszkodzie twoja przeszkoda jest tak duża, że wypełnia lub całkowicie blokuje podróż od jednego nav-poly do drugiego, to możesz w jakiś sposób sprawdzić ten przypadek krawędzi i ponownie obliczyć ścieżkę między polem, w którym się obecnie znajdujesz, a jeden, przed którym jesteś zablokowany.
źródło