Pracuję nad znalezieniem ścieżki do gry RTS, w której buduję siatkę nawigacyjną z siatki gry.Najszybszy algorytm triangulacji z dziurami?
Napisałem algorytm podobny do Marszowych Kwadratów, który tworzy i upraszcza granice między obszarami mapy, które można chodzić i nimi nie łączyć. Teraz mam "siatkę" składającą się tylko z krawędzi. Muszę triangulować tę siatkę, aby ostateczna triangulacja zawierała początkowe krawędzie, a następnie mogę usunąć nieodtwarzalne regiony, aby utworzyć otwory w siatce nawigacyjnej. Na przykład, muszę to zrobić ...
Trójkąty reprezentują regiony na chodzenie po mapie. Otwory stanowią nieodłączne regiony, takie jak góry lub budynki. Siatkę można uznać za 2D, ponieważ wysokość jest nieistotna. Jest to oczywiście bardzo uproszczony przypadek. Siatka nawigacyjna w grze będzie składać się z tysięcy wierzchołków i wielu dziur, ale mogę ją podzielić na mniejsze fragmenty w celu dynamicznej aktualizacji.
Przyjrzałem się ograniczonym algorytmom Triangulacji Delaunay, które najpierw tworzą triangulację delaunay punktów, a następnie usuwają trójkąty, które przecinają ograniczone krawędzie, a następnie ponownie triangulują usunięte trójkąty.
Wydaje się to trochę zbędne dla moich celów. Moja siatka nie musi być Delaunay i składa się całkowicie z ograniczonych krawędzi, więc jeśli to możliwe, chciałbym pominąć wykonywanie dodatkowych triangulacji. Czy istnieje lepszy algorytm do tego? Szukałem i patrzyłem, i byłem w stanie znaleźć tylko ograniczone algorytmy Delaunaya. A może się mylę, a najlepszy algorytm Delaunaya byłby najlepszy?
Zrobiłem nawigację po ścieżce siatki od początku, ale nigdy nie musiałem generować siatki nawigacyjnej. Algorytmy triangulacji są dla mnie nowością. Jakiś wgląd?
Ponieważ nie masz specjalnych żądań dotyczących trójkątów, prostsze podejście, takie jak [triangulacja wielokąta] (http://en.wikipedia.org/wiki/Polygon_triangulation) jest lepszym rozwiązaniem niż Delaunay. – Ante
Spojrzałem na metodę Ear-Clipping, która wydaje się nieco wolniejsza niż triangulacja Delaunaya, ale wymagałaby ode mnie sortowania moich wierzchołków w pętli zamówień, prawda? –
Teraz zdaję sobie sprawę, że masz tylko krawędzie. W każdym przypadku będziesz musiał połączyć i zorientować krawędzie, znaleźć część, która znajduje się wewnątrz innej części (wiedzieć, czy jest to dziura, czy nie), a następnie triangulować wielokąt z dziurami. Otwory można usunąć, dodając 2 takie same krawędzie z otworu do granicy wielokąta lub innego otworu. Obcinanie uszu jest prostą metodą iz partycjonowaniem przestrzeni (drzewo BSP, drzewo quadowe, ...) jest szybsze niż O (n^2). – Ante