Jak przedstawić siatkę hextile / hex w pamięci?

Powiedzmy, że tworzę grę planszową z hextile grid, na przykład Settlers of Catan :

Zwróć uwagę, że każdy wierzchołek i krawędź mogą mieć atrybut (droga i osada powyżej).

Jak mógłbym stworzyć strukturę danych reprezentującą tę tablicę? Jakie są wzory dostępu do sąsiadów, krawędzi i wierzchołków każdego kafelka?

Amit Patel opublikował niesamowitą stronę na ten temat. Jest tak obszerna i cudowna, że ​​musi być ostateczną odpowiedzią na to pytanie: siatki sześciokątne

Taką siatkę można przedstawić w postaci dwuwymiarowej tablicy:

Jeśli

   2
7     3
   1   
6     4
   5

jest numerem jeden z jego sąsiadami w siatce heksadecymalnej, możesz to umieścić w tablicy 2D w następujący sposób:

2 3
7 1 4
  6 5

Oczywiście sąsiedztwo jest określane w tej siatce nie tylko przez to, że sąsiaduje w poziomie lub w pionie, ale także na podstawie jednej przekątnej.

Możesz jednak użyć wykresu, jeśli chcesz.

W tym artykule opisano, jak skonfigurować grę z siatką izomeryczną / sześciokątną. Polecam zajrzeć do Forcing Isometric and Hexagonal Maps onto a Rectangular Gridsekcji i sekcji ruchu. Chociaż różni się od tego, czego szukasz, może pomóc ci sformułować, jak robić to, co chcesz.

Dużo zajmowałem się klątwami. W takich przypadkach śledzisz każdy z 6 punktów dla granic heksa. Pozwala to dość łatwo go narysować.

Będziesz mieć pojedynczą tablicę obiektów reprezentujących heksy. Każdy z tych obiektów heksadecymalnych ma również 6 „wskaźników” (lub indeks do innej tablicy) wskazujących na inną tablicę „boków”. To samo dotyczy „wierzchołków”. Oczywiście wierzchołki miałyby 3 wskaźniki do sąsiednich heksów, a boki miałyby 2.

Zatem hex może być czymś w rodzaju: X, Y, Point (6), Vertices (6), Sides (6)

Następnie masz tablicę Hex, tablicę wierzchołków i tablicę boczną.

Wtedy bardzo łatwo jest znaleźć wierzchołki / boki dla hexa lub czegokolwiek.

Kiedy mówię pointer, równie łatwo może to być liczba całkowita wskazująca na element w tablicy wierzchołków lub bocznych lub cokolwiek innego. I oczywiście tablice mogą być listami lub czymkolwiek.

   2
7     3
   1   
6     4
   5

Możesz także spróbować „spłaszczyć” wiersze mapy. W tym przykładzie byłoby to:

  2
7 1 3
6 5 4

Czasami bardziej przydatne jest umieszczanie wierszy w jednym wierszu: P

Sugerowałbym coś takiego (użyję deklaracji w stylu 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;

Każdy heks ma sześć krawędzi i sześć wierzchołków. Każda krawędź śledzi dwa sąsiednie heksy, a każdy wierzchołek śledzi jego trzy sąsiednie heksy (heksy na krawędziach mapy będą przypadkiem specjalnym).

Oczywiście jest wiele rzeczy, które możesz zrobić w inny sposób. Możesz użyć wskaźników zamiast tablic, możesz użyć obiektów zamiast rekordów i możesz przechowywać swoje heksy w dwuwymiarowej tablicy, jak sugerowali inni respondenci.

Miejmy nadzieję, że może to dać ci kilka pomysłów na temat jednego ze sposobów podejścia.

Zaimplementowaliśmy AI Settlers of Catan dla projektu klasowego i zmodyfikowaliśmy kod z tej odpowiedzi (który był błędny), aby stworzyć tablicę ze stałym, losowym dostępem do wierzchołków i krawędzi. To był fajny problem, ale tablica zajęła dużo czasu, więc na wypadek, gdyby ktoś nadal szukał prostej implementacji, oto nasz kod w Pythonie:

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

Siedzę tu „w wolnym czasie programując dla zabawy” z heksami. I wygląda to tak ... Opowiem wam słowami, jak to wygląda.

1. Sześciokąt: ma sześć sąsiadujących sześciokątów. Może dostarczyć odniesienie do każdego sąsiedniego pola heksów. Potrafi powiedzieć, z czego się składa (woda, skała, pył). Może łączyć się z innymi i odwrotnie. Może nawet automatycznie łączyć inne, które go otaczają, aby stworzyć większe pole i / lub upewnić się, że wszystkie pola mogą być zajęte przez jego sąsiadów.
2. Budynek odnosi się do trzech dróg i trzech heksów. Mogą ci powiedzieć, kim oni są.
3. Droga odnosi się do dwóch heksów i innych dróg, gdy są skierowane przez sąsiednie kafelki. Potrafią określić, które to kafelki iz którymi drogami lub budynkami się łączą.

To tylko pomysł, jak bym nad tym pracował.

Możesz utworzyć tablicę 2D, a następnie rozważyć prawidłowe pozycje jako:

• W wierszach o numerach parzystych (0,2,4, ...): komórki o numerach nieparzystych.
• W wierszach o numerach nieparzystych (1, 3, 5, ...): komórki o numerach parzystych.

W przypadku każdej komórki sąsiadami byłyby:

• Ta sama kolumna, 2 wiersze w górę
• Ta sama kolumna, 2 wiersze w dół
• 1 w lewo + 1 w górę
• 1 w lewo + 1 w dół
• 1 w prawo + 1 w górę
• 1 w prawo + 1 w dół

Ilustracja: Siatka sześciokątna

Znaki x to heksy. x, które są ukośnie względem siebie, są sąsiadami. | łączy pionowych sąsiadów.