Sechseckige Fliesen und Finden ihrer angrenzenden Nachbarn

Question

Ich entwickle ein einfaches 2D -Brettspiel mit hexagonalen Fliesenkarten, ich habe mehrere Artikel gelesen (einschließlich der Gameev One, die jedes Mal verknüpft sind, wenn es eine Frage zu sechseckigen Fliesen gibt), wie man Hexen auf dem Bildschirm zeichnet und wie man verwaltet wird Die Bewegung (obwohl vieles ich bereits zuvor getan hatte). Mein Hauptproblem ist es, die angrenzenden Fliesen auf der Grundlage eines bestimmten Radius zu finden.

So funktioniert mein Kartensystem:

(0,0) (0,1) (0,2) (0,3) (0,4)
   (1,0) (1,1) (1,2) (1,3) (1,4)
(2,0) (2,1) (2,2) (2,3) (2,4)
   (3,0) (3,1) (3,2) (3,3) (3,4)

etc...

Ich kämpfe mit der Tatsache, dass ich die angrenzenden Kacheln mit Verwendung nicht einfach "auswählen" kann for(x-range;x+range;x++); for(y-range;y+range;y++); Da es unerwünschte Kacheln auswählt (in dem Beispiel, das ich angegeben habe, würde das Auswählen der (1,1) Fliesen und das Angeben eines Bereichs von 1 mir auch die (3,0) Fliese geben (die, die ich tatsächlich sein muss (0,1) ( 0,2) (1,0) (1,2) (2,1) (2,2)), was irgendwie an der Fliese nebeneinander liegt (aufgrund der Art und Weise, wie das Array strukturiert ist), aber es ist nicht wirklich das, was ich will zu wählen. Ich könnte es nur brutal erzwingen, aber das wäre nicht schön und würde wahrscheinlich nicht jeden Aspekt des „Auswählens von Radius -Ding“ abdecken.

Kann mich jemand hier in die richtige Richtung zeigen?

Answer 1

Was ist ein sechseckiges Netz?

Was Sie oben sehen können, sind die beiden Gitter. Es ist alles in der Art und Weise, wie Sie Ihre Fliesen nummerieren und wie Sie verstehen, was für ein sechseckiges Netz ist. So wie ich es sehe, ist ein hexagonales Raster nichts anderes als ein deformiertes orthogonales.

Die beiden Sechskantfliesen, die ich in Lila eingekreist, sind theoretisch immer noch neben 0,0. Aufgrund der Verformung, die wir durchlaufen haben, um das Hex-Fliesen-Gitter von den orthogonalen zu erhalten, sind die beiden nicht mehr visuell benachbart.

Verformung

Was wir verstehen müssen, ist, dass die Verformung in einer bestimmten Richtung entlang a geschehen ist [(-1,1) (1,-1)] imaginäre Linie in meinem Beispiel. Um genauer zu sein, ist es, als wäre das Netz entlang dieser Linie verlängert worden, und gequetscht entlang einer Linie senkrecht. Natürlich haben sich die beiden Kacheln in dieser Linie verteilt und sind nicht mehr visuell nebeneinander. Umgekehrt die Fliesen (1, 1) und (-1, -1) die diagonal waren (0, 0) sind jetzt ungewöhnlich nahe da (0, 0), so nah in der Tat, dass sie jetzt sind visuell nebeneinander zu (0, 0). Mathematisch sind sie jedoch immer noch Diagonale und es hilft, sie in Ihrem Code so zu behandeln.

Auswahl

Das Bild, das ich zeige, zeigt einen Radius von 1. für einen Radius von zwei, werden Sie es bemerken (2, -2) und (-2, 2) sind die Fliesen, die nicht in die Auswahl einbezogen werden sollten. Usw. Also für jede Auswahl an Radius r, die Punkte (r, -r) und (-r, r) sollte nicht ausgewählt werden. Abgesehen davon sollte Ihr Auswahlalgorithmus mit einem Raster mit quadratischem Fliesen gleich sein.

Stellen Sie einfach sicher, dass Ihre Achse ordnungsgemäß auf dem hexagonalen Netz eingerichtet ist und Ihre Fliesen entsprechend nummerieren.

Implementierung

Lassen Sie uns dies für ein bisschen erweitern. Wir wissen jetzt, dass diese Bewegung entlang einer beliebigen Richtung im Netz uns 1. und Bewegung entlang der kostet gestreckt Die Richtung kostet uns 2. Siehe (0, 0) zu (-1, 1) zum Beispiel.

Wenn wir dies wissen, können wir den kürzesten Abstand zwischen zwei Fliesen in einem solchen Gitter berechnen, indem wir den Abstand in zwei Komponenten zersetzen: eine diagonale Bewegung und eine geraden Bewegung entlang einer der Achse. Zum Beispiel für den Abstand zwischen (1, 1) und (-2, 5) In einem normalen Stromnetz haben wir:

Normal distance = (1, 1) - (-2, 5) = (3, -4)

Das wäre der Abstandsvektor zwischen den beiden Kacheln, wenn sie auf einem quadratischen Netz wären. Wir müssen jedoch die Gitterdeformation kompensieren, damit wir uns so zersetzen:

(3, -4) = (3, -3) + (0, -1)

Wie Sie sehen können, haben wir den Vektor in eine diagonale zerlegt (3, -3) und eine Straight entlang einer Achse (0, -1).

Wir prüfen nun, ob sich die diagonale Achse entlang der Verformungsachse befindet (n, -n) wo n ist eine Ganzzahl, die entweder positiv oder negativ sein kann.(3, -3) Erfüllt in der Tat diesen Zustand, so dass dieser diagonale Vektor entlang der Verformung ist. Dies bedeutet, dass die Länge (oder Kosten) dieses Vektors anstatt zu sein 3, es wird doppelt sein, das heißt 6.

Also umzusetzen. Der Abstand zwischen (1, 1) und (-2, 5) ist die Länge von (3, -3) plus die Länge von (0, -1). Das ist distance = 3 * 2 + 1 = 7.

Implementierung in C ++

Nachfolgend finden Sie die Implementierung in C ++ des Algorithmus, den ich oben erklärt habe:

int ComputeDistanceHexGrid(const Point & A, const Point & B)
{
  // compute distance as we would on a normal grid
  Point distance;
  distance.x = A.x - B.x;
  distance.y = A.y - B.y;

  // compensate for grid deformation
  // grid is stretched along (-n, n) line so points along that line have
  // a distance of 2 between them instead of 1

  // to calculate the shortest path, we decompose it into one diagonal movement(shortcut)
  // and one straight movement along an axis
  Point diagonalMovement;
  int lesserCoord = abs(distance.x) < abs(distance.y) ? abs(distance.x) : abs(distance.y);
  diagonalMovement.x = (distance.x < 0) ? -lesserCoord : lesserCoord; // keep the sign 
  diagonalMovement.y = (distance.y < 0) ? -lesserCoord : lesserCoord; // keep the sign

  Point straightMovement;

  // one of x or y should always be 0 because we are calculating a straight
  // line along one of the axis
  straightMovement.x = distance.x - diagonalMovement.x;
  straightMovement.y = distance.y - diagonalMovement.y;

  // calculate distance
  size_t straightDistance = abs(straightMovement.x) + abs(straightMovement.y);
  size_t diagonalDistance = abs(diagonalMovement.x);

  // if we are traveling diagonally along the stretch deformation we double
  // the diagonal distance
  if ( (diagonalMovement.x < 0 && diagonalMovement.y > 0) || 
       (diagonalMovement.x > 0 && diagonalMovement.y < 0) )
  {
    diagonalDistance *= 2;
  }

  return straightDistance + diagonalDistance;
}

Nun angesichts der oben genannten implementierten ComputeDistanceHexGrid Funktion können Sie jetzt eine naive, nicht optimierte Implementierung eines Auswahlalgorithmus haben, der alle Kacheln weiter ignoriert als der angegebene Auswahlbereich:

int _tmain(int argc, _TCHAR* argv[])
{
  // your radius selection now becomes your usual orthogonal algorithm
  // except you eliminate hex tiles too far away from your selection center
  // for(x-range;x+range;x++); for(y-range;y+range;y++);
  Point selectionCenter = {1, 1};
  int range = 1;

  for ( int x = selectionCenter.x - range;
            x <= selectionCenter.x + range;
            ++x )
  {
    for ( int y = selectionCenter.y - range;
              y <= selectionCenter.y + range;
              ++y )
    {
      Point p = {x, y};
      if ( ComputeDistanceHexGrid(selectionCenter, p) <= range )
        cout << "(" << x << ", " << y << ")" << endl;
      else
      {
        // do nothing, skip this tile since it is out of selection range
      }
    }
  }

    return 0;
}

Für einen Auswahlpunkt (1, 1) und eine Reihe von 1, Der obige Code zeigt das erwartete Ergebnis an:

(0, 0)
(0, 1)
(1, 0)
(1, 1)
(1, 2)
(2, 1)
(2, 2)

Mögliche Optimierung

Um dies zu optimieren, können Sie die Logik einschließen, zu wissen, wie weit eine Fliese vom Auswahlpunkt entfernt sind (Logik in ComputeDistanceHexGrid) Direkt in Ihre Auswahlschleife, sodass Sie das Gitter auf eine Weise itererieren können, die insgesamt außerhalb von Reichweite ausgeht.

Answer 2

Die einfachste Methode kann ich mir vorstellen ...

minX = x-range; maxX = x+range
select (minX,y) to (maxX, y), excluding (x,y) if that's what you want to do
for each i from 1 to range:
    if y+i is odd then maxX -= 1, otherwise minX += 1
    select (minX, y+i) to (maxX, y+i)
    select (minX, y-i) to (maxX, y-i)

Es kann ein wenig abgehen; Ich habe es gerade in meinem Kopf durchgearbeitet. Aber zumindest ist es eine Vorstellung davon, was Sie tun müssen.

In C'ish:

void select(int x, int y) { /* todo: implement this */ }

void selectRange(int x, int y, int range)
{
    int minX = x - range, maxX = x + range;
    for (int i = minX; i <= maxX; ++i)
        if (i != x) select(i, y);
    for (int yOff = 1; yOff <= range; ++yOff)
    {
        if (y+yOff % 2 == 1) --maxX; else ++minX;
        for (int i=minX; i<=maxX; ++i)
        {
            select(i, y+yOff);  select(i, y-yOff);
        }
    }  
}