odnajdywanie przeszkód w grze podobnej do Warcraft 3

Rozważ wyszukiwanie A * na mapie opartej na kafelkach. Prosty kod brzmiałby: jeśli w tej komórce znajduje się jednostka, to jest ona nieosiągalna, to jest w porządku.

Ale jest problem z rozdzielczością mapy. Kiedy patrzę na Warcraft 3, tam potwory i struktury mają różny promień i możesz podejść bardzo blisko, co jest bardziej oparte na wektorze, jak to zostało zaimplementowane?

Jakie jest standardowe rozwiązanie obejmujące wykrywanie kolizji ruchomych przeszkód z algorytmem znajdowania ścieżki, takim jak Warcraft 3?

Nie mogę powiedzieć na pewno, jakie podejście zastosowali programiści WC3, ale wygląda to prawie jak Hierarchical Annotated A *. Promień jednostki zdefiniowany w WC3Editor został użyty jako-jest do skalowania modelu 3d, ale rzeczywisty rozmiar jednostki dla szukania ścieżki był dyskretny, być może coś w rodzaju unitSize = (int) (unitRadius / 10). To na pewno nie było oparte na wektorze.

Powiedzmy, że istnieje wiele węzłów ścieżki tworzących siatkę węzłów o wysokiej rozdzielczości. Prosta jednostka jak ghul ma rozmiar 2, więc aby umieścić ją gdzieś w siatce, potrzebujemy 4 wolnych węzłów ścieżki w pobliżu siebie. Rycerz śmierci jest nieco większy i ma rozmiar 3, biorąc łącznie 9 węzłów ścieżki. Teraz umieszczamy 2 zigguraty razem, pozostawiając między nimi przestrzeń o szerokości 2 węzłów i wysyłamy ghula i rycerza śmierci po drugiej stronie. Ghul będzie mógł przejść między dwoma zigguratami, a rycerz śmierci będzie musiał się poruszać. Jak można to ustalić?

Aby sprawdzić, czy węzeł może pomieścić jednostkę o określonym rozmiarze, przypiszmy do każdego węzła specjalną wartość luzu określającą maksymalny dozwolony rozmiar jednostki. Zasadniczo oznacza to, że wykonano kilka kontroli granic dla węzła, a największe możliwe granice zostały zapamiętane jako prześwit węzła. Kiedy więc chcemy umieścić rycerza śmierci na jakimś węźle, staje się to tak proste, jak porównanie prześwitu węzła z rozmiarem rycerza śmierci. Oczywiście sprawy staną się znacznie bardziej złożone, gdy kilka jednostek skacze dookoła rywalizując o węzły, ale to już inna historia.

Aby uzyskać więcej informacji, możesz sprawdzić ten artykuł:

http://harablog.wordpress.com/2009/01/29/clearance-based-pathfinding/

Korzystałby z teselacji, aby tworzyć siatki nawigacyjne obszarów AKA. W tym artykule wyjaśniono tę koncepcję za pomocą pełnych diagramów.

Nadal możesz zachować A * jako swoje podejście do wyszukiwania ścieżek, jednak twoja sieć nie jest już siatką (wykres 4 połączony), ale grafem reprezentującym dowolną łączność między regionami wielokątnymi. Musisz więc dostosować algorytm do własnych potrzeb.