Comment représenter une grille hextile / hex en mémoire?

Disons que je construis un jeu de société avec une grille hextile, comme Settlers of Catan :

Notez que chaque sommet et chaque arête peuvent avoir un attribut (une route et un règlement au-dessus).

Comment créer une structure de données qui représente ce tableau? Quels sont les modèles d'accès aux voisins, arêtes et sommets de chaque tuile?

Amit Patel a publié une page incroyable sur ce sujet. C'est tellement complet et merveilleux qu'il doit être la réponse définitive à cette question: Grilles hexagonales

Une telle grille peut être représentée dans un tableau à deux dimensions:

Si

   2
7     3
   1   
6     4
   5

est le numéro un avec ses voisins dans la grille hexadécimale, alors vous pouvez le mettre dans un tableau 2D comme ceci:

2 3
7 1 4
  6 5

Évidemment, la voisinage est déterminée dans cette grille non seulement en étant adjacente horizontalement ou verticalement mais aussi en utilisant une diagonale.

Cependant, vous pouvez également utiliser un graphique si vous le souhaitez.

Cet article explique comment configurer un jeu de grille isomérique / hexagonale. Je vous recommande de jeter un œil à la Forcing Isometric and Hexagonal Maps onto a Rectangular Gridsection et à la section mouvement. Bien qu'il soit différent de ce que vous recherchez, il peut vous aider à formuler comment faire ce que vous voulez.

J'ai beaucoup traité de maléfices. Dans de tels cas, vous suivez chacun des 6 points pour les frontières de l'hex. Cela vous permet de le dessiner assez facilement.

Vous auriez un seul tableau d'objets qui représentent des hexagones. Chacun de ces objets hexadécimaux possède également 6 "pointeurs" (ou un index vers un autre tableau) pointant vers un autre tableau de "côtés". Même chose pour les "sommets". Bien sûr, les sommets auraient 3 pointeurs vers les hexagones adjacents, et les côtés en auraient 2.

Ainsi, un hexagone peut être quelque chose comme: X, Y, Point (6), Vertices (6), Sides (6)

Ensuite, vous avez un tableau Hex, un tableau de sommets et un tableau latéral.

Ensuite, il est assez simple de trouver les sommets / côtés d'un hexagone, ou autre.

Quand je dis pointeur, cela pourrait tout aussi bien être un entier pointant vers l'élément dans le sommet ou le tableau latéral ou autre. Et bien sûr, les tableaux peuvent être des listes ou autre.

   2
7     3
   1   
6     4
   5

Vous pouvez également essayer de «mettre à plat» les lignes de votre carte. Pour cet exemple, ce serait:

  2
7 1 3
6 5 4

Il est parfois plus utile d'avoir des lignes sur une seule ligne: P

Je suggérerais quelque chose comme ce qui suit (j'utiliserai des déclarations de style Delphi):

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;

Chaque hexagone a six arêtes et six sommets. Chaque bord garde la trace de ses deux hexs adjacents, et chaque sommet garde la trace de ses trois hexs adjacents (les hexagones sur les bords de la carte seront un cas particulier).

Il y a beaucoup de choses que vous pourriez faire d'une manière différente bien sûr. Vous pouvez utiliser des pointeurs plutôt que des tableaux, vous pouvez utiliser des objets plutôt que des enregistrements, et vous pouvez stocker vos hexagones dans un tableau à deux dimensions, comme d'autres répondants l'ont suggéré.

J'espère que cela pourrait vous donner quelques idées sur une façon de l'aborder.

Nous avons implémenté une IA Settlers of Catan pour un projet de classe et modifié le code de cette réponse (qui était boguée) pour créer un tableau avec un accès aléatoire en temps constant aux sommets et aux arêtes. C'était un problème amusant, mais le tableau a pris beaucoup de temps, donc au cas où quelqu'un chercherait encore une implémentation simple, voici notre code Python:

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

Je suis assis ici "dans mon temps libre à coder pour le plaisir" avec des hexagones. Et ça va comme ça ... Je vais vous dire à quoi ça ressemble en mots.

1. Hexagone: il a six hexagones voisins. Il peut fournir la référence pour chaque tuile hexagonale voisine. Il peut vous dire en quoi il consiste (eau, roche, poussière). Il peut se connecter aux autres et vice versa. Il peut même connecter automatiquement les autres qui l'entourent pour créer un champ plus grand et / ou s'assurer que tous les champs peuvent être adressés par ses voisins.
2. Un bâtiment fait référence jusqu'à trois routes et trois tuiles hexagonales. Ils peuvent vous dire lesquels ils sont.
3. Une route fait référence à deux hexagones et à d'autres routes lorsqu'elles sont adressées par des tuiles voisines. Ils peuvent dire quelles tuiles sont et à quelles routes ou bâtiments ils se connectent.

C'est juste une idée de la façon dont je travaillerais dessus.

Vous pouvez créer un tableau 2D et considérer les positions valides comme:

• Sur les lignes paires (0,2,4, ...): les cellules impaires.
• Sur les lignes impaires (1,3,5, ...): les cellules paires.

Pour chaque cellule, ses voisins seraient:

• Même colonne, 2 lignes plus haut
• Même colonne, 2 lignes vers le bas
• 1 gauche + 1 haut
• 1 gauche + 1 bas
• 1 droite + 1 haut
• 1 droite + 1 bas

Illustration: grille hexagonale

Les marques x sont des hexagones. x qui sont en diagonale les uns par rapport aux autres sont voisins. | relie les voisins verticaux.