Jak działa wyszukiwanie ścieżki Nawigacji?

27

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:

6

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)
użytkownik712092
źródło
2

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ń
1
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
0

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.


źródło