Wie erhalte ich Pixel-zu-Hex-Koordinaten auf einer Array-basierten Hex-Karte?

10

Ich versuche, eine Pixel-zu-Koordinaten-Funktion für eine Hex-Karte zu erstellen, aber ich verstehe die Mathematik nicht richtig. Alles, was ich versuche, scheint ein wenig anders zu sein, und die Beispiele, die ich gefunden habe, basieren auf eingekreisten zentrierten Karten.

Mit 'Array-basiert' meine ich die Art und Weise, wie die Hexes geordnet sind, siehe Bild.

Das genaueste Ergebnis, das ich erhalten habe, war mit dem folgenden Code, aber er ist immer noch deaktiviert und wird umso schlimmer, je mehr die Werte steigen:

public HexCell<T> coordsToHexCell(float x, float y){
    final float size = this.size; // cell size
    float q = (float) ((1f/3f* Math.sqrt(3) * x - 1f/3f * y) / size);
    float r = 2f/3f * y / size;
    return getHexCell((int) r, (int) q);
}

Hexmap

Der Bildschirm beginnt mit 0,0 oben links, jede Zelle kennt ihre Mitte.

Ich brauche nur eine Möglichkeit, Bildschirmkoordinaten in Hex-Koordinaten zu übersetzen. Wie könnte ich das machen?

petervaz
quelle

Antworten:

12

Es gibt viele Hex-Koordinatensysteme. Die "Offset" -Ansätze eignen sich gut zum Speichern einer rechteckigen Karte, aber die Hex-Algorithmen sind in der Regel schwieriger.

In meiner Hex-Gitterführung (von der ich glaube, dass Sie sie bereits gefunden haben) heißt Ihr Koordinatensystem "gerade-r", außer Sie beschriften sie r,qanstelle von q,r. Mit den folgenden Schritten können Sie Pixelpositionen in Hex-Koordinaten konvertieren:

  1. Konvertieren Sie Pixelpositionen mit dem in diesem Abschnitt beschriebenen Algorithmus in axiale Hex-Koordinaten . Dies ist, was Ihre Funktion tut. Sie müssen jedoch noch einen Schritt tun.
  2. Diese axialen Koordinaten sind gebrochen. Sie müssen auf das nächste Hex abgerundet werden. In Ihrem Code verwenden Sie, (int)r, (int)qaber das funktioniert nur für Quadrate; Für Hexes brauchen wir einen komplizierteren Rundungsansatz. Konvertieren der r, qzu Würfel Koordinaten unter Verwendung der axialen Würfel Formeln hier . Dann nutzen Sie die hex_roundFunktion hier .
  3. Jetzt haben Sie einen ganzzahligen Satz von Würfelkoordinaten . Ihre Karte verwendet "gerade-r", keinen Würfel, daher müssen Sie zurück konvertieren. Verwenden Sie den Würfel, um Formeln von hier aus auszugleichen .

Ich muss den Pixel-Hex-Koordinatenabschnitt neu schreiben, um ihn viel klarer zu machen. Es tut uns leid!

Ich weiß, das scheint verworren zu sein. Ich verwende diesen Ansatz, weil er am wenigsten fehleranfällig ist (keine Sonderfälle!) Und eine Wiederverwendung ermöglicht. Diese Konvertierungsroutinen können wiederverwendet werden. Die Sechskantrundung kann wiederverwendet werden. Wenn Sie jemals Linien zeichnen oder um eine Hex-Koordinate drehen oder ein Sichtfeld oder andere Algorithmen ausführen möchten, sind einige dieser Routinen auch dort hilfreich.

amitp
quelle
Ich werde das versuchen. Vielen Dank. Ich habe bereits eine funktionierende Lösung gefunden, möchte mich aber wirklich mehr mit Hex-Mathematik beschäftigen. Ich habe nur ein bisschen Probleme damit, meinen Kopf darum zu wickeln und kleine Schritte zu machen.
Petervaz
2
@amitp: Ich liebe deinen Reiseführer, ich bin darauf gestoßen, als ich vor ein paar Jahren einen hexagonalen Gittergenerator geschrieben habe. Hier ist meine Lösung, wenn Sie interessiert sind: Stapelüberlauf - Algorithmus zum Erzeugen eines hexagonalen Gitters mit Koordinatensystem .
Mr. Polywhirl
1
Wo liegt der Ursprung der Pixelkoordinaten? In der Mitte des Sechsecks 0,0 in Versatzkoordinaten?
Andrew
1
@ Andrew Ja. Sie können den Ursprung in Pixelkoordinaten verschieben, bevor Sie die Transformation in Hex-Koordinaten ausführen.
Amitp
9

Meiner Meinung nach gibt es zwei Möglichkeiten, um mit diesem Problem umzugehen.

  1. Verwenden Sie ein besseres Koordinatensystem. Sie können sich die Mathematik viel leichter machen, wenn Sie klug sind, wie Sie die Felder nummerieren. Amit Patel hat die endgültige Referenz für hexagonale Gitter. Auf dieser Seite sollten Sie nach axialen Koordinaten suchen .

  2. Leihen Sie sich Code von jemandem aus, der ihn bereits gelöst hat. Ich habe einen Code , der funktioniert und den ich aus der Quelle Battle for Wesnoth entnommen habe . Denken Sie daran, dass meine Version den flachen Teil der Felder oben hat, so dass Sie x und y tauschen müssen.

Michael Kristofik
quelle
6

Ich denke, Michael Kristofiks Antwort ist richtig, insbesondere, weil er die Website von Amit Patel erwähnt hat, aber ich wollte meinen neuen Ansatz für Hex-Gitter teilen.

Dieser Code stammt aus einem Projekt, an dem ich das Interesse verloren habe und das ich in JavaScript aufgegeben habe , aber die Mausposition für Hex-Kacheln hat hervorragend funktioniert. Ich habe * diesen GameDev-Artikel * für meine Referenzen verwendet. Von dieser Website hatte der Autor dieses Bild, das zeigte, wie alle Hex-Seiten und -Positionen mathematisch dargestellt werden können.

In meiner Renderklasse hatte ich dies in einer Methode definiert, mit der ich jede gewünschte Hex-Seitenlänge einstellen konnte. Hier gezeigt, weil einige dieser Werte im Pixel-Hex-Koordinatencode referenziert wurden.

                this.s = Side; //Side length
                this.h = Math.floor(Math.sin(30 * Math.PI / 180) * this.s);
                this.r = Math.floor(Math.cos(30 * Math.PI / 180) * this.s);
                this.HEXWIDTH = 2 * this.r;
                this.HEXHEIGHT = this.h + this.s;
                this.HEXHEIGHT_CENTER = this.h + Math.floor(this.s / 2);

In der Mauseingabeklasse habe ich eine Methode erstellt, die eine x- und y-Koordinate des Bildschirms akzeptiert, und ein Objekt mit der Hex-Koordinate zurückgegeben, in der sich das Pixel befindet. * Beachten Sie, dass ich eine gefälschte "Kamera" hatte, so dass auch Offsets für die Renderposition enthalten sind.

    ConvertToHexCoords:function (xpixel, ypixel) {
        var xSection = Math.floor(xpixel / ( this.Renderer.HEXWIDTH )),
            ySection = Math.floor(ypixel / ( this.Renderer.HEXHEIGHT )),
            xSectionPixel = Math.floor(xpixel % ( this.Renderer.HEXWIDTH )),
            ySectionPixel = Math.floor(ypixel % ( this.Renderer.HEXHEIGHT )),
            m = this.Renderer.h / this.Renderer.r, //slope of Hex points
            ArrayX = xSection,
            ArrayY = ySection,
            SectionType = 'A';
        if (ySection % 2 == 0) {
            /******************
             * http://www.gamedev.net/page/resources/_/technical/game-programming/coordinates-in-hexagon-based-tile-maps-r1800
             * Type A Section
             *************
             *     *     *
             *   *   *   *
             * *       * *
             * *       * *
             *************
             * If the pixel position in question lies within the big bottom area the array coordinate of the
             *      tile is the same as the coordinate of our section.
             * If the position lies within the top left edge we have to subtract one from the horizontal (x)
             *      and the vertical (y) component of our section coordinate.
             * If the position lies within the top right edge we reduce only the vertical component.
             ******************/
            if (ySectionPixel < (this.Renderer.h - xSectionPixel * m)) {// left Edge
                ArrayY = ySection - 1;
                ArrayX = xSection - 1;
            } else if (ySectionPixel < (-this.Renderer.h + xSectionPixel * m)) {// right Edge
                ArrayY = ySection - 1;
                ArrayX = xSection;
            }
        } else {
            /******************
             * Type B section
             *********
             * *   * *
             *   *   *
             *   *   *
             *********
             * If the pixel position in question lies within the right area the array coordinate of the
             *      tile is the same as the coordinate of our section.
             * If the position lies within the left area we have to subtract one from the horizontal (x) component
             *      of our section coordinate.
             * If the position lies within the top area we have to subtract one from the vertical (y) component.
             ******************/
            SectionType = 'B';
            if (xSectionPixel >= this.Renderer.r) {//Right side
                if (ySectionPixel < (2 * this.Renderer.h - xSectionPixel * m)) {
                    ArrayY = ySection - 1;
                    ArrayX = xSection;
                } else {
                    ArrayY = ySection;
                    ArrayX = xSection;
                }
            } else {//Left side
                if (ySectionPixel < ( xSectionPixel * m)) {
                    ArrayY = ySection - 1;
                    ArrayX = xSection;
                } else {
                    ArrayY = ySection;
                    ArrayX = xSection - 1;
                }
            }
        }
        return {
            x:ArrayX + this.Main.DrawPosition.x, //Draw position is the "camera" offset
            y:ArrayY + this.Main.DrawPosition.y
        };
    },

Zum Schluss hier ein Screenshot meines Projekts mit aktiviertem Debug des Renderings. Es zeigt die roten Linien, in denen der Code nach TypeA- und TypeB-Zellen sucht, zusammen mit den Hex-Koordinaten und Zellumrissen. Ich Geben Sie hier die Bildbeschreibung ein
hoffe, dies hilft einigen.

user32959
quelle
4

Ich habe tatsächlich eine Lösung ohne Hex-Mathematik gefunden.
Wie ich in der Frage erwähnt habe, speichert jede Zelle ihre eigenen Mittenkoordinaten. Durch Berechnen der Hex-Mitte, die den Pixelkoordinaten am nächsten liegt, kann ich die entsprechende Hex-Zelle mit Pixelgenauigkeit (oder sehr nahe daran) bestimmen.
Ich denke nicht, dass dies der beste Weg ist, da ich zu jeder Zelle iterieren muss und sehen kann, wie anstrengend das sein könnte, aber den Code als alternative Lösung belassen wird:

public HexCell<T> coordsToHexCell(float x, float y){
    HexCell<T> cell;
    HexCell<T> result = null;
    float distance = Float.MAX_VALUE;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            cell = getHexCell(r, c);

            final float dx = x - cell.getX();
            final float dy = y - cell.getY();
            final float newdistance = (float) Math.sqrt(dx*dx + dy*dy);

            if (newdistance < distance) {
                distance = newdistance;
                result = cell;
            }           
        }
    }
    return result;
}
petervaz
quelle
3
Dies ist ein vernünftiger Ansatz. Sie können es beschleunigen, indem Sie einen kleineren Bereich von Zeilen / Spalten scannen, anstatt alle zu scannen. Dazu benötigen Sie eine ungefähre Vorstellung davon, wo sich das Hex befindet. Da Sie versetzte Gitter verwenden, können Sie eine grobe Schätzung erhalten, indem Sie x durch den Abstand zwischen Spalten und y durch den Abstand zwischen Zeilen teilen. Anstatt alle Spalten 0…cols-1und Zeilen zu 0…rows-1scannen, können Sie col_guess - 1 … col_guess+1und scannen row_guess - 1 … row_guess + 1. Das sind nur 9 Felder, also schnell und unabhängig von der Größe der Karte.
Amitp
3

Hier ist der Mut einer C # -Implementierung einer der auf der Amit Patel-Website veröffentlichten Techniken (ich bin sicher, dass das Übersetzen in Java keine Herausforderung darstellt):

public class Hexgrid : IHexgrid {
  /// <summary>Return a new instance of <c>Hexgrid</c>.</summary>
  public Hexgrid(IHexgridHost host) { Host = host; }

  /// <inheritdoc/>
  public virtual Point ScrollPosition { get { return Host.ScrollPosition; } }

/// <inheritdoc/>
public virtual Size  Size           { get { return Size.Ceiling(Host.MapSizePixels.Scale(Host.MapScale)); } }

/// <inheritdoc/>
public virtual HexCoords GetHexCoords(Point point, Size autoScroll) {
  if( Host == null ) return HexCoords.EmptyCanon;

  // Adjust for origin not as assumed by GetCoordinate().
  var grid    = new Size((int)(Host.GridSizeF.Width*2F/3F), (int)Host.GridSizeF.Height);
  var margin  = new Size((int)(Host.MapMargin.Width  * Host.MapScale), 
                         (int)(Host.MapMargin.Height * Host.MapScale));
  point      -= autoScroll + margin + grid;

  return HexCoords.NewCanonCoords( GetCoordinate(matrixX, point), 
                                   GetCoordinate(matrixY, point) );
}

/// <inheritdoc/>
public virtual Point   ScrollPositionToCenterOnHex(HexCoords coordsNewCenterHex) {
  return HexCenterPoint(HexCoords.NewUserCoords(
          coordsNewCenterHex.User - ( new IntVector2D(Host.VisibleRectangle.Size.User) / 2 )
  ));
}

/// <summary>Scrolling control hosting this HexGrid.</summary>
protected IHexgridHost Host { get; private set; }

/// <summary>Matrix2D for 'picking' the <B>X</B> hex coordinate</summary>
Matrix matrixX { 
  get { return new Matrix(
      (3.0F/2.0F)/Host.GridSizeF.Width,  (3.0F/2.0F)/Host.GridSizeF.Width,
             1.0F/Host.GridSizeF.Height,       -1.0F/Host.GridSizeF.Height,  -0.5F,-0.5F); } 
}
/// <summary>Matrix2D for 'picking' the <B>Y</B> hex coordinate</summary>
Matrix matrixY { 
  get { return new Matrix(
            0.0F,                        (3.0F/2.0F)/Host.GridSizeF.Width,
            2.0F/Host.GridSizeF.Height,         1.0F/Host.GridSizeF.Height,  -0.5F,-0.5F); } 
}

/// <summary>Calculates a (canonical X or Y) grid-coordinate for a point, from the supplied 'picking' matrix.</summary>
/// <param name="matrix">The 'picking' matrix</param>
/// <param name="point">The screen point identifying the hex to be 'picked'.</param>
/// <returns>A (canonical X or Y) grid coordinate of the 'picked' hex.</returns>
  static int GetCoordinate (Matrix matrix, Point point){
  var pts = new Point[] {point};
  matrix.TransformPoints(pts);
      return (int) Math.Floor( (pts[0].X + pts[0].Y + 2F) / 3F );
  }

Der Rest des Projekts ist hier als Open Source verfügbar, einschließlich der oben genannten Klassen MatrixInt2D und VectorInt2D:
http://hexgridutilities.codeplex.com/

Obwohl die obige Implementierung für Hexes mit flachen Spitzen gilt, enthält die HexgridUtilities-Bibliothek die Option, das Gitter zu transponieren.

Pieter Geerkens
quelle
0

Ich habe einen einfachen, alternativen Ansatz gefunden, der dieselbe Logik wie ein normales Schachbrett verwendet. Es wird ein Rastereffekt mit Punkten in der Mitte jeder Kachel und an jedem Scheitelpunkt erstellt (indem ein engeres Raster erstellt und abwechselnde Punkte ignoriert werden).

Dieser Ansatz eignet sich gut für Spiele wie Catan, bei denen Spieler mit Kacheln und Scheitelpunkten interagieren. Er eignet sich jedoch nicht für Spiele, bei denen Spieler nur mit Kacheln interagieren, da er zurückgibt, welchem ​​Mittelpunkt oder Scheitelpunkt die Koordinaten am nächsten liegen und nicht welcher sechseckigen Kachel Koordinaten sind innerhalb.

Die Geometrie

Wenn Sie Punkte in einem Raster mit Spalten platzieren, die viertel der Breite einer Kachel entsprechen, und Zeilen, die die halbe Höhe einer Kachel haben, erhalten Sie folgendes Muster:

wie oben beschrieben

Wenn Sie dann den Code so ändern, dass jeder zweite Punkt in einem Schachbrettmuster übersprungen wird (Überspringen if column % 2 + row % 2 == 1), erhalten Sie folgendes Muster:

wie oben beschrieben

Implementierung

Unter Berücksichtigung dieser Geometrie können Sie ein 2D-Array erstellen (genau wie bei einem quadratischen Raster) und die x, yKoordinaten für jeden Punkt im Raster (aus dem ersten Diagramm) speichern - ungefähr so:

points = []
for x in numberOfColumns
    points.push([])
    for y in numberOfRows
        points[x].push({x: x * widthOfColumn, y: y * heightOfRow})

Hinweis: Wenn Sie ein Raster um die Punkte erstellen (anstatt Punkte an den Punkten selbst zu platzieren), müssen Sie wie gewohnt den Ursprung versetzen (indem Sie die Hälfte der Breite einer Spalte von xund die Hälfte der Höhe einer Zeile von subtrahieren y).

Nachdem Sie Ihr 2D-Array ( points) initialisiert haben, können Sie den Punkt finden, der der Maus am nächsten liegt, genau wie in einem quadratischen Raster. Sie müssen nur jeden anderen Punkt ignorieren, um das Muster im zweiten Diagramm zu erstellen:

column, row = floor(mouse.x / columnWidth), floor(mouse.y / rowHeight)
point = null if column % 2 + row % 2 != 1 else points[column][row]

Das wird funktionieren, aber die Koordinaten werden auf den nächsten Punkt (oder keinen Punkt) gerundet, basierend auf dem unsichtbaren Rechteck, in dem sich der Zeiger befindet. Sie möchten wirklich eine kreisförmige Zone um den Punkt (also ist der Fangbereich in jeder Richtung gleich). Nachdem Sie nun wissen, welchen Punkt Sie überprüfen müssen, können Sie die Entfernung leicht ermitteln (mithilfe des Satzes von Pythagoras). Der implizite Kreis müsste immer noch in das ursprüngliche Begrenzungsrechteck passen und seinen maximalen Durchmesser auf die Breite einer Säule (Viertel der Breite einer Kachel) beschränken, aber das ist immer noch groß genug, um in der Praxis gut zu funktionieren.

Carl Smith
quelle