Jak wygenerować siatkę nawigacji dla świata 3D?

Próbuję znaleźć rozwiązanie tego problemu. Próbuję zbudować siatkę nawigacyjną w formacie siatki wierzchołków zablokowanych na x, y ułożyłem współrzędne w kształcie kwadratów dla przestrzeni 3D. Ale mam problemy z próbowaniem rozwiązania tego problemu.

Próbowałem zajrzeć do biblioteki Recast. Jest to dość solidna metoda, ale najwyraźniej zwalnia przy większych mapach i otwartej przestrzeni. Nie wiem też, w jaki sposób generują wierzchołki i krawędzie przestrzeni świata za pomocą mapy wysokości.

Moją kolejną myślą było zrobienie tego, co robił Unreal Engine 3.

https://udn.epicgames.com/Three/NavigationMeshReference.html

Który miał użyć raycastów do wygenerowania siatki. Nie mogłem wymyślić, jak zatrzymać rodzynki.

Więc ... moją następną opcją było pudełko, być może obsada pudełka. Utwórz podzielony wolumin o wielkości, która jest potęgą 2. Wyrównaj skrzynkę z siatką i wystrzel prostokątne pryzmaty w dół jak promień. Jeśli wyląduje na kawałku geometrii, który jest częścią ziemi, a prostokąt nie zostanie przecięty, pozostaw tam kwadrat. I idź w dół, dopóki nie zostaną osiągnięte granice głośności. Aby sprawdzić, czy krawędzie muszą być połączone, przypuszczam, że mógłbym sprawdzić, czy nachylenie między dwiema parami wierzchołków mieści się w nachyleniu, na którym można chodzić, łącz je, jeśli to prawda.

Moje główne problemy to ... to nie wydaje się zbyt optymalne. Nie zastanawiając się nad tym, przy szacowaniu procesem jest O (N ^ 3) dla poziomu wielowarstwowego. Co może stać się dość paskudne.

Ostatni bit dotyczy automatycznego tworzenia prostokątnych grup tych kwadratów. Nie jestem do końca pewien, jak to zrobić. Implementacja Unreal rozdziela je według nachyleń. Staram się jednak zachować format siatki. To nie jest całkowicie konieczne. Nadal występują problemy z tworzeniem dużych prostokątnych płytek w celu podzielenia procesu wyszukiwania ścieżki na podstawie poszczególnych płytek. Płytki nie mogą być ani za duże, ani za małe.

Więc pytania są ...

Jaki byłby skuteczny sposób na wygenerowanie tego przepasanego navmesh? A jaki byłby dobry sposób na tworzenie kafelków?

Podstawowy świat 3D może być reprezentowany przez siatkę nawigacyjną, którą można wygodnie wbudować w większość silników gier. Aktor może podróżować wzdłuż krawędzi wielokątów.

To byłoby proste rozwiązanie. Istnieje wiele algorytmów do wyszukiwania ścieżek i generowania navmesh.

Chciałbym się podzielić czymś, co czytałem jakiś czas temu.

To opisuje możliwe rozwiązanie, w którym możemy rozbić nasz świat gry na kwadratowe płytki. za każdym razem, gdy do gry dodaje się kwadratową płytkę (gdy gracz zbliża się do obszaru / terenu proceduralnego), dodaje się kwadratową płytkę. Jednak nie musimy już obliczać całego navmesh. po prostu obliczamy go dla tego kafelka i dodajemy do istniejącego wykresu. Znaczący wzrost wydajności tam.

Kolejnym rozwiązanym problemem jest postrzępiony ruch z poprzedniego przykładu. Rozumiem, że rozważenie przyszłych zakrętów i uogólnienie kierunku znacznie zmniejszy ruch zygzakowaty i sprawi, że ruch będzie płynny. Gry ze szczegółową animacją tego nie zdradzają, ale można to zauważyć w niektórych grach z otwartym światem, w których przypuszczam, że nawigacja jest w większości upieczona.

Jeśli chodzi o pytanie, polecam sprawdzić odpowiedź Kromstera na liście algorytmów generujących navmesh .

Zobacz także AI Systems of Left 4 Dead, których przykłady są częścią. Omówiono wiele innych interesujących tematów

Powodzenia.

istnieje wiele sposobów, dlaczego nie po prostu ustawić go lokalnie dla gracza, zrobić małą siatkę, która podąża za odtwarzaczem i sprawdzić pod każdym skrzyżowaniem, czy jest on poprzeczny, czy jest tam podłoga, czy wykonać rzut promieniami, aby sprawdzić, czy jest ściana / budynek z dowolnej nadchodzącej strony ..

Jest to problem, który widziałem wszędzie. Sztuką jest „rozdzielenie obaw”. „Powiedz co?”, Słyszałem, jak myślisz. To, co jest wyświetlane na ekranie, NIE jest tym, czym jest „struktura danych”. Ważne jest oddzielenie elementów wizualnych od danych w celu stworzenia elementów wizualnych. Dzięki temu gra będzie zawsze „przyszłościowa”, gdy zostaną wydane nowe wersje oprogramowania.

Zbuduj strukturę danych (aka: model), która będzie reprezentować Twój świat gier. Następnie skonstruuj „widok” modelu struktury danych. Jeśli chcesz zmienić świat z siatki szachownicy na siatkę heksagonalną, struktura danych (model) pozostaje taka sama, ale wyświetlacz „pomaluje” (renderuje) inny widok.

Zrób podwójną tablicę. A jeśli obiekt / obiekty są nie do przejścia, zastosuj metodę, która poinformuje tablicę, że pozycja jest nie do przejścia. Kiedy AI próbuje się poruszyć, spojrzą na podwójną tablicę i sprawdzą, czy jest ona przejezdna.