Как представить гехетильную/шестнадцатеричную сетку в памяти?

Question

Say Я строй настольной игры с hextile сеткой, как Settlers of Catan:

Обратите внимание, что каждая вершина и ребро могут иметь атрибут (дороги и расчет выше).

Как создать структуру данных, представляющую эту плату? Каковы шаблоны для доступа к соседям, краям и вершинам каждой плитки?

Answer 1

Amit Patel опубликовал удивительный номер на эту тему. Это настолько всеобъемлющим и замечательно, что он должен быть окончательный ответ на этот вопрос: Hexagonal Grids

Answer 2

Такая сетка может быть представлена ​​в виде двухмерного массива:

If

2 
7  3 
    1 
6  4 
    5 

это номер один со своими соседями в шестигранной сетки, то вы можете поместить это в 2D-массив например, так:

2 3 
7 1 4 
    6 5 

Очевидно, что сосед-ность определяется в этой сетке не только быть горизонтально или вертикально смежными, но и с использованием одной диагональной.

Вы также можете использовать график, если хотите.

Answer 3

2 
7  3 
    1 
6  4 
    5 

Вы также можете попробовать «плоские» ряды своей карты. В этом примере это будет:

2 
7 1 3 
6 5 4 

Сво иногда более полезно иметь строки в одну строке: P

Answer 4

This article проходит как настроить изомерную/шестиугольную игру сетки. Я рекомендую вам посмотреть раздел Forcing Isometric and Hexagonal Maps onto a Rectangular Grid и раздел движения. Хотя это отличается от того, что вы ищете, это может помочь вам сформулировать, как делать то, что вы хотите.

Answer 5

Я хотел бы предложить что-то вроде следующего (я буду использовать объявления 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; 

Каждый гекс имеет шесть граней и шесть вершин. Каждый ребро отслеживает два соседних гекса, и каждая вершина отслеживает три своих соседних гекса (гекса на краях карты будет особым случаем).

Есть много вещей, которые вы могли бы сделать по-другому. Вы могли бы использовать указатели, а не массивы, вы могли бы использовать объекты, а не записи, и вы могли бы хранить ваши гексы в двумерном массиве, как предполагали другие ответчики.

Надеюсь, это может дать вам некоторые идеи об одном способе подхода к нему.

Answer 6

Я много разбираюсь с гексами. В таких случаях вы отслеживаете каждый из 6 пунктов для границ гексагона. Это позволяет вам легко рисовать.

У вас будет единственный массив объектов, представляющих гексы. Каждый из этих шестнадцатеричных объектов также имеет 6 «указателей» (или индекс для другого массива), указывающий на другой массив «сторон». То же самое для «вершин». Конечно, вершины имели бы 3 указателя на соседние гексы, а стороны имели бы 2.

Таким образом, шестигранный может быть что-то вроде: X, Y, точка (6), Вершины (6), Sides (6)

Тогда у вас есть Hex массив, массив Vertice и боковой массив.

Тогда довольно просто найти вершины/стороны для шестнадцатеричного или что-то еще.

Когда я говорю указатель, он может так же легко быть целым числом, указывающим на элемент в вершине или боковом массиве или что-то еще. И, конечно же, массивы могут быть списками или что угодно.

Answer 7

Мы реализовали Поселенцы Катан AI для класса проекта, и модифицированный код this ответа (который был глючный) создать Совет с постоянным временным случайным доступом к вершинам и ребрам. Это была забавная проблема, но доска заняла много времени, поэтому, если кто-то все еще ищет простую реализацию, вот наш код 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