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

Скажем, я создаю настольную игру с гекстильной сеткой, например Settlers of Catan :

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

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

Амит Патель опубликовал потрясающую страницу по этой теме. Он настолько всеобъемлющий и замечательный, что должен быть окончательным ответом на этот вопрос: гексагональные сетки.

Такую сетку можно представить в виде двумерного массива:

Если

   2
7     3
   1   
6     4
   5

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

2 3
7 1 4
  6 5

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

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

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

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

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

Итак, шестиугольник может быть примерно таким: X, Y, Point (6), Vertices (6), Sides (6).

Затем у вас есть шестнадцатеричный массив, массив вершин и боковой массив.

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

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

   2
7     3
   1   
6     4
   5

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

  2
7 1 3
6 5 4

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

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

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

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

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

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

Я сижу здесь «в свободное время, кодирую для развлечения» с проклятиями. А происходит это так ... Я расскажу вам, как это выглядит словами.

1. Шестиугольник: у него шесть соседних шестиугольников. Он может доставить ссылку для каждой соседней шестнадцатеричной плитки. Он может сказать вам, из чего он состоит (вода, камень, пыль). Он может подключаться к другим и наоборот. Он может даже автоматически подключать других, окружающих его, чтобы создать большее поле и / или убедиться, что все поля могут быть адресованы его соседям.
2. Здание ссылается на три дороги и три шестиугольных плитки. Они могут сказать вам, какие они.
3. Дорога ссылается на два гекса и другие дороги, когда к ним обращаются соседние плитки. Они могут сказать, какие это плитки и с какими дорогами или зданиями они связаны.

Это просто идея, как я буду над этим работать.

Вы можете создать 2D-массив, а затем рассматривать допустимые позиции как:

• В строках с четными номерами (0,2,4, ...): ячейки с нечетными номерами.
• В строках с нечетными номерами (1,3,5, ...): ячейки с четными номерами.

Для каждой ячейки ее соседями будут:

• Тот же столбец, на 2 строки вверх
• В том же столбце, на 2 строки вниз
• 1 осталось + 1 вверх
• 1 слева + 1 вниз
• 1 право + 1 вверх
• 1 вправо + 1 вниз

Иллюстрация: шестигранная сетка

Знаки x - это шестиугольники. x, диагональные друг к другу, являются соседями. | связывает вертикальных соседей.