Den kürzesten Weg auf einem sechseckigen Gitter finden

14

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.

Timothy Mayes
quelle
5
Ein * gibt Ihnen den kürzesten Weg unabhängig von der Form Ihres Diagramms (Raster, Hex, Freiform ..)
Jari Komppa

Antworten:

21

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:

Bildbeschreibung hier eingeben

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.

ZorbaTHut
quelle
Vielen Dank für den Link zum A * -Suchalgorithmus. Der einzige Weg, den ich mir vorstellen kann, nsew und nw / se zu durchqueren, ist ein gekipptes Hex. Was in meinem Kopf komisch aussieht. Kannst du mir ein Beispiel dafür geben?
Timothy Mayes
4
Ich sage, dass Ihr gerendertes Bild nicht viel Ähnlichkeit mit der internen Struktur haben muss. Ich schlage vor, dass Sie intern NSEW und NW / SE verwenden, aber Sie zeigen es dem Benutzer an, als ob es ein Raster wäre. Anhängen eines erläuternden Diagramms an die ursprüngliche Antwort :)
ZorbaTHut
2
Interessante Darstellung für ein Hex-Gitter. Normalerweise mache ich ein gezacktes Muster, daher ist die Nachbarschaft für gerade und ungerade Reihen unterschiedlich. Dies führt zu einer zusätzlichen minimalen Komplexität bei der Pfadsuche, nutzt jedoch ein zweidimensionales Array effizienter (vorausgesetzt, der gesamte Spielbereich ist ein Rechteck).
Panda Pyjama
2
@PandaPyjama: gezackt funktioniert besser, um rechteckige Karten effizient zu speichern. Mit diesem Trick
amitp
2
@PandaPyjama, es gibt noch einen anderen interessanten Trick, den Sie verwenden können: Sie können die nicht gezackte Darstellung für Koordinaten verwenden und dann den Hintergrund für Ihren Datenspeicher hinter etwas abstrahieren, das die "gezackte" Methode verwendet. Ich habe festgestellt, dass das Koordinatensystem von non-jagged viel einfacher zu handhaben ist, aber wenn es einmal abstrahiert ist, kann das Backend alles tun, um die Dinge effizienter zu machen :)
ZorbaTHut
5

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.

Pieter Geerkens
quelle
Beeindruckend! Netto eine Stimme weniger für das Posten einer Bibliothek mit Arbeitscode, mit Beispielen und Dokumentation, die die vom OP gestellten Fragen / Probleme beantwortet.
Pieter Geerkens
5
Ich war zwar nicht der Downvoter (und die Etikette schlägt im Allgemeinen vor, einen Kommentar zu hinterlassen, der eine Downvote erklärt), aber ich vermute, dass die Downvote darauf zurückzuführen ist, dass (a) der Post nach Werbung aussieht und (b) der Großteil einer Antwort auf die andere gestellt wird Die Seite eines Links wird im Allgemeinen verpönt, weil Links dazu neigen zu verrotten und SE-Sites versuchen, in sich geschlossen zu sein. Die hier bereitgestellten Informationen sind interessant, beantworten jedoch nicht die Frage des Benutzers. Die einzigen Informationen, die die Frage beantworten können, befinden sich auf der anderen Seite des Links.
Steven Stadnicki
Gute Argumente; Danke. Ich habe den Beitrag um Auszüge erweitert, die sich mit der Frage befassen, wie mehrere hexadezimale Gitterkoordinaten effizient verwaltet werden können. Die Bibliothek mit den veröffentlichten Codes ist Freeware
Pieter Geerkens
Hoppla! Die Division durch 2 funktioniert nur für positive ganze Zahlen. (Nochmals vielen Dank, K & R.) Es sollte durch einen Aufruf der Normalize () -Methode in IntVector2D ersetzt werden:
Pieter Geerkens
public IntVector2D Normalize() { if (Z==1) return this; else { var x = (X >= 0) ? X : X - Z; var y = (Y >= 0) ? Y : Y - Z; return new IntVector2D(x/Z, y/Z); } }
Pieter Geerkens
0

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.

david.pfx
quelle