Finden von Zellen in Reichweite auf einem hexagonalen Gitter

8

Zuerst einmal - ich weiß, dass ich hier sehr dicht bin.

Damit versuche ich, eine C # -Implementierung dieses Algorithmus zu schreiben:

var results = []
for each -N  dx  N:
  for each max(-N, -dx-N)  dy  min(N, -dx+N):
    var dz = -dx-dy
    results.append(cube_add(center, Cube(dx, dy, dz)))

Ich habe dies aus dieser enormen Ressource genommen.

Mein Problem ist, dass jede Implementierung, die ich bisher ausprobiert habe, verrückte Ergebnisse erzielt hat. Der unten gezeigte Code führt derzeit beispielsweise dazu:

1

und das:

2

Mein Code sieht derzeit so aus:

for (int x = this.CellPositionX - distance; x <= this.CellPositionX + distance; x++)
    {
        for (int y = this.CellPositionY - Math.Max(-distance, -x - distance); y <= this.CellPositionY + Math.Min(distance, -x + distance); y++)
        {
            HexPosition rangePosition = new HexPosition(x, y);
            range.Add(rangePosition);
        }
    }

Kann hier jemand etwas Falsches erkennen? Alle Vorschläge sind willkommen. Ich habe jetzt schon eine Weile meinen Kopf darauf geschlagen.

Vielen Dank!

Aktualisierter Hinweis: Ich verwende Axialkoordinaten im Raster. Update Nr. 2: Wie unten erwähnt, hatte ich meine for..each-Schleife falsch und verwendete keine Deltas für das Training. Danke für die Hilfe!

Ich habe derzeit ein Problem wie unten gezeigt mit der Implementierung aus den Antworten: Geben Sie hier die Bildbeschreibung ein

Ich werde weiter nachforschen - wenn ich es herausfinde, werde ich die vollständigen Ergebnisse hier veröffentlichen. Vielen Dank an alle!

Aaron-Bindung
quelle
1
Vielen Dank für die Ressource, die wirklich gut aussieht! Ich war ein bisschen überwältigt, als mir klar wurde, dass fast alle Grafiken interaktiv sind. :)
Christer
3
In dem Beispiel, das er gibt, werden Würfelkoordinaten verwendet, während Sie anscheinend entweder versetzte oder axiale Koordinaten verwenden. Sie müssen das x, y, z von den kubischen Koordinaten, die er hat, in das von Ihnen verwendete Koordinatensystem konvertieren.
Alex Sherman
1
@ Vector57 Ich benutze Axial. Im dortigen Konvertierungsabschnitt wird erwähnt, dass ich mit der Z-Eigenschaft nichts zu tun habe und dass q / r und x / y austauschbar sind ... oder habe ich das falsch verstanden?
Aaron-Bond
Es scheint so, obwohl er in den Beispielen r = z verwendet, aber ich verstehe nicht, warum es wichtig sein sollte, welche Sie wählen.
Alex Sherman

Antworten:

4

Bei näherer Betrachtung hat Ihr Problem also nichts mit Koordinatensystemkonvertierungen zu tun. Dies hätte deutlicher gemacht werden können, indem Sie nicht Ihre Axialkoordinaten X und Y, sondern Q und R benannt haben. Das Problem, das Sie tatsächlich haben, sind schlechte Schleifenbedingungen. Das ursprüngliche Codebeispiel erzeugt Delta-Qs und -Rs, die Sie in Ihren for-Schleifen in absolute Koordinaten konvertieren möchten, und Sie haben einen Fehler gemacht. Der Algorithmus sollte stattdessen wie folgt aussehen:

for (int dx = -distance; dx <= distance; dx++)
{
    for (int dy = Math.Max(-distance, -dx - distance); dy <= Math.Min(distance, -dx + distance); dy++)
    {
        HexPosition rangePosition = new HexPosition(
            this.CellPositionX + dx, this.CellPositionY + dy);
        range.Add(rangePosition);
    }
}
Alex Sherman
quelle
Oh derp ... der Artikel erwähnt sogar, dass es sich um Delta-Werte handelt :( Ich werde das jetzt ausprobieren und sehen, wie es geht. Danke :)
Aaron-Bond
Danke dafür. Es ist definitiv viel näher an der richtigen Vorgehensweise. Ich vermassle immer noch etwas mit den Koordinaten, aber zumindest habe ich die richtige Nummer! Aus irgendeinem Grund habe ich eine Zelle zu hoch auf dem -x und eine zu niedrig auf dem + x. Ich habe oben ein Bild gepostet, wenn Sie etwas darüber wissen, aber ich werde mich trotzdem weiter untersuchen :) Vielen Dank für Ihre Hilfe!
Aaron-Bond
Interpretieren Sie die axialen Koordinaten richtig? Denken Sie daran, dass Sie x und y anstelle von x und z verwendet haben. Wenn der Rest Ihres Codes diese Änderung gegenüber den Beispielen nicht berücksichtigt, kann dies zu einem seltsamen Verhalten führen.
Alex Sherman
Ja, ich habe so gewechselt, dass es x und z ist. dx wird x und z = -dx - dy ...
Aaron-Bindung
1
Das neue Bild, das Sie gepostet haben, zeigt 7 hervorgehobene Felder. Dies ist, was Sie mit Abstand = 1 erwarten würden. Versuchen Sie, die Werte auszudrucken. Wenn CellPosition auf 0,0 und Abstand 1 eingestellt ist, sollten die erhaltenen Hexen (-1, 0) sein. (-1, 1); (0, -1); (0, 0); (0, 1); (1, -1); (1, 0)
amitp
7

Wie Vector57 feststellte, besteht das Problem darin, dass Sie das falsche Koordinatensystem verwenden . Der beschriebene Algorithmus soll mit Würfelkoordinaten verwendet werden , die x-, y- und z-Komponenten haben :

Würfelkoordinaten

Dies kann nicht aus dem Algorithmus des Pseudo - Code offensichtlich sein, aber das ist , weil es sich um eine Vereinfachung der ist dies :

var results = []
for each -N  dx  N:
    for each -N  dy  N:
        for each -N  dz  N:
            if dx + dy + dz = 0:
                results.append(cube_add(center, Cube(dx, dy, dz)))

... eine einfache verschachtelte Schleife über x, y und z, was Sie von einem Bereichsalgorithmus erwarten würden.

Ich weiß nicht, welches Koordinatensystem Sie verwenden, aber ich vermute, es ist eines der "Versatzkoordinatensysteme", die beliebt sind, weil sie einfach zu implementieren sind, indem die Gitterzellen in einem 2D-Array platziert werden:

Versatz q vertikale Layouts

Dies bedeutet nicht, dass Sie diese Cube-Algorithmen nicht verwenden können. es bedeutet nur, dass Sie müssen von den Würfelkoordinaten in Ihre eigenen konvertieren . Verwenden Sie beispielsweise Folgendes, um in das vertikale Layout "odd-q" zu konvertieren:

# convert cube to odd-q offset
col = x
row = z + (x - (x&1)) / 2

# convert odd-q offset to cube
x = col
z = row - (col - (col&1)) / 2
y = -x-z
Congusbongus
quelle
Ich hatte das Gefühl, dass es so etwas war. Es gab einen Teil dieser Seite, der die Konvertierung von Cube zu Axial erwähnte und sagte, dass nur der z-Teil entfernt werden soll und das verbleibende q und r zu x und y werden sollen. Ich denke, ich muss dort zu stark vereinfacht haben. Danke dafür. Hervorragende Erklärung, was mir gefehlt hat. Ich werde es später versuchen! :)
Aaron-Bond
Ich habe gerade einen Blick darauf geworfen und benutze Axial. Sicher, da der Algorithmus Z nicht erwähnt, ist er auch ein Straight q = xund ein r = ySystem?
Aaron-Bond