Decir que estoy construyendo un juego de mesa con una rejilla Hextile, como Settlers of Catan:¿Cómo represento una cuadrícula hexagonal/hexagonal en la memoria?
Tenga en cuenta que cada vértice y el borde pueden tener un atributo (una carretera y liquidación arriba).
¿Cómo podría hacer una estructura de datos que represente esta placa? ¿Cuáles son los patrones para acceder a los vecinos, bordes y vértices de cada tesela?
Amit Patel ha publicado increíble página sobre este tema. Es tan amplio y maravilloso que tiene que ser la respuesta definitiva a esta pregunta: Hexagonal Grids
Dicha rejilla se puede representar en una matriz de dos dimensiones:
Si
2
7 3
1
6 4
5
es el número uno con sus vecinos en la red hexagonal, a continuación, se puede poner esto en una matriz 2D así:
2 3
7 1 4
6 5
Obviamente vecino-dad se determina en esta rejilla no sólo por ser horizontal o verticalmente adyacente, sino también el uso de una diagonal.
Aunque puede usar un gráfico también, si lo desea.
Cool. ¿Qué pasa con los datos de los bordes y vértices? –
Probablemente los guarde por separado. Independientemente de si mira principalmente los mosaicos o los bordes/vértices, la otra mitad de los datos es dolorosa o redundante de almacenar. – Joey
Vea el artículo de Amit Patel en una respuesta de "nerd pagado". – aredridel
2
7 3
1
6 4
5
También puede tratar de 'planas' filas de su mapa. Para este ejemplo sería:
2
7 1 3
6 5 4
Su veces más útil tener filas en una fila: P
Esto podría tener un código de comprobación de vecinos desordenado, porque, por ejemplo, 1 y 6 son vecinos, pero 3 y 5 no, pero tienen las mismas posiciones relativas. – Dukeling
This article pasa por cómo configurar un juego de rejilla isoméricas/hexagonal. Te recomiendo que eches un vistazo a la sección Forcing Isometric and Hexagonal Maps onto a Rectangular Grid y la sección de movimiento. Aunque es diferente de lo que está buscando, puede ayudarlo a formular cómo hacer lo que desea.
Yo sugeriría algo como lo siguiente (Voy a usar declaraciones de estilo 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;
Cada hexágono tiene seis bordes y seis vértices. Cada borde hace un seguimiento de sus dos hexágonos contiguos, y cada vértice hace un seguimiento de sus tres hexes contiguos (los hexágonos en los bordes del mapa serán un caso especial).
Hay muchas cosas que podrías hacer de una manera diferente, por supuesto. Podría usar punteros en lugar de matrices, podría usar objetos en lugar de registros, y podría almacenar sus hexágonos en una matriz bidimensional como han sugerido otros contestadores.
Afortunadamente, eso podría darte algunas ideas sobre una forma de abordarlo.
He tratado mucho con hexes. En casos como este, haces un seguimiento de cada uno de los 6 puntos para los bordes del hex. Esto te permite dibujarlo con bastante facilidad.
Tendría una única matriz de objetos que representan hexes. Cada uno de estos objetos hexadecimales también tiene 6 "punteros" (o un índice de otra matriz) apuntando a otra matriz de "lados". Lo mismo para "vértices". Por supuesto, los vértices tendrían 3 punteros a los hexágonos contiguos, y los lados tendrían 2.
Así, un hexágono puede ser algo como: X, Y Punto (6), los vértices (6), Sides (6)
entonces usted tiene una serie Hex, matriz vértice, y la matriz lado.
Luego es bastante simple encontrar los vértices/lados para un hexágono, o lo que sea.
Cuando digo puntero, podría ser un número entero que apunta al elemento en el vértice o en la matriz lateral o lo que sea. Y, por supuesto, las matrices podrían ser listas o lo que sea.
se implementó un Colonos de Catan AI para un proyecto de clase, y el código modificado de this respuesta (que estaba con errores) para crear una Junta con acceso aleatorio de tiempo constante a vértices y bordes. Fue un problema divertido, pero la junta tomó mucho tiempo, por lo que si alguien todavía está buscando una implementación simple aquí está nuestro código 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
Gracias :) Esa página no cubre los bordes y vértices, pero los cubro en la sección de Relaciones entre partes de mi artículo sobre grids en http://www-cs-students.stanford.edu/~amitp/game-programming/ cuadrículas/(los diagramas son para cuadrículas cuadradas, pero la tabla también incluye las fórmulas para cuadrículas hexagonales axiales) – amitp