Ein Spielfeld aus Sechsecken ist auf dem Papier schnell gezeichnet. Beim Programmieren fängt der Ärger mit der ersten Frage an: Wie heißt ein Feld? Ein normales Raster hat x und y, vier Nachbarn und eine Distanz, die man im Schlaf ausrechnet. Bei Sechsecken stimmt davon nichts mehr, und zum Nummerieren gibt es gleich mehrere Möglichkeiten, die alle ihre Berechtigung haben.
Die Demo zeigt ein Feld aus 9 mal 7 Hexes. Ein Klick oder Ziehen setzt den Cursor, rechts steht dasselbe Feld als Offset, Axial, Cube und Doubled. Die sechs Nachbarn leuchten orange, alle anderen Felder zeigen ihre Distanz zum Cursor. Fährst du mit der Maus über ein Feld, siehst du, wie sich die Zahl zusammensetzt.
Die Chips unten rechts schalten zwischen Pointy (eine Ecke zeigt nach oben) und Flat (eine Seite liegt oben) um, außerdem zwischen odd und even. Mit "Offset" und "Axial" stehen die Koordinaten in den Feldern, "Naive" zeigt eine Distanz, die man gern zuerst baut und die falsch ist. Der Cursor lässt sich auch mit Q W E A D Z X C oder den Pfeiltasten bewegen.
Red Blob Games erklärt Hex-Raster seit Jahren ausführlich und mit schönen interaktiven Grafiken: Hexagonal Grids und die dazugehörige Implementierungs-Seite. Hier ist alles in eigenem Code nachgebaut, mit Tests. Der Post legt die Grundlagen für ein paar Folgeposts.
Offset: das Array
Wer ein Hex-Feld in einem zweidimensionalen Array speichert, landet bei Offset-Koordinaten (col, row). Jede zweite Zeile ist um ein halbes Feld nach rechts geschoben, damit die Sechsecke ineinandergreifen. Welche Zeilen das sind, ist Geschmackssache: bei odd-r die ungeraden, bei even-r die geraden. Bei Flat-Hexes sind es Spalten, die nach unten rutschen (odd-q und even-q). Das sind vier Konventionen, und die Demo schaltet sie live um. Dasselbe Feld hat danach andere Offset-Zahlen.
Für Rechnungen taugt Offset schlecht, weil sich die Nachbarn je nach Zeile anders verhalten. Bei odd-r bleibt, wer in Zeile 2 nach rechts oben geht, in derselben Spalte, in Zeile 3 landet er eine Spalte weiter rechts. Dafür braucht man zwei Nachbartabellen, eine pro Parität:
{{1, 0}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}, {0, 1}}, // row not pushed right
{{1, 0}, {1, -1}, {0, -1}, {-1, 0}, {0, 1}, {1, 1}}, // row pushed right
Das sind die sechs Schritte {dcol, drow} für eine Pointy-Zeile ohne und mit Verschiebung. Für Flat gibt es zwei weitere, für even statt odd wird die Auswahl vertauscht. Mit neighborOffset bewegt sich in der Demo der Cursor, wenn du eine Taste drückst.
Axial: zwei Achsen, ein Schritt
Gerechnet wird in Axial. Statt Spalte und Zeile gibt es q (waagerecht) und r (bei Pointy schräg nach unten, einen Versatz gibt es nicht mehr). Dafür sind die sechs Nachbarn in jedem Feld dieselben Schritte:
constexpr Axial kAxialDirections[kDirections] = {{1, 0}, {1, -1}, {0, -1}, {-1, 0}, {-1, 1}, {0, 1}};
Zum Nachbarn geht es mit einer Addition, ohne Fallunterscheidung:
inline Axial neighbor(Axial a, int direction) {
const Axial step = kAxialDirections[wrapDirection(direction)];
return {a.q + step.q, a.r + step.r};
}
Der Umweg von Offset nach Axial ist einmal geschrieben. Für Pointy mit odd-r:
const int shift = l.parity == Parity::Odd ? o.row - parityBit(o.row) : o.row + parityBit(o.row);
return {o.col - shift / 2, o.row};
Vom Zeilenwert wird erst das Paritätsbit abgezogen (bei even-r addiert), dann ist die Zahl gerade und die Division durch 2 exakt. Die Demo rechnet für das Feld unter dem Cursor genau so: Offset col 4, row 3 wird zu q 3, r 3.
Cube: die dritte Achse
Cube bekommt zu q und r ein s dazu, und die drei Werte ergeben immer null:
inline Cube toCube(Axial a) { return {a.q, a.r, -a.q - a.r}; }
Axial ist also Cube ohne s, mehr steckt nicht dahinter. Die Demo zeigt die Rechnung in der orangen Zeile: s = -(3) - (3) = -6. Dass man s trotzdem mitführt, liegt an der Distanz. Die Anzahl der Schritte zwischen zwei Feldern ist der größte Betrag der drei Differenzen:
inline int cubeDistance(Cube a, Cube b) { return std::max({std::abs(a.q - b.q), std::abs(a.r - b.r), std::abs(a.s - b.s)}); }
Im Startbild ist der Cursor bei (3, 3, -6) und das markierte Feld bei (7, 1, -8). Die Differenzen sind 4, -2 und -2, der größte Betrag ist 4. Es liegen vier Schritte dazwischen, und die Heatmap zeigt dort auch eine 4.
Direkt in Axial geht es auch, (|dq| + |dq + dr| + |dr|) / 2 liefert dieselbe Zahl, nur sieht man dabei nicht mehr, warum.
Doubled
Die vierte Form ist selten. Bei Pointy verdoppelt Doubled die Spalte: col = 2q + r, row = r. Die Spalte zählt dann halbe Hexbreiten, und gültig sind nur Zellen, bei denen col + row gerade ist. Bei Flat wird stattdessen die Zeile verdoppelt.
Zeichnen
Auf den Bildschirm kommt ein Hex per Formel aus den Axial-Koordinaten. Für Pointy liegt der Mittelpunkt bei:
return {kSqrt3 * (q + r / 2.0), 1.5 * r};
Alles ist für eine Hex-Größe von 1 (Mittelpunkt bis Ecke) gerechnet, die Demo multipliziert mit 30 Pixeln. Ein Test prüft, dass alle sechs Nachbarn exakt √3 entfernt liegen und sich mit dem Feld zwei Ecken teilen.
Das Feld unter der Maus finde ich hier noch auf dem faulen Weg: der nächste Mittelpunkt, danach prüfe ich, ob der Punkt wirklich in diesem Sechseck liegt. Bei 63 Feldern reicht das. Die Formel, die direkt von Pixel zu Hex rechnet, kommt in einem Folgepost.
Stolperfallen
Die naheliegende Distanz im Offset-Raster ist |dcol| + |drow|. Der Chip "Naive" schaltet sie ein, und die Ringe um den Cursor zerfallen. Schon die Nachbarn zeigen nicht mehr überall eine 1. Bei odd-r ist das Feld (1, 0) ein Nachbar von (0, 1), der naive Wert sagt 2. Das Hover-Feld rechts zeigt beide Zahlen untereinander und markiert die falsche.
Die zweite Falle steckt in row % 2. In C++ ist -1 % 2 gleich -1, und row % 2 == 1 hält eine negative ungerade Zeile für gerade. Mit x & 1 kommt bei Zweierkomplement auch bei negativen Zahlen das richtige Bit heraus, der Test deckt Zeile -1 und Spalte -1 deshalb extra ab.
Dazu kommt das Vermischen von odd und even. Dieselben Offset-Zahlen liegen in odd-r und even-r an anderer Stelle, die Demo zeigt das beim Umschalten, weil der Cursor seine Offset-Werte behält.
Wie ich das teste
Alle Umrechnungen laufen in beide Richtungen für alle vier Konventionen, das fängt Vorzeichenfehler. Die Nachbartabellen vergleiche ich für jedes Feld eines Bereichs mit dem Weg über Axial: umrechnen, Schritt machen, zurückrechnen. Die Distanz prüfe ich ohne Formel. Eine Breitensuche läuft vom Ursprung Schritt für Schritt nach außen, 217 Felder innerhalb von acht Schritten, und cubeDistance muss für jedes die Schrittzahl liefern, mit der die Suche es erreicht hat.
Den Code findest du im Repo unter hex-koordinaten. Alle Demos der Serie sammelt das Projekt Game Dev Snippets.