Znajdowanie najkrótszej ścieżki na siatce sześciokątnej

Piszę turową grę, która ma pewne elementy symulacyjne. Jednym z zadań, na których się teraz rozłączam, jest znalezienie ścieżki. Chcę za każdym razem przesuwać poszukiwacza przygód AI o jedną płytkę bliżej celu, używając jego obecnego x, y i jego celu x, y.

Próbując samemu to rozgryźć, mogę ustalić 4 kierunki bez problemu, używając

dx = currentX - targetY
dy = currentY - targetY

ale nie jestem pewien, jak ustalić, który z 6 kierunków jest faktycznie „najlepszą” lub „najkrótszą” trasą.

Na przykład, zgodnie z obecną konfiguracją, używam Wschodu, Zachodu, NE, NW, SE, SW, ale aby dostać się do kafelka NE, przesuwam się na wschód, potem na północny zachód zamiast po prostu przesuwać na północny zachód.

Mam nadzieję, że to nie wszystko było niepotrzebne. Przydałby mi się nawet tylko jeden lub dwa łącza. Większość informacji, które znalazłem, dotyczy rysowania siatek i rozcierania potrzebnego dziwnego układu współrzędnych.

Kilka odpowiedzi!

Układ współrzędnych, który widziałem najczęściej dla ruchu opartego na heksach, to taki, w którym gracz może poruszać się w każdym normalnym kierunku NSEW, a także w NW i SE. Następnie renderujesz po prostu każdy wiersz z przesunięciem o pół kwadratu. Na przykład lokalizację (2,7) uważa się za sąsiadującą z (1,7), (3,7), (2,6), (2,8), a te dziwne: (1,6) i (3,8). Tymczasem, jeśli założymy, że (2,7) jest renderowane na środku ekranu, (2,6) będzie renderowane w górę iw prawo, (2,8) będzie renderowane w dół i do - lewy, (1,7) i (3,7) przechwycą go odpowiednio w lewo i w prawo, a (1,6) i (3,8) ustawią się odpowiednio w lewym górnym i prawym dolnym rogu.

Schemat tego, co mam na myśli:

Jeśli robisz to w ten sposób, znalezienie najkrótszej bezpośredniej ścieżki nie jest trudne - pokonaj maksymalną odległość NW / SE, jaką możesz, nie przekraczając celu wzdłuż osi głównej, a następnie przejdź bezpośrednio wzdłuż tej osi do celu.

Ale oczywiście to z radością poprowadzi cię prosto przez góry lub inny nieprzejezdny teren. Aby odpowiedzieć na pytanie, które jeszcze nie zostało zadane: Algorytm wyszukiwania A * jest powszechnym i dość dobrym podejściem do wyszukiwania ścieżek. Poradzi sobie nie tylko z dziwnymi układami bez siatki, ale z radością poradzi sobie z przeszkodami, a nawet przeszkodą / powolnym podłożem.

Właśnie zamieściłem bibliotekę narzędzi hex-grid na CodePlex.com tutaj: https://hexgridutilities.codeplex.com/ Biblioteka zawiera wyszukiwanie ścieżek (przy użyciu A- * a la Eric Lippert) i zawiera narzędzia do automatycznej konwersji między postrzępione (zwane użytkownikiem) kordinaty i współrzędne nie strzępione (zwane kanonicznymi). Algorytm znajdowania ścieżki pozwala, aby koszt kroku dla każdego węzła zmieniał się zarówno w polu szesnastkowym wejściowym, jak i po stronie szesnastkowej (chociaż podany przykład jest prostszy). Zapewniono także podwyższone pole widzenia za pomocą rzutowania w tle, [edycja: słowa usunięte].

Oto przykładowy kod, który łatwo konwertuje między trzema układami współrzędnych sześciokątnych:

static readonly IntMatrix2D MatrixUserToCanon = new IntMatrix2D(2,1, 0,2, 0,0, 2);
IntVector2D VectorCanon {
  get { return !isCanonNull ? vectorCanon : VectorUser * MatrixUserToCanon / 2; }
  set { vectorCanon = value;  isUserNull = isCustomNull = true; }
} IntVector2D vectorCanon;
bool isCanonNull;

static readonly IntMatrix2D MatrixCanonToUser  = new IntMatrix2D(2,-1, 0,2, 0,1, 2);    
IntVector2D VectorUser {
  get { return !isUserNull  ? vectorUser 
             : !isCanonNull ? VectorCanon  * MatrixCanonToUser / 2
                            : VectorCustom * MatrixCustomToUser / 2; }
  set { vectorUser  = value;  isCustomNull = isCanonNull = true; }
} IntVector2D vectorUser;
bool isUserNull;

static IntMatrix2D MatrixCustomToUser = new IntMatrix2D(2,0, 0,-2, 0,(2*Height)-1, 2);
static IntMatrix2D MatrixUserToCustom = new IntMatrix2D(2,0, 0,-2, 0,(2*Height)-1, 2);
IntVector2D VectorCustom {
  get { return !isCustomNull ? vectorCustom : VectorUser * MatrixUserToCustom / 2; }
  set { vectorCustom  = value;  isCanonNull = isUserNull = true; }
} IntVector2D vectorCustom;
bool isCustomNull;

IntMatrix2D i IntVector2D to [edytuj: jednorodne] implementacje liczb całkowitych Affine2D Graphics Vector i Matrix. Ostateczny podział przez 2 w zastosowaniach wektorowych polega na ponownej normalizacji wektorów; może to być zakopane w implementacji IntMatrix2D, ale powód 7. argumentu dla konstruktorów IntMatrix2D jest mniej oczywisty. Zwróć uwagę na połączone buforowanie i leniwą ocenę preparatów długoterminowych.

Te macierze dotyczą przypadku:

• Ziarno sześciokątne pionowe;
• Pochodzenie w lewym górnym rogu dla współrzędnych kanonicznych i użytkownika, w lewym dolnym rogu dla współrzędnych niestandardowych;
• Oś Y pionowo w dół;
• Prostokątna oś X poziomo w poprzek; i
• Kanoniczna oś X w kierunku północno-wschodnim (tj. W górę i w prawo, w 120 stopniach w lewo od osi Y).

Wspomniana wyżej biblioteka kodów zapewnia podobnie elegancki mechanizm wybierania heksadecymalnego (tj. Identyfikowanie heksa wybranego kliknięciem myszy).

We współrzędnych kanonicznych 6 głównych wektorów kierunkowych to (1,0), (0,1), (1,1) i ich odwrotności dla wszystkich sześciokątów, bez asymetrii poszarpanych współrzędnych.

Jest to rozwiązany problem, który wymaga dużej literatury. Najlepszy zasób, jaki znam, to gry Red Blob: https://www.redblobgames.com/grids/hexagons/ .

W skrócie, najbardziej prawdopodobnym powodem jest to, że zacząłeś od niewłaściwego układu współrzędnych. Korzystanie z układu współrzędnych Cube implementującego algorytm A * jest dość proste. Zobacz demo na żywo pod powyższym linkiem.

Jeśli naprawdę chcesz skorzystać z innego systemu, w razie potrzeby dokonaj konwersji do iz.