Jak działa wyszukiwanie ścieżki Nawigacji?

Chcę zrozumieć, jak działają navmeshes, jak je wdrożyć i dlaczego jest lepszy niż inne rodzaje systemów ścieżek.

algorithm path-finding

— Ogień
źródło

To pojawiło się podczas moich porannych wędrówek internetowych: aigamedev.com/open/reviews/alienswarm-node-graph Może warto przeczytać :-)

— programista

Ten samouczek może być przydatny dla użytkowników Unity, którzy natkną się na ten post: binpress.com/tutorial/unity3d-ai-navmesh-navigation/119

— MichaelHouse

Odpowiedzi:

Jest to to samo, co odnajdywanie waypointów, tyle że zamiast waypointów masz wielokąty way i możesz wywnioskować z niego kilka rzeczy na temat navimesh:

wielokąty orientacyjne to obszary, w których istoty mogą bezpiecznie chodzić
- inne obszary prawdopodobnie nie powinny być brane pod uwagę
- punkty drogi muszą zrobić skok wiary w przestrzeń między nimi; pamiętasz NPC-ów tkwiących w ścianach? Było to w miejscach, w których dwa punkty pośrednie nie były bezpośrednio połączone.
Istnieje potencjalnie mniej węzłów (ponieważ wielokąty są większe)
- Dlatego najprawdopodobniej jest szybszy
- Dlatego ma potencjalnie mniejsze wymagania dotyczące pamięci
Jest bardziej realistyczny (ponieważ obszar wielokąta zawiera teoretycznie nieskończoną liczbę punktów)
- W wielokątach Możesz zachowywać się jak flokowanie, aby uniknąć kolizji między postaciami niezależnymi

— użytkownik712092
źródło

Zasadniczo są one używane z pewnego rodzaju ulepszonym algorytmem A * (bierze pod uwagę łącza przeskakujące lub przelotowe w celu znalezienia ścieżki 3D). W ten sposób nie jest to tak naprawdę inny system niż cokolwiek innego, jest to raczej sposób na wygenerowanie normalnej sieci wyszukiwania ścieżek bezpośrednio z wysoko-poli (dobrze mówiąc) środowiska lub terenu. Z jakiegokolwiek powodu nazywamy je tutaj beaconami, ale idea jest taka sama, pewien rodzaj zautomatyzowanego procesu działa na każdej mapie i tworzy prosty zestaw połączeń, które mogą mieć A * uruchomione na nich w rozsądnych ramach czasowych. Jeśli spróbujesz znaleźć ścieżkę względem surowych danych bazowych, będzie to zbyt wolne dla gry ze względu na gęstość siatki.

— koderanger
źródło

Czy to nie jest wykres punktu, z wyjątkiem tego, że wykonano go na uproszczonej siatce? Myślałem, że navmeshes pozwalają na tworzenie ścieżek na wielokącie.

— Ogień

Uproszczony wykres umożliwia wykonywanie ścieżek na duże odległości, krótki zasięg jest zwykle obsługiwany w inny sposób. Wygląda na to, że system Valve używa danych siatki dla obu, tylko na różne sposoby (routing supernode vs. ograniczenia lokalne).

— coderanger

Prosty zestaw połączeń nie jest navmesh, prawda? Myślałem, że nazywa się to navmesh, ponieważ nakładasz ścieżki na wielokąty.

— Ogień

Nie sądzę, aby nawigacja lokalna czy globalna była tutaj istotna.

— Ogień

Zestaw sąsiadujących wielokątów jest nadal wykresem, podobnie jak ustawione punkty, i możesz wykonać na nim A * w ten sam sposób. Jedyną różnicą jest to, że kiedy już wiesz, przez które wielokąty zamierzasz się poruszać, rysujesz linie inaczej.

— coderanger

Można to zrobić na wiele sposobów. A * i takie jest dobrą opcją, ale brakuje w niej dokumentacji. Możesz zrobić coś takiego jak rozmieszczenie węzłów quasi-losowo wokół mapy i sprawdzić, które węzły się widzą i zbudować małą sieć węzłów. Nie najbardziej optymalny, ale łatwy do zrozumienia.