data-structures - book - data structures types

¿Cómo represento una grilla hexagonal/hexagonal en la memoria?

Question

Digamos que estoy construyendo un juego de mesa con una grilla de hextil, como Settlers of Catan :

Tenga en cuenta que cada vértice y borde puede tener un atributo (un camino y asentamiento arriba).

¿Cómo crearía 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?

Answer 1

Amit Patel ha publicado una página increíble sobre este tema. Es tan completo y maravilloso que tiene que ser la respuesta definitiva a esta pregunta: rejillas hexagonales

Answer 2

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.

Por lo tanto, un hex puede ser algo así como: X, Y, punto (6), vértices (6), lados (6)

Entonces tienes una matriz hexagonal, una matriz de vértices y una matriz lateral.

Entonces 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.

Answer 3

Implementamos un Settlers of Catan AI para un proyecto de clase, y modificamos el código de this respuesta (que tenía errores) para crear un Tablero 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

Answer 4

Sugeriría algo como lo siguiente (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 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 otra manera, 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.

Con suerte, eso podría darte algunas ideas sobre una forma de abordarlo.

Answer 5

Tal rejilla se puede representar en una matriz bidimensional:

Si

 2
7 3
1
6 4
5

es el número uno con sus vecinos en la cuadrícula hexagonal, luego puedes poner esto en una matriz 2D como esta:

2 3
7 1 4
6 5

Obviamente, la vecindad se determina en esta cuadrícula no solo por ser horizontal o verticalmente adyacente, sino también por usar una diagonal.

Aunque puede usar un gráfico también, si lo desea.

Answer 6

Este artículo explica cómo configurar un juego de cuadrícula Isomérico / Hexagonal. Te recomiendo que eches un vistazo a Forcing Isometric and Hexagonal Maps onto a Rectangular Grid sección de Forcing Isometric and Hexagonal Maps onto a Rectangular Grid y en la sección de movimiento. Aunque es diferente de lo que está buscando, puede ayudarlo a formular cómo hacer lo que desea.

Answer 7

 2
7 3
1
6 4
5

También puede intentar "alinear" las filas de su mapa. Para este ejemplo, sería:

 2
7 1 3
6 5 4

A veces es más útil tener filas en una fila: P