Ein Hex-Raster zu zeichnen ist Formelsache, wie das geht steht in Hex-Koordinaten. Die Gegenrichtung braucht man dauernd: Die Maus steht irgendwo, welches Feld ist gemeint? Bei einem Quadratraster teilst du durch die Kantenlänge und bist fertig. Bei Hexagonen sind die Zeilen gegeneinander versetzt und die Kanten schräg, mit einer Division kommst du nicht weit.
Die Karte links zeigt die Rechnung für die Mausposition: erst die gebrochenen Werte q, r und s, dann die gerundeten, dann wie weit jeder Wert beim Runden gewandert ist, und ganz unten das Ergebnis. Der Chip "Naive" rundet die drei Werte einzeln, "Rounded" korrigiert das Ergebnis. Die orange Fläche im Feld ist die Stelle, an der die naive Variante kein Hex findet. Mit "Line" zeichnest du eine Linie zwischen zwei Feldern: ein Klick setzt den Start, die Maus ist das Ende. Spitz oder flach lässt sich umschalten, der Code ist derselbe, nur die Matrix ist eine andere.
Die Idee stammt aus dem Hex-Tutorial von Red Blob Games, das ich dir sehr ans Herz lege. Hier steht alles in meinen Worten und mit meinem Code.
Pixel zu gebrochenen Koordinaten
Hex nach Pixel ist eine lineare Abbildung, bei spitzen Hexagonen so:
return {l.origin.x + l.size * (kSqrt3 * q + kSqrt3 / 2.0 * r), l.origin.y + l.size * 1.5 * r};
Zurück geht es mit der inversen Matrix. Erst Ursprung abziehen und durch die Hexgröße teilen, dann zwei Zeilen:
const double x = (p.x - l.origin.x) / l.size;
const double y = (p.y - l.origin.y) / l.size;
const double q = l.flat ? 2.0 / 3.0 * x : kSqrt3 / 3.0 * x - 1.0 / 3.0 * y;
const double r = l.flat ? -1.0 / 3.0 * x + kSqrt3 / 3.0 * y : 2.0 / 3.0 * y;
return {q, r, -q - r};
Das Ergebnis sind Koordinaten mit Nachkommastellen, die Maus liegt irgendwo zwischen den Feldmitten. s wird aus q und r abgeleitet, damit der Punkt auf der Ebene q + r + s = 0 bleibt. Fehlt nur noch das Runden.
Die naheliegende Falle
Drei Zahlen, jede auf die nächste ganze Zahl: round(q), round(r), round(s). Dumm nur: Jeder Wert wandert dabei um bis zu 0,5, die Summe der gerundeten Werte ist danach -1, 0 oder +1. Bei -1 und +1 steht da ein Tripel, das kein Hex ist.
Wie oft das passiert, lässt sich ausrechnen. Sei a der Abstand von q zur nächsten ganzen Zahl, b der von r, beide mit Vorzeichen. Die Summe stimmt nur, wenn |a + b| unter 0,5 bleibt. Im Einheitsquadrat verletzen das zwei Dreiecke in den Ecken mit je einem Achtel Fläche, zusammen ein Viertel. Im Test zähle ich es über ein Pixelraster nach, über beide Layouts liegt der Anteil zwischen 20 und 30 Prozent. In der Demo siehst du es: Chip 1 drücken, die orange Fläche liegt rund um die Kanten der Felder. Mitten in einem Feld rundet alles richtig, die Fehlstellen sitzen an den Rändern.
Beim Start steht die Maus nahe an der Ecke eines Feldes: q = 0,554, r = -0,308, s = -0,246. Gerundet wird daraus (1, 0, 0), Summe 1. Das ist kein Hex.
Die Korrektur
Der Wert, der beim Runden am weitesten gewandert ist, hat den größten Fehler. Den wirft man weg und rechnet ihn aus den beiden anderen neu aus:
if (o.dq > o.dr && o.dq > o.ds) {
o.fixed.q = -o.naive.r - o.naive.s;
o.fixedAxis = 0;
} else if (o.dr > o.ds) {
o.fixed.r = -o.naive.q - o.naive.s;
o.fixedAxis = 1;
} else {
o.fixed.s = -o.naive.q - o.naive.r;
o.fixedAxis = 2;
}
Im Beispiel ist q um 0,446 gewandert, r um 0,308, s um 0,246. Also fliegt q raus und wird zu -0 - 0 = 0. Die Maus liegt im Feld (0, 0, 0). Das ist auch tatsächlich das Feld, dessen Mitte am nächsten liegt: Ich vergleiche im Test 4000 zufällige Punkte in beiden Layouts gegen eine Brute-Force-Suche über alle Feldmitten, es gibt keine Abweichung.
Liegen zwei Werte gleichauf, entscheidet die Reihenfolge der Abfrage. Das ist bei Punkten genau auf einer Kante eine Konvention, die beiden Felder sind gleich nah.
Eine Linie über das Raster
Dasselbe Runden trägt auch Linien. Zwischen zwei Feldern liegen N = distance(a, b) Schritte, das größte Maß der drei Koordinatenunterschiede. Man nimmt N + 1 gleichmäßige Punkte der geraden Linie im Würfelraum und rundet jeden:
out.push_back(n == 0 ? fa : lerp(fa, fb, static_cast<double>(i) / static_cast<double>(n)));
Das Ergebnis ist eine Kette von Nachbarfeldern ohne Lücken und ohne Sprünge. Das teste ich für viele Start- und Zielpaare. Schaltest du in der Demo bei Line auf "Naive", fallen die Stützpunkte heraus, deren naive Rundung kein Hex ergibt: orange Punkt, kein Feld.
Bleibt die Kante. Läuft die Linie genau auf der Grenze zweier Felder, entscheidet die Regel beim Gleichstand. Von (0, 0, 0) nach (2, -1, -1) liegt der mittlere Punkt exakt bei (1, -0,5, -0,5), und ohne weitere Maßnahme kommt (1, -1, 0) heraus. Der Chip "Nudge" verschiebt die ganze Linie um 0,000001 (genauer um (e, e, -2e), die Summe bleibt null):
const Frac fa{a.q + e, a.r + e, a.s - 2.0 * e};
const Frac fb{b.q + e, b.r + e, b.s - 2.0 * e};
Damit liegt der Punkt eindeutig auf einer Seite, das Ergebnis ist (1, 0, -1), und es ist egal, in welche Richtung du die Linie läufst. Im Test steht genau dieser Fall. In der Demo siehst du ihn, wenn du den Start auf die Mitte setzt, das Ende zwei Felder rechts oben davon legst und N drückst: Das Feld in der Mitte der Linie springt auf die andere Seite.
Stolperfallen
Die Umrechnung in int ist der Punkt, an dem Mauskoordinaten außerhalb des Fensters oder ein NaN schiefgehen können. toInt klemmt auf plus minus eine Million und macht aus NaN eine Null, damit der Cast nie undefiniertes Verhalten auslöst. Eine Hexgröße von 0 würde in toFractional durch null teilen, dort kommt das Ursprungsfeld heraus.
Und die Orientierung: Spitz und flach brauchen verschiedene Matrizen und verschiedene Eckwinkel (30 Grad Versatz). Wer Formeln von spitz und flach vermischt, bekommt Felder, die sich nur fast treffen. Der Test prüft deshalb, dass zwei benachbarte Felder in beiden Layouts genau zwei Ecken teilen.
Den Code findest du im Repo unter hex-pixel-runden. Alle Demos der Serie sammelt das Projekt Game Dev Snippets.