Jak mogę reprezentować siatkę hextile/hex w pamięci?

Question

Say buduję grę planszową z siatką hextile, jak Settlers of Catan:

pamiętać, że każdy wierzchołek i krawędź może mieć atrybut (drogi i rozliczeniu wyżej).

Jak utworzyć strukturę danych reprezentującą tę płytę? Jakie są wzorce dostępu do sąsiadów, krawędzi i wierzchołków poszczególnych płytek?

Answer 1

Amit Patel opublikował na stronie niesamowitą stronę. Jest tak wszechstronny i wspaniałe, że to musi być ostateczna odpowiedź na to pytanie: Hexagonal Grids

Answer 2

Taka siatka może być reprezentowana w dwuwymiarowej tablicy:

If

2 
7  3 
    1 
6  4 
    5 

jest numerem jeden z jego sąsiadów w siatce sześciokątnym, a następnie można umieścić to w 2D tablicy tak:

2 3 
7 1 4 
    6 5 

Oczywiście sąsiadem Ness określa się tej siatki nie tylko poprzez poziomo lub pionowo, w sąsiedztwie, ale także za pomocą jednej przekątnej.

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

Answer 3

2 
7  3 
    1 
6  4 
    5 

Można także spróbować „płaska” rzędami mapie. W tym przykładzie będzie to:

2 
7 1 3 
6 5 4 

Its czasami bardziej przydatne wiersze w jednym rzędzie: P

Answer 4

This article przechodzi jak założyć izomerycznych/sześciokątne grę siatki. Polecam zapoznać się z sekcją Forcing Isometric and Hexagonal Maps onto a Rectangular Grid i sekcją ruchu. Chociaż różni się od tego, czego szukasz, może pomóc Ci sformułować, jak robić to, co chcesz.

Answer 5

chciałbym zaproponować coś jak następuje (użyję deklaracji Delphi-style):

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 hex ma sześć krawędzi i sześć wierzchołków. Każda krawędź śledzi dwa sąsiednie heksy, a każdy wierzchołek śledzi trzy sąsiednie heksy (heksy na krawędziach mapy będą specjalnym przypadkiem).

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 zapisów i możesz przechowywać swoje heksy w dwuwymiarowej tablicy, jak sugerowali inni.

Mamy nadzieję, że może to dać kilka pomysłów na temat jednego sposobu podejścia.

Answer 6

Mam dużo do czynienia z heksami. W takich przypadkach śledzisz każdy z 6 punktów dla granic heksu. To pozwala na łatwe narysowanie.

Będziesz miał jedną tablicę obiektów reprezentujących heksy. Każdy z tych obiektów szesnastkowych 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.

Tak, hex może być coś takiego: X, Y, pkt (6), Wierzchołki (6), strony (6)

wtedy masz tablicy HEX, tablicę vértice i boczną tablicę.

Wówczas bardzo łatwo jest znaleźć wierzchołki/boki dla heksu lub cokolwiek innego.

Kiedy wypowiadam wskaźnik, równie łatwo może być liczbą całkowitą wskazującą na element w tablicy wierzchołków lub bocznych, czy cokolwiek innego. I oczywiście tablice mogą być listami lub czymkolwiek.

Answer 7

Wdrożyliśmy Osadników z Catanu AI dla projektu klasy i kod modyfikowany this odpowiedzi (który był wadliwy) aby utworzyć planszę ze stałym czasem losowego dostępu do wierzchołków i krawędzi. To był zabawny problem, ale deska zajęła dużo czasu, więc na wypadek, gdyby ktoś nadal szukał prostej implementacji, tutaj jest nasz kod Pythona:

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