data structures - precio - ¿Estructura de datos para el mapa Colonos de Catan?

manual catan

Question

Esta pregunta ya tiene una respuesta aquí:

• ¿Cómo represento una cuadrícula hexadecimal / hexadecimal en la memoria? 8 respuestas

Hace un tiempo, alguien me preguntó si conocía una buena forma de codificar la información para el juego Settlers of Catan. Esto requeriría almacenar una cuadrícula hexagonal de una manera en la que cada hex pueda tener datos asociados. Sin embargo, lo más importante es que necesitaría alguna forma de buscar eficientemente los vértices y los bordes en los lados de estos hexágonos, ya que ahí es donde está toda la acción.

Mi pregunta es la siguiente: ¿existe una estructura de datos buena y simple para almacenar una cuadrícula hexagonal que permita la búsqueda rápida de hexágonos, bordes entre hexágonos y vértices en las intersecciones de hexágonos? Sé que las estructuras generales como un borde alado o cuádruple podrían hacer esto, pero eso parece una exageración masiva.

Answer 1

Aquí hay una alternativa a la respuesta más votada porque encontramos muchos errores en esa implementación al implementar nuestra propia AI para los colonos de Catan. Por cierto, se pueden encontrar muchos recursos en la estructura de cuadrícula hexagonal aquí: post

Código en 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
# tested
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 2

Como es una estructura bidimensional, siempre podemos hacerlo con solo dos dimensiones, que en este caso no están a 90 ° sino a 60 ° entre sí. Sin embargo, los cálculos de distancia (en términos de hexes atravesados) son un poco más difíciles en esa configuración.

Otra idea sería almacenar las posiciones como tripletes (x, y, z) a lo largo de los tres ejes que tiene naturalmente un hexágono, y donde sea necesario, normalizar una de las coordenadas a 0.

Muchos de los juegos de guerra usan estructuras hexagonales, pero tratar de ver la implementación de algo como Vassal y VASL en busca de ideas puede ser un poco excesivo.

Answer 3

Es posible que encuentre esta publicación de blog (y otras en la serie) útil para algunas ideas de fondo.

Answer 4

Si miras un cubo desde un ángulo de 45 grados (con una esquina hacia ti), verás que su silueta es un hexágono. Podemos obtener mucho kilometraje al tratar los hexágonos como proyecciones bidimensionales de cubos para propósitos algorítmicos.

Para obtener más información sobre el enfoque del hexágono como cubo, echa un vistazo a la post de Amit. Es la respuesta definitiva sobre la implementación de grillas hexagonales en juegos.

Answer 5

Una estructura simple para almacenar una cuadrícula hexagonal cuando solo te preocupan los hexágonos, es una matriz, con un hexágono en (x, y) que es un vecino de hexágonos en (x, y ± 1), (x ± 1, y), y (x ± 1, y + 1) para xs par (x ± 1, y-1) para xs impares. Podemos evolucionar esta idea para permitir una búsqueda rápida de bordes y vértices.

Agregue otras dos matrices a esto: una para los bordes y otra para los vértices.

Considera un hexágono en (x, y) delimitado por los vértices en las posiciones (x, 2y), (x, 2y + 1), (x, 2y + 2), (x + 1,2y), (x + 1 , 2y + 1), y (x + 1,2y + 2), para x iguales. Para las xs impares, agregue 1 a la coordenada y. Los bordes que lo rodean son aquellos en (2x, 2y), (2x, 2y + 1), (2x + 1, 2y), (2x + 1,2y + 2), (2x + 2,2y), y (2x + 2,2y + 1), con un ajuste adicional a y agregando uno si x es impar.

Esto le da un acceso aleatorio constante a los bordes y vértices dado un hexágono (y puede calcular las transformaciones de coordenadas para hacer la búsqueda inversa también).

Con algunas fórmulas más simples, puedes buscar bordes de vértices, hexes de vértices y otras búsquedas que puedas necesitar para jugar.

De esta manera, puede representar el tablero con nada más que matrices y hacer búsquedas con cálculos simples para transformar entre "coordenadas hexagonales", "coordenadas de borde" y "coordenadas de vértice".

Debido a que la placa no se ajusta perfectamente a una matriz (rectangular), tendrá que llenar un par de celdas con algún valor "vacío" o "no válido", para representar la pareja de celdas delimitadas que no coinciden con la forma hexagonal de la placa.

Asintóticamente, este método utiliza la memoria lineal en el número de hexes y da tiempo constante para cualquier búsqueda.

Aquí hay un ejemplo de código C #:

class Board
{
public readonly Hex[,] Hexes = new Hex[10,10];
public readonly Edge[,] Edges = new Edge[22,22];
public readonly Vertex[,] Vertices = new Vertex[22,22];
public Board()
{
for(int i = 0; i < 10; i++)
for(int j = 0; j < 10; j++)
Hexes[i,j] = new Hex { X = i, Y = j };
for(int i = 0; i < 22; i++)
for(int j = 0; j < 22; j++)
{
Edges[i,j] = new Edge { X = i, Y = j };
Vertices[i,j] = new Vertex { X = i, Y = j };
}
}
public IEnumerable<Hex> GetNeighbors(Hex hex)
{
var x = hex.X; var y = hex.Y;
var offset = x % 2 == 0? +1 : -1;
return new []
{
Hexes[x,y+1],
Hexes[x,y-1],
Hexes[x+1,y],
Hexes[x-1,y],
Hexes[x+1,y+offset],
Hexes[x-1,y+offset],
};
}
public IEnumerable<Vertex> GetVertices(Hex hex)
{
var x = hex.X; var y = hex.Y;
var offset = x % 2;
return new[]
{
Vertices[x,2*y+offset],
Vertices[x,2*y+1+offset],
Vertices[x,2*y+2+offset],
Vertices[x+1,2*y+offset],
Vertices[x+1,2*y+1+offset],
Vertices[x+1,2*y+2+offset],
};
}
public IEnumerable<Edge> GetEdges(Hex hex)
{
var x = hex.X; var y = hex.Y;
var offset = x % 2;
return new[]
{
Edges[2*x,2*y+offset],
Edges[2*x,2*y+1+offset],
Edges[2*x+1,2*y+offset],
Edges[2*x+1,2*y+2+offset],
Edges[2*x+2,2*y+offset],
Edges[2*x+2,2*y+1+offset],
};
}
public IEnumerable<Vertex> GetEnds(Edge edge)
{
var x = edge.X; var y = edge.Y;
if(x % 2 == 0)
return new[]
{
Vertices[x/2,y],
Vertices[x/2,y+1],
};
else
return new[]
{
Vertices[(x-1)/2,y],
Vertices[(x+1)/2,y],
};
}
public IEnumerable<Edge> GetEdges(Vertex vertex)
{
var x = vertex.X; var y = vertex.Y;
return new []
{
Edges[x*2,y],
Edges[x*2+1,y],
Edges[x*2-1,y],
};
}
public IEnumerable<Hex> GetHexes(Vertex vertex)
{
var x = vertex.X; var y = vertex.Y;
var xoffset = x % 2;
var yoffset = y % 2;
return new[]
{
Hexes[x-1,(y+xoffset)/2-1],
Hexes[x-(1-yoffset)*xoffset,(y-1)/2],
Hexes[x,(y-xoffset)/2],
};
}
}

Hay algo de ineficiencia de memoria porque algunas celdas nunca se usan, pero eso no debería ser un problema. El consumo de memoria permanece bajo el mismo límite asintótico.

Answer 6

Una posibilidad es la técnica del "muro de ladrillo", que utiliza una cuadrícula cuadrada con cada fila desplazada en medio cuadrado desde las filas superior e inferior. Es topológicamente lo mismo que una cuadrícula hexagonal, pero más fácil de usar de alguna manera.

Siempre puede tener elementos de datos hexagonales y de vértice, conectados con punteros o referencias, pero eso podría no cumplir con sus requisitos de escalado, y será más difícil colocarlos en una pantalla.

Si recuerdo correctamente las reglas, es muy importante saber en qué hexágonos hay un vértice, y muy importante saber qué vértices son adyacentes a los cuales, y la mayoría de las otras relaciones no son importantes (aparte de los lados hexadecimales que tienen puertos o lo que sea) llamas a esos intercambiar cosas).