Sind quadratische oder hexadezimale Gitter besser für die Wegfindung?

16

Gibt es einen signifikanten Unterschied zwischen der Verwendung eines quadratischen oder hexagonalen Gitters für den Bereich, der von einem Pfadsuchalgorithmus durchsucht wird? Mit anderen Worten, ist quadratisch oder sechseckig besser, und wenn ja, warum.

ai path-finding Edwin Earl Ross
quelle
4
Denken Sie, Sie sollten verwenden, was auch immer zu Ihrem Gameplay passt;)
Andrew Russell

Antworten:

18

Die Hauptüberlegung bei der Entscheidung, ob ein Quadrat-Hex-Gitter verwendet werden soll, sollte nicht die einfache AI-Implementierung sein. Die Suchalgorithmen für die Breite und Tiefe sind nahezu gleich, unabhängig davon, welche Art von Grafik Sie haben.

Vielmehr handelt es sich um ein Gameplay-Problem, das von den Game-Designern berücksichtigt werden sollte. Quadratische Gitter sind für den Massenmarkt besser zugänglich (Hex-Boards sehen in der Regel "geeky" aus), und in einer Welt mit Steuerelementen für Auf / Ab / Links / Rechts ist es vom Standpunkt der Benutzeroberfläche aus viel intuitiver, durch Quadrate zu navigieren als durch Hex-Felder. Quadratische Gitter neigen auch dazu, die Bewegung etwas stärker einzuschränken. Unter der Annahme einer orthogonalen Bewegung (und nicht einer Diagonalen) sind 4 Züge erforderlich, um ein Hindernis mit einem Quadrat zu umgehen, im Vergleich zu 3 Zügen in einem Hex-Raster. Vom Standpunkt der Programmierung aus sind Hexes auch ein bisschen einfacher zu implementieren, aber es geht nicht so sehr um Suchalgorithmen, als dass ein quadratisches Gitter einem zweidimensionalen Array entspricht, sondern dass ein Hex-Gitter nicht wirklich einer Standarddatenstruktur zugeordnet ist.

Die Kehrseite von quadratischen Gittern ist, dass sich die Bewegung niemals richtig anfühlt. Eine diagonale Bewegung sollte sqrt (2) Bewegungspunkte erfordern, aber in der Praxis ist es entweder eine Bewegung (bei der man das Gefühl hat, auf Diagonalen zu laufen, und es gibt selten einen Grund, orthogonal zu laufen) oder eine Bewegung (bei der sich die diagonale Bewegung zu langsam anfühlt) ). Mit Hex-Gittern ist die Bewegungsentfernung viel intuitiver, da sie immer dieselbe Entfernung von einem Hex zu einem anderen aufweist, unabhängig davon, welchen Weg Sie einschlagen.

Ian Schreiber
quelle
3
+1. Dies ist eine Entwurfsentscheidung, keine KI-Entscheidung. Wenn Sie hexagonale Gitter verwenden möchten, ist ein Gitter mit quadratischem Versatz wie www-cs-students.stanford.edu/~amitp/game-programming/grids/… für Gelegenheitsspieler möglicherweise weniger einschüchternd und entspricht mathematisch den Sechsecken. Es ist auch eine praktische In-Memory-Darstellung.
2
+1 für den Satz "Quadratische Gitter sind für den Massenmarkt besser zugänglich (hexadezimale Bretter sehen normalerweise" geeky "aus)": D
Kornel Kisielewicz
Edwin fragt nicht, was in einem Spiel auf Gitterbasis besser ist. Er fragt, was für die KI besser ist, wenn sie Quadrate oder Sechsecke verwendet. Die Welt und das Gameplay selbst müssen sich nicht auf die Knoten beschränken, auf denen die KI sucht.
AttackingHobo
Ich habe rundenbasierte Strategiespiele mit hexadezimalen und quadratischen Gittern implementiert, und es gibt absolut keinen notwendigen Unterschied in Bezug auf die Komplexität der Wegfindung. Ich habe sogar ein Spiel von einer hexadezimalen Karte auf eine quadratische Karte umgestellt, und (abgesehen vom Rendern) musste ich nur eine MapLocation :: GetDistance () -Methode ändern, mit der die Entfernung zwischen zwei Sektoren berechnet wurde. Ich musste einfach die Berechnungen anpassen, um mit jeder anderen Zeile fertig zu werden, die etwas versetzt ist. In beiden Fällen können Sie dieselbe speicherinterne Darstellung verwenden. Also, wie die anderen gesagt haben, ist es wirklich ein Designproblem.
Mike Strobel
4
Abgesehen davon können Verhexungen einem zweidimensionalen Array zugeordnet werden. Stellen Sie sich ein quadratisches Gitter vor und verschieben Sie dann jede gerade Spalte um einen halben Schritt nach unten. Sie haben jetzt ein versetztes quadratisches Gitter, das isomorph zu einem hexadezimalen Gitter ist.
Asmor
3

Ich bin keineswegs ein KI-Experte, aber der Unterschied sollte vernachlässigbar sein. Quadratische Gitter sind etwas schneller (4 Verbindungen pro Knoten anstelle von 6), aber das ist nicht der limitierende Faktor in der algorithmischen Laufzeit. Je nachdem, welchen Algorithmus Sie verwenden möchten, ist der Code für ein Hex-Gitter möglicherweise etwas komplexer, da die Koordinatenberechnung etwas komplizierter ist und es schwieriger ist, die Abkürzungen für Quadtree / Octree zu verwenden, von denen ich glaube, dass sie es sind wird oft bei der Wegfindung verwendet.

In einer einfachen Welt wie einem rundenbasierten Strategiespiel sollte der Unterschied zwischen den beiden Layouts jedoch keine große Rolle spielen. Ein quadratisches Gitter ist etwas einfacher und schneller.

Gregory Avery-Weir
quelle
5
"Quadratische Gitter sind etwas schneller (4 statt 6 Verbindungen pro Knoten)" - es sei denn, Sie können über Diagonalen fahren. In diesem Fall sind es 8 gegenüber 6 Verbindungen.
Ian Schreiber
Touche. Du hast vollkommen recht. natürlich wären diagonale verbindungen wahrscheinlich.
Gregory Avery-Weir
3

Es gibt einen praktischen Unterschied, den ich in Bezug auf die Pfadplanung ausdenken kann. Das Verfahren von der Mitte einer Hex-Zelle zu einem ihrer Nachbarn ist immer gleich weit, wohingegen dies für Quadrate nicht gilt, wenn Sie eine diagonale Bewegung zulassen.

Clodéric
quelle
0

Diese Anleitung für Sechsecke ist fantastisch. Der Teil über die Pfadfindung enthält ein interaktives Beispiel und einige Informationen zur Verwendung der quadratischen Pfadfindung.

Wenn Sie graphbasierte Pfadfindung wie A * oder den Dijkstra-Algorithmus oder Floyd-Warshall verwenden, unterscheidet sich die Pfadfindung in Hex-Gittern nicht von der Pfadfindung in quadratischen Gittern.

  • Nachbarn. Der Beispielcode, den ich im Lernprogramm zur Pfadfindung zur Verfügung stelle, ruft graph.neighbors auf, um die Nachbarn eines Standorts abzurufen. Nutzen Sie dazu die Funktion im Abschnitt Nachbarn. Filtern Sie die unpassierbaren Nachbarn heraus.
  • Heuristik. Der Beispielcode für A * verwendet eine heuristische Funktion, die einen Abstand zwischen zwei Positionen angibt. Verwenden Sie die Entfernungsformel, die auf die Bewegungskosten skaliert ist. Wenn Ihre Bewegungskosten beispielsweise 5 pro Hex betragen, multiplizieren Sie die Distanz mit 5.
Kennzeichen
quelle