Jak mogę wygenerować siatkę nawigacji dla siatki kafelków?

18

Właściwie to jeszcze nie zacząłem programować dla tego, ale chciałem zobaczyć, jak bym to zrobił.

Powiedzmy, że mam siatkę płytek, wszystkie tego samego rozmiaru, niektóre przechodzące, a niektóre nie. Jak miałbym zacząć tworzyć siatkę nawigacyjną wielokątów z tej siatki?

Moim pomysłem było wyciągnięcie nieobrotowych płytek i przedłużenie linii stamtąd krawędzi, aby stworzyć wielokąty ... to wszystko, co do tej pory mam. Jakakolwiek rada?

2d mathematics algorithm navmesh Ross Hays
źródło
2
Technicznie siatka jest prawie odpowiednikiem siatki nawigacyjnej. Podejrzewam, że faktycznie pytasz o sposób optymalizacji siatki i zlewania sąsiadujących ze sobą kwadratów.
Kylotan
@Kylotan Tak, dokładnie to miałem na myśli, po prostu sposób na połączenie sąsiednich wielokątów.
Ross Hays,

Odpowiedzi:

28

Oto jedna z metod, które wymyśliłem, robiąc navmesh dla gry RTS. Pamiętaj, że jest to homebrew, nie użyto żadnych narzędzi innych firm, wdrożenie i poprawka zajęło mi około 3 tygodni:

  1. Użyj algorytmu Marching Squares , aby przekształcić płytki przeszkód w kontury . Pamiętaj, że krawędzie mapy są również konturem i również muszą zostać uwzględnione.
  2. Zmniejsz liczbę punktów na konturach za pomocą algorytmu Douglasa-Peuckera (fioletowe linie na dolnym obrazku)
  3. Wprowadź wszystkie punkty do triangulacji Delaunaya (aby uzyskać najbardziej jednolite trójkąty)
  4. Dodaj dodatkowe punkty w pustych obszarach i wzdłuż krawędzi mapy (aby uzyskać bardziej równomierny navmesh)
  5. Sprawdź wzdłuż konturów przeszkód i odwróć wielokąty produkowane przez Delaunay, aby dopasować kontury. - Często Delaunay może umieszczać trójkąty (szare), które nie pasują do twoich konturów (czerwone), a następnie musisz je wykryć i przerzucić. Łącząc je z powrotem w wielokąt, podziel go wzdłuż konturów i ręcznie trianguluj wprowadź opis zdjęcia tutaj
  6. Przycinaj wewnętrzne przeszkody - usuwaj wielokąty znajdujące się w przeszkodach (różowy na powyższym obrazku)
  7. Uzupełnij dane dotyczące łączności między pozostałymi trójkątami i wierzchołkami, ile potrzebujesz - to twój navmesh.

Wynik:

tilemap navmesh

Kromster mówi, że popiera Monikę
źródło
1

Siatki są zwykle implementowane jako wykresy. Jeśli chcesz zaimplementować wyszukiwanie ścieżek na mapie opartej na siatce, wykonaj następujące czynności:

Utwórz wykres, w którym każdy kwadrat jest reprezentowany jako wierzchołek. Każda para sąsiednich kwadratów, które można przechodzić, reprezentowanych jako wierzchołki, będzie miała krawędź między nimi. I jesteś skończony.

wolfdawn
źródło
1
Nie tak zazwyczaj stosuje się navmeshes. Celem navmesh (i, jak sądzę, powodem, dla którego pytający nawet zadał tutaj swoje pytanie), jest optymalizacja wykresu do minimalnej wymaganej liczby wielokątów (zwykle trójkątów), które obejmują najbardziej przydatne spacje, aby zmniejszyć zarówno liczbę kroki niezbędne do znalezienia dobrej ścieżki oraz ślad pamięci wymagany do zdefiniowania siatki. Surowa implementacja pochłonie o wiele więcej pamięci i zmarnuje cenny czas przetwarzania AI.
Gurgadurgen,
Masz rację. Oczywiście dziesiątkowanie (redukcja wielokątów) jest rozsądną i pożądaną optymalizacją. Po prostu, kiedy czytasz pytanie op, masz wrażenie, że on chce po prostu przekształcić siatkę w wykres.
wolfdawn