Wie stelle ich ein Hextil / Hex-Gitter im Speicher dar?

118

Angenommen, ich baue ein Brettspiel mit einem Hextilgitter wie Settlers of Catan :

Gehostet von imgur.com

Beachten Sie, dass jeder Scheitelpunkt und jede Kante ein Attribut haben kann (eine Straße und eine Siedlung oben).

Wie würde ich eine Datenstruktur erstellen, die diese Karte darstellt? Welche Muster gibt es für den Zugriff auf die Nachbarn, Kanten und Eckpunkte der einzelnen Kacheln?

ein bezahlter Nerd
quelle
Sie können auch eine Hilbert-Kurve verwenden. Dabei handelt es sich um Abstandskurven, sodass die Nachbarschaft in der Ebene in einer linearen Codierung erhalten bleibt. Schauen Sie sich die räumliche Indizierung an und wie diese verwendet werden! v interessant
pbordeaux

Antworten:

155

Amit Patel hat eine erstaunliche Seite zu diesem Thema gepostet . Es ist so umfassend und wunderbar, dass es die endgültige Antwort auf diese Frage sein muss: Sechseckige Gitter

cubez

ein bezahlter Nerd
quelle
27
Danke :) Diese Seite behandelt keine Kanten und Eckpunkte, aber ich beschreibe sie im Abschnitt "Beziehungen zwischen Teilen" meines Grids-Artikels unter www-cs-students.stanford.edu/~amitp/game-programming/grids (die Diagramme sind für quadratische Gitter, aber die Tabelle enthält auch die Formeln für axiale Sechskantgitter)
amitp
18

Ein solches Gitter kann in einem zweidimensionalen Array dargestellt werden:

Wenn

   2
7     3
   1   
6     4
   5

ist die Nummer eins mit ihren Nachbarn im Hex-Raster, dann können Sie dies wie folgt in ein 2D-Array einfügen:

2 3
7 1 4
  6 5

Offensichtlich wird die Nachbarschaft in diesem Gitter nicht nur dadurch bestimmt, dass sie horizontal oder vertikal benachbart ist, sondern auch unter Verwendung einer Diagonale.

Sie können jedoch auch ein Diagramm verwenden, wenn Sie möchten.

Joey
quelle
Cool. Was ist mit Daten für Kanten und Eckpunkte?
Ein bezahlter Nerd
1
Ich würde sie wahrscheinlich separat aufbewahren. Unabhängig davon, ob Sie hauptsächlich die Kacheln oder die Kanten / Eckpunkte betrachten, ist die andere Hälfte der Daten entweder schmerzhaft oder überflüssig zu speichern.
Joey
Siehe Amit Patels Artikel in der Antwort "Ein bezahlter Nerd".
Aredridel
11

In diesem Artikel wird beschrieben, wie Sie ein isomeres / hexagonales Rasterspiel einrichten. Ich empfehle Ihnen, sich den Forcing Isometric and Hexagonal Maps onto a Rectangular GridAbschnitt und den Bewegungsabschnitt anzusehen . Obwohl es sich von dem unterscheidet, wonach Sie suchen, kann es Ihnen helfen, zu formulieren, wie Sie das tun, was Sie wollen.

zfedoran
quelle
2

Ich habe mich viel mit Hexen beschäftigt. In solchen Fällen verfolgen Sie jeden der 6 Punkte für die Ränder des Hexfelds. Auf diese Weise können Sie es ganz einfach zeichnen.

Sie hätten ein einzelnes Array von Objekten, die Hexes darstellen. Jedes dieser Hex-Objekte hat auch 6 "Zeiger" (oder einen Index auf ein anderes Array), die auf ein anderes Array von "Seiten" zeigen. Gleiches gilt für "Eckpunkte". Natürlich hätten die Eckpunkte 3 Zeiger auf die angrenzenden Felder, und die Seiten hätten 2.

Ein Hex kann also so etwas wie X, Y, Punkt (6), Eckpunkte (6), Seiten (6) sein.

Dann haben Sie ein Hex-Array, ein Vertice-Array und ein Side-Array.

Dann ist es ziemlich einfach, die Eckpunkte / Seiten für ein Hex oder was auch immer zu finden.

Wenn ich Zeiger sage, kann es genauso gut eine Ganzzahl sein, die auf das Element im Scheitelpunkt oder im Seitenarray oder was auch immer zeigt. Und natürlich können Arrays Listen sein oder was auch immer.

Niemand Besonderes
quelle
0
   2
7     3
   1   
6     4
   5

Sie können auch versuchen, Zeilen Ihrer Karte "flach" zu machen. Für dieses Beispiel wäre es:

  2
7 1 3
6 5 4

Es ist manchmal nützlicher, Zeilen in einer Zeile zu haben: P.

qba
quelle
1
Dies kann einen unordentlichen Code zur Überprüfung von Nachbarn enthalten, da beispielsweise 1 und 6 Nachbarn sind, 3 und 5 jedoch nicht, sie jedoch dieselben relativen Positionen haben.
Bernhard Barker
0

Ich würde Folgendes vorschlagen (ich verwende Deklarationen im Delphi-Stil):

type
  THexEdge = record
    Hexes: array[1..2] of Integer; // Index of adjoining hexes.
    // Other edge stuff goes here.
  end;

  THexVertex = record
    Hexes: array[1..3] of Integer; // Index of adjoining hexes.
    // Other vertex stuff goes here.
  end;

  THex = record
    Edges: array[1..6] of Integer; // Index of edge.
    Vertices: array[1..6] of Integer; // Index of vertex.
    // Other hex stuff goes here.
  end;

var
  Edges: array of THexEdge;
  Vertices: array of THexVertex;
  HexMap: array of THex;

Jedes Hex hat sechs Kanten und sechs Eckpunkte. Jede Kante verfolgt die beiden benachbarten Felder, und jeder Scheitelpunkt verfolgt die drei benachbarten Felder (Hexfelder an den Kanten der Karte sind ein Sonderfall).

Es gibt viele Dinge, die Sie natürlich anders machen könnten. Sie könnten Zeiger anstelle von Arrays verwenden, Sie könnten Objekte anstelle von Datensätzen verwenden und Sie könnten Ihre Hexes in einem zweidimensionalen Array speichern, wie andere Antwortende vorgeschlagen haben.

Hoffentlich gibt Ihnen das einige Ideen, wie Sie es angehen können.

Unglaublicher Mönch
quelle
0

Wir haben einen Siedler von Catan AI für ein Klassenprojekt implementiert und den Code aus dieser Antwort (die fehlerhaft war) geändert , um ein Board mit konstantem zeitlich zufälligem Zugriff auf Eckpunkte und Kanten zu erstellen. Es war ein lustiges Problem, aber das Board hat viel Zeit in Anspruch genommen. Für den Fall, dass noch jemand nach einer einfachen Implementierung sucht, ist hier unser Python-Code:

class Board:
  # Layout is just a double list of Tiles, some will be None
  def __init__(self, layout=None):
    self.numRows = len(layout)
    self.numCols = len(layout[0])
    self.hexagons = [[None for x in xrange(self.numCols)] for x in xrange(self.numRows)] 
    self.edges = [[None for x in xrange(self.numCols*2+2)] for x in xrange(self.numRows*2+2)] 
    self.vertices = [[None for x in xrange(self.numCols*2+2)] for x in xrange(self.numRows*2+2)] 
    for row in self.hexagons:
      for hexagon in row:
        if hexagon == None: continue
        edgeLocations = self.getEdgeLocations(hexagon)
        vertexLocations = self.getVertexLocations(hexagon)
        for xLoc,yLoc in edgeLocations:
          if self.edges[xLoc][yLoc] == None:
            self.edges[xLoc][yLoc] = Edge(xLoc,yLoc)
        for xLoc,yLoc in vertexLocations:
          if self.vertices[xLoc][yLoc] == None:
            self.vertices[xLoc][yLoc] = Vertex(xLoc,yLoc)

  def getNeighborHexes(self, hex):
    neighbors = []
    x = hex.X
    y = hex.Y
    offset = 1
    if x % 2 != 0:
      offset = -1

    if (y+1) < len(self.hexagons[x]):
      hexOne = self.hexagons[x][y+1]
      if hexOne != None: neighbors.append(hexOne)
    if y > 0:
      hexTwo = self.hexagons[x][y-1]
      if hexTwo != None: neighbors.append(hexTwo)
    if (x+1) < len(self.hexagons):
      hexThree = self.hexagons[x+1][y]
      if hexThree != None: neighbors.append(hexThree)
    if x > 0:
      hexFour = self.hexagons[x-1][y]
      if hexFour != None: neighbors.append(hexFour)
    if (y+offset) >= 0 and (y+offset) < len(self.hexagons[x]):
      if (x+1) < len(self.hexagons):
        hexFive = self.hexagons[x+1][y+offset]
        if hexFive != None: neighbors.append(hexFive)
      if x > 0:
        hexSix = self.hexagons[x-1][y+offset]
        if hexSix != None: neighbors.append(hexSix)
    return neighbors

  def getNeighborVertices(self, vertex):
    neighbors = []
    x = vertex.X
    y = vertex.Y
    offset = -1
    if x % 2 == y % 2: offset = 1
    # Logic from thinking that this is saying getEdgesOfVertex
    # and then for each edge getVertexEnds, taking out the three that are ==vertex
    if (y+1) < len(self.vertices[0]):
      vertexOne = self.vertices[x][y+1]
      if vertexOne != None: neighbors.append(vertexOne)
    if y > 0:
      vertexTwo = self.vertices[x][y-1]
      if vertexTwo != None: neighbors.append(vertexTwo)
    if (x+offset) >= 0 and (x+offset) < len(self.vertices):
      vertexThree = self.vertices[x+offset][y]
      if vertexThree != None: neighbors.append(vertexThree)
    return neighbors

  # used to initially create vertices
  def getVertexLocations(self, hex):
    vertexLocations = []
    x = hex.X
    y = hex.Y
    offset = x % 2
    offset = 0-offset
    vertexLocations.append((x, 2*y+offset))
    vertexLocations.append((x, 2*y+1+offset))
    vertexLocations.append((x, 2*y+2+offset))
    vertexLocations.append((x+1, 2*y+offset))
    vertexLocations.append((x+1, 2*y+1+offset))
    vertexLocations.append((x+1, 2*y+2+offset))
    return vertexLocations

  # used to initially create edges
  def getEdgeLocations(self, hex):
    edgeLocations = []
    x = hex.X
    y = hex.Y
    offset = x % 2
    offset = 0-offset
    edgeLocations.append((2*x,2*y+offset))
    edgeLocations.append((2*x,2*y+1+offset))
    edgeLocations.append((2*x+1,2*y+offset))
    edgeLocations.append((2*x+1,2*y+2+offset))
    edgeLocations.append((2*x+2,2*y+offset))
    edgeLocations.append((2*x+2,2*y+1+offset))
    return edgeLocations

  def getVertices(self, hex):
    hexVertices = []
    x = hex.X
    y = hex.Y
    offset = x % 2
    offset = 0-offset
    hexVertices.append(self.vertices[x][2*y+offset]) # top vertex
    hexVertices.append(self.vertices[x][2*y+1+offset]) # left top vertex
    hexVertices.append(self.vertices[x][2*y+2+offset]) # left bottom vertex
    hexVertices.append(self.vertices[x+1][2*y+offset]) # right top vertex
    hexVertices.append(self.vertices[x+1][2*y+1+offset]) # right bottom vertex
    hexVertices.append(self.vertices[x+1][2*y+2+offset]) # bottom vertex
    return hexVertices

  def getEdges(self, hex):
    hexEdges = []
    x = hex.X
    y = hex.Y
    offset = x % 2
    offset = 0-offset
    hexEdges.append(self.edges[2*x][2*y+offset])
    hexEdges.append(self.edges[2*x][2*y+1+offset])
    hexEdges.append(self.edges[2*x+1][2*y+offset])
    hexEdges.append(self.edges[2*x+1][2*y+2+offset])
    hexEdges.append(self.edges[2*x+2][2*y+offset])
    hexEdges.append(self.edges[2*x+2][2*y+1+offset])
    return hexEdges

  # returns (start, end) tuple
  def getVertexEnds(self, edge):
    x = edge.X
    y = edge.Y
    vertexOne = self.vertices[(x-1)/2][y]
    vertexTwo = self.vertices[(x+1)/2][y]
    if x%2 == 0:
      vertexOne = self.vertices[x/2][y]
      vertexTwo = self.vertices[x/2][y+1]
    return (vertexOne, vertexTwo)

  def getEdgesOfVertex(self, vertex):
    vertexEdges = []
    x = vertex.X
    y = vertex.Y
    offset = -1
    if x % 2 == y % 2: offset = 1
    edgeOne = self.edges[x*2][y-1]
    edgeTwo = self.edges[x*2][y]
    edgeThree = self.edges[x*2+offset][y]
    if edgeOne != None: vertexEdges.append(edgeOne)
    if edgeTwo != None: vertexEdges.append(edgeTwo)
    if edgeThree != None: vertexEdges.append(edgeThree)
    return vertexEdges

  def getHexes(self, vertex):
    vertexHexes = []
    x = vertex.X
    y = vertex.Y
    xOffset = x % 2
    yOffset = y % 2

    if x < len(self.hexagons) and y/2 < len(self.hexagons[x]):
      hexOne = self.hexagons[x][y/2]
      if hexOne != None: vertexHexes.append(hexOne)

    weirdX = x
    if (xOffset+yOffset) == 1: weirdX = x-1
    weirdY = y/2 
    if yOffset == 1: weirdY += 1
    else: weirdY -= 1
    if weirdX >= 0 and weirdX < len(self.hexagons) and weirdY >= 0 and weirdY < len(self.hexagons):
      hexTwo = self.hexagons[weirdX][weirdY]
      if hexTwo != None: vertexHexes.append(hexTwo)

    if x > 0 and x < len(self.hexagons) and y/2 < len(self.hexagons[x]):
      hexThree = self.hexagons[x-1][y/2]
      if hexThree != None: vertexHexes.append(hexThree)

    return vertexHexes
Ghopper
quelle
Diese Antwort ist schrecklich. Sie haben gerade Tonnen von Code eingefügt, ohne etwas zu erklären (außer wer den Code geschrieben hat). Auch wenn das hier in Ordnung war, ist der Code selbst schrecklich. Es gibt keine Dokumentzeichenfolgen, fast keine Kommentare, und die wenigen enthaltenen Kommentare sind unverständlich (Logik aus dem Gedanken, dass dies getEdgesOfVertex bedeutet, und dann für jede Kante getVertexEnds, die drei herausnehmen, die == Vertex sind).
Carl Smith
0

Ich sitze hier "in meiner Freizeit zum Spaß" mit Hexen. Und es geht so ... Ich werde Ihnen sagen, wie es in Worten aussieht.

  1. Sechseck: Es hat sechs benachbarte Sechsecke. Es kann die Referenz für jede benachbarte Hex-Kachel liefern. Es kann Ihnen sagen, woraus es besteht (Wasser, Stein, Staub). Es kann sich mit anderen verbinden und umgekehrt. Es kann sogar automatisch die anderen um ihn herum verbinden, um ein größeres Feld zu erstellen und sicherzustellen, dass alle Felder von seinen Nachbarn adressiert werden können.
  2. Ein Gebäude verweist auf bis zu drei Straßen und drei Hex-Kacheln. Sie können Ihnen sagen, was sie sind.
  3. Eine Straße verweist auf zwei Felder und andere Straßen, wenn sie von benachbarten Kacheln angesprochen werden. Sie können erkennen, um welche Kacheln es sich handelt und mit welchen Straßen oder Gebäuden sie verbunden sind.

Dies ist nur eine Idee, wie ich daran arbeiten würde.

Raphael Denken
quelle
0

Sie können ein 2D-Array erstellen und dann die gültigen Positionen wie folgt betrachten:

  • In geradzahligen Zeilen (0,2,4, ...): die ungeradzahligen Zellen.
  • In ungeradzahligen Zeilen (1,3,5, ...): die geradzahligen Zellen.

Für jede Zelle wären ihre Nachbarn:

  • Gleiche Spalte, 2 Zeilen höher
  • Gleiche Spalte, 2 Zeilen nach unten
  • 1 übrig + 1 oben
  • 1 links + 1 unten
  • 1 rechts + 1 oben
  • 1 rechts + 1 runter

Abbildung: Hex Grid

Die x-Markierungen sind Hexen. x, die diagonal zueinander sind, sind Nachbarn. | verbindet vertikale Nachbarn.

Yman
quelle