Jak mogę wygenerować siatkę nawigacji 2d w środowisku dynamicznym w czasie wykonywania?

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.

siatka nawigacyjna

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.

— Stephen
źródło

Dynamiczne partycjonowanie, które próbujesz wdrożyć, będzie zależeć od specyfiki elementów mapy. Czy elementy przeszkód składają się w całości z prostokątów wyrównanych do siatki, jak pokazano w przykładzie? Obrócone prostokąty? Nieregularne wielokąty? A może kształty inne niż wielokąt z dużą ilością zakrętów? Czy masz dane punktowe / poli dla kształtu przeszkód? Jeśli tak, to czy dane dotyczące kształtu w kategoriach trójkątów, prostokątów, wyłącznie wielokątów wypukłych lub mieszanki wielokątów wypukłych i wklęsłych?

— Matthew R

@Matthew Mój świat składa się z wypukłych przeszkód wielokątnych, bez zakrętów i wklęsłych wielokątów. Każda przeszkoda jest przechowywana jako obiekt wielokąta z wierzchołkami reprezentowanymi przez obiekty wektorowe.

— Stephen

Jeśli chodzi o to, co warto, pracuję nad rozwiązaniem opartym na tym dokumencie: gradworks.umi.com/3493710.pdf Jeśli mi się powiedzie, opublikuję swoje rozwiązanie.

— Stephen

siatka nawigacyjna nie istnieje, aby w 100% powiedzieć, czy możesz gdzieś iść, czy nie, to tylko podstawowy zarys obszarów, na których można chodzić pieszo, nadal musisz sprawdzać kolizje z obiektami dynamicznymi, edytuj:

— właściwie

@ Stephen - Patrz odpowiedź na długi komentarz .

— Matthew R

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.

— Matthew R.
źródło

Świetna odpowiedź, @Mathew. I zdecydowanie powinieneś przeczytać ten artykuł! Jest łatwy do naśladowania i wyjaśnia świetną technikę (zwłaszcza Dodatek A, który mówi o wykrywaniu / generowaniu siatki przez agenta). Koduję wersję tego algorytmu dla javascript i idzie dobrze. Kiedy to zrobię, opublikuję to jako odpowiedź.

— Stephen

@Stephen chciałbym zobaczyć tę pracę

— kevzettler

@Stephen Szukam też wersji javascript

— Apolo,

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.

— Sean Middleditch
źródło

Muszę wyjaśnić dalej: moja gra nie jest wyrównana do siatki. Budowałem siatkę w obszarze 800 x 600 pikseli, każdy piksel stanowił jedno miejsce na siatce (wciąż zastanawiałem się nad A *, więc nie myślałem o wydajności tego). Mam przeszkody, które nie są tak proste jak te z powyższego przykładowego obrazu, próbowałem tylko zilustrować problem. Oczywiście takie pole gry wymagało rewizji, a po kilku badaniach uważam, że siatka nawigacyjna byłaby właściwą drogą.

— Stephen

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.

— Ray Dey
źródło