Czy kwadratowe lub heksagonalne siatki są lepsze do wyszukiwania ścieżek?

Czy jest jakaś znacząca różnica między użyciem kwadratowej lub heksagonalnej siatki dla obszaru przeszukiwanego przez algorytm wyszukiwania ścieżki? Innymi słowy, jest kwadratowy lub sześciokątny lepszy, a jeśli tak, to dlaczego.

Główną kwestią przy podejmowaniu decyzji, czy używać siatek kwadratowych vs heksadecymalnych, nie powinna być łatwość implementacji sztucznej inteligencji - algorytmy wyszukiwania w pierwszej kolejności i w pierwszej kolejności są w zasadzie takie same, bez względu na rodzaj posiadanego wykresu.

Jest to raczej problem z grą, który powinien wziąć pod uwagę projektant gry. Kwadratowe siatki są bardziej dostępne dla rynku masowego (tablice sześciokątne zwykle wyglądają „maniakalne”), aw świecie kontrolek góra / dół / lewo / prawo jest o wiele bardziej intuicyjne poruszanie się po kwadratach niż heksy z punktu widzenia interfejsu użytkownika. Kwadratowe siatki również nieco bardziej ograniczają ruch; zakładając ruch ortogonalny (a nie ukośny), potrzeba 4 ruchów, aby obejść przeszkodę o jednym kwadracie, w porównaniu do 3 ruchów na siatce heksadecymalnej. Z punktu widzenia programowania, hexy są również nieco łatwiejsze do implementacji, ale nie chodzi tu o algorytmy wyszukiwania, ponieważ kwadratowa siatka jest równa dwuwymiarowej tablicy, ale siatka heksadecy tak naprawdę nie jest odwzorowana na standardową strukturę danych.

Wadą kwadratowych siatek jest to, że ruch nigdy nie wydaje się właściwy. Poruszanie się po przekątnej powinno zająć sqrt (2) punkty ruchu, ale w praktyce jest to albo 1 ruch (co sprawia, że ​​chodzenie po przekątnych jest szybkie i rzadko ma powód, aby chodzić ortogonalnie), albo 2 ruchy (co sprawia, że ​​ruch po przekątnej jest zbyt wolny ). W przypadku siatek heksadecymalnych odległość ruchu jest o wiele bardziej intuicyjna, ponieważ zawsze jest taka sama odległość od jednego heksa do drugiego, bez względu na wybraną ścieżkę.

W żadnym wypadku nie jestem ekspertem od sztucznej inteligencji, ale różnica powinna być znikoma. Siatki kwadratowe są nieco szybsze (4 połączenia na węzeł zamiast 6), ale tak naprawdę nie jest to czynnik ograniczający w środowisku algorytmicznym. W zależności od algorytmu, którego planujesz użyć, kod może być nieco bardziej złożony dla siatki heksadecymalnej, ponieważ obliczenie współrzędnych jest nieco bardziej skomplikowane, a trudniej jest użyć rodzaju skrótów czterokrotnie / ośmiokątnych, które moim zdaniem są często używane w poszukiwaniu ścieżek.

Ale w prostym świecie, takim jak turowy poziom strategii, różnica między dwoma układami nie powinna mieć większego znaczenia; kwadratowa siatka będzie nieco prostsza i szybsza.

Jest jedna praktyczna różnica, którą mogę przemyśleć w zakresie planowania ścieżki. Przemieszczanie się od środka komórki heksadecymalnej do jednego z sąsiadów jest zawsze tej samej odległości, natomiast jeśli pozwalasz na ruch ukośny, nie dotyczy to kwadratów.

Ten przewodnik na temat sześciokątów jest niesamowity. Część o wyszukiwaniu ścieżek zawiera interaktywny przykład i kilka informacji o tym, jak stosować kwadratowe wyszukiwanie ścieżek.

Jeśli korzystasz z graficznego wyszukiwania ścieżek, takiego jak A * lub algorytm Dijkstry lub Floyd-Warshall, wyszukiwanie ścieżek na siatkach szesnastkowych nie różni się od wyszukiwania ścieżek na siatkach kwadratowych.

• Sąsiedzi Przykładowy kod, który podaję w samouczku odnajdywania ścieżek, wywołuje graph.neighbors, aby uzyskać sąsiadów z lokalizacji. W tym celu użyj funkcji w części dotyczącej sąsiadów. Odfiltruj sąsiadów, którzy są nieprzejezdni.
• Heurystyczny. Przykładowy kod dla A * wykorzystuje funkcję heurystyczną, która podaje odległość między dwiema lokalizacjami. Użyj formuły odległości, skalowanej w celu dopasowania do kosztów ruchu. Na przykład, jeśli koszt ruchu wynosi 5 na heks, pomnóż odległość przez 5.