Den kürzesten Weg auf einem sechseckigen Gitter finden

Ich schreibe ein rundenbasiertes Spiel mit einigen Simulationselementen. Eine Aufgabe, mit der ich gerade beschäftigt bin, ist die Wegfindung. Ich möchte einen KI-Abenteurer in jeder Runde mit seinem aktuellen x, y und seinem Ziel x, y um ein Feld näher an sein Ziel heranrücken.

Wenn ich versuche, das selbst herauszufinden, kann ich mit 4 Richtungen problemlos feststellen

dx = currentX - targetY
dy = currentY - targetY

aber ich bin nicht sicher, wie ich feststellen soll, welche der 6 Richtungen tatsächlich die "beste" oder "kürzeste" Route ist.

In der aktuellen Konfiguration verwende ich beispielsweise Ost, West, Nordwest, Nordwest, Südwest, Südwest, Südwest, Südwest, Südwest, Südwest, Südwest, Südwest, Südwest.

Ich hoffe, das war nicht alles. Sogar ein oder zwei Links, um mich anzufangen, wären nett. Die meisten Informationen, die ich gefunden habe, beziehen sich auf das Zeichnen der Gitter und das Ermitteln des benötigten seltsamen Koordinatensystems.

Ein paar Antworten!

Das Koordinatensystem, das ich bei hexadezimaler Durchquerung am häufigsten gesehen habe, ist eines, bei dem sich der Spieler in jede normale NSEW-Richtung sowie nach NW und SE bewegen kann. Dann rendern Sie einfach jede Zeile um ein halbes Quadrat versetzt. Als Beispiel wird die Stelle (2,7) neben (1,7), (3,7), (2,6), (2,8) und den seltsamen Stellen betrachtet: (1,6) und (3,8). Wenn wir annehmen, dass (2,7) in der Mitte des Bildschirms gerendert wird, wird (2,6) nach oben und rechts gerendert, und (2,8) wird nach unten und rechts gerendert -die-links, (1,7) und (3,7) werden es links und rechts einklammern, und (1,6) und (3,8) werden sich oben links und unten rechts positionieren.

Ein Diagramm dessen, was ich meine:

Wenn Sie dies auf diese Weise tun, ist es nicht schwierig, den kürzesten direkten Weg zu finden. Fahren Sie die maximale NW / SE-Entfernung, die Sie können, ohne Ihr Ziel entlang einer Kardinalachse zu überschießen, und fahren Sie dann direkt entlang dieser Achse zum Ziel.

Aber das führt Sie natürlich gerne direkt durch Berge oder anderes unwegsames Gelände. Um eine Frage zu beantworten, die Sie noch nicht gestellt haben: A * -Suchalgorithmus ist ein gängiger und einigermaßen guter Ansatz zur Pfadfindung. Es wird nicht nur seltsame Nicht-Gitter-Layouts handhaben, sondern auch Hindernisse und sogar behinderten / langsamen Untergrund bewältigen können.

Ich habe gerade eine Bibliothek mit Hex-Grid-Anwendungen auf CodePlex.com veröffentlicht: https://hexgridutilities.codeplex.com/ Die Bibliothek enthält die Pfadfindung (unter Verwendung von A- * a la Eric Lippert) und Anwendungen für die automatisierte Konvertierung zwischen gezackte (als Benutzer bezeichnete) Koordinaten und nicht gezackte (als kanonisch bezeichnete) Koordinaten. Der Pfadfindungsalgorithmus ermöglicht, dass die Schrittkosten für jeden Knoten sowohl mit dem Eingangshex als auch mit der durchquerten Hex-Seite variieren (obwohl das bereitgestellte Beispiel einfacher ist). Es wird auch ein erhöhtes Sichtfeld mit Schattenwurf bereitgestellt [Bearbeiten: Wörter entfernt].

Hier ist ein Codebeispiel, das problemlos zwischen drei Hex-Gitter-Koordinatensystemen konvertiert werden kann:

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 und IntVector2D sind [edit: homogene] Integer-Implementierungen von affine2D Graphics Vector und Matrix. Die letzte Division der Vektoranwendungen durch 2 besteht darin, die Vektoren neu zu normalisieren. Dies könnte in der IntMatrix2D-Implementierung begraben sein, aber der Grund für das 7. Argument für die IntMatrix2D-Konstruktoren ist weniger offensichtlich. Beachten Sie die kombinierte Zwischenspeicherung und verzögerte Bewertung nicht aktueller Formulierungen.

Diese Matrizen sind für den Fall:

• Hex korn vertikale;
• Ursprung links oben für kanonische und Benutzerkoordinaten, links unten für benutzerdefinierte Koordinaten;
• Y-Achse senkrecht nach unten;
• Rechteckige X-Achse horizontal über; und
• Kanonische X-Achse nach Nordosten (dh nach oben und rechts, um 120 Grad nach links von der Y-Achse).

Die oben erwähnte Codebibliothek bietet einen ähnlich eleganten Mechanismus für das Hex-Picking (dh das Identifizieren des ausgewählten Hex mit einem Mausklick).

In kanonischen Koordinaten sind die 6 Kardinalrichtungsvektoren (1,0), (0,1), (1,1) und ihre Inversen für alle Sechsecke ohne die Asymmetrie gezackter Koordinaten.

Dies ist ein gelöstes Problem, für das viel Literatur zur Verfügung steht. Die beste Ressource, die ich kenne, sind Red Blob-Spiele: https://www.redblobgames.com/grids/hexagons/ .

Kurz gesagt, der wahrscheinlichste Grund ist, dass Sie mit dem falschen Koordinatensystem begonnen haben. Die Verwendung eines Cube-Koordinatensystems zur Implementierung des A * -Algorithmus ist recht einfach. Siehe Live-Demo über den obigen Link.

Wenn du wirklich ein anderes System verwenden möchten, konvertieren Sie bei Bedarf zu und von.