Как мне представить гексилированную / шестигранную сетку в памяти?
Скажем, я строю настольную игру с шестигранной сеткой, как Settlers of Catan:
Обратите внимание, что каждая вершина и ребро могут иметь атрибут (дорога и поселение выше).
Как бы я сделал структуру данных, которая представляет эту доску? Каковы шаблоны для доступа к соседям, ребрам и вершинам каждой плитки?
8 ответов
Амит Патель разместил удивительную страницу на эту тему. Он настолько всеобъемлющий и замечательный, что должен быть окончательным ответом на этот вопрос: шестиугольные сетки
Такая сетка может быть представлена в двумерном массиве:
Если
2
7 3
1
6 4
5
это номер один со своими соседями в шестнадцатеричной сетке, тогда вы можете поместить это в 2D-массив следующим образом:
2 3
7 1 4
6 5
Очевидно, что соседство определяется в этой сетке не только по горизонтали или вертикали, но также по одной диагонали.
Вы также можете использовать график, если хотите.
В этой статье рассказывается, как настроить игру "Изомерная / шестиугольная сетка". Я рекомендую вам взглянуть на Forcing Isometric and Hexagonal Maps onto a Rectangular Grid раздел и раздел движения. Хотя это отличается от того, что вы ищете, оно может помочь вам сформулировать, как делать то, что вы хотите.
Вы можете создать 2D-массив, а затем рассматривать допустимые позиции как:
- В строках с четными номерами (0,2,4,...): ячейки с нечетными номерами.
- В строках с нечетными номерами (1,3,5,...): ячейки с четными номерами.
Для каждой ячейки ее соседями будут:
- В том же столбце, на 2 строки вверх
- В том же столбце, на 2 строки вниз
- 1 осталось + 1 вверх
- 1 слева + 1 вниз
- 1 право + 1 вверх
- 1 вправо + 1 вниз
Иллюстрация:шестигранная сетка
Знаки x - это шестиугольники. x, диагональные друг к другу, являются соседями. | связывает вертикальных соседей.
Я много имел дело с гексами. В подобных случаях вы отслеживаете каждую из 6 точек для границ гекса. Это позволяет вам нарисовать это довольно легко.
У вас будет один массив объектов, представляющих гексы. Каждый из этих шестнадцатеричных объектов также имеет 6 "указателей" (или указатель на другой массив), указывающих на другой массив "сторон". То же самое для "вершин". Конечно, у вершин будет 3 указателя на смежные гексы, а у сторон будет 2.
Таким образом, гекс может быть что-то вроде: X, Y, точка (6), вершины (6), стороны (6)
Затем у вас есть массив Hex, массив вершин и боковой массив.
Тогда довольно просто найти вершины / стороны для гекса или что-то еще.
Когда я говорю "указатель", это может быть просто целое число, указывающее на элемент в массиве вершины или стороны или что-то еще. И, конечно, массивы могут быть списками или чем-то еще.
Мы реализовали 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
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;
Каждый гекс имеет шесть ребер и шесть вершин. Каждый край отслеживает два смежных гекса, а каждая вершина отслеживает три смежных гекса (особый случай - гексы по краям карты).
Есть много вещей, которые вы могли бы сделать по-другому, конечно. Вы можете использовать указатели, а не массивы, вы можете использовать объекты, а не записи, и вы можете хранить свои гексы в двумерном массиве, как предлагали другие авторы.
Надеюсь, это может дать вам некоторые идеи об одном способе подойти к нему, хотя.