Структура данных для поселенцев на карте Катана?

Ответ 1

Простая структура для хранения гексагональной сетки, когда вы заботитесь только о шестиугольниках, представляет собой матрицу с шестиугольником at (x, y), являющимся соседством шестиугольников в точке (x, y ± 1), (x ± 1, y) и (x ± 1, y + 1) для четных xs или (x ± 1, y-1) для нечетных xs. Мы можем развить эту идею, чтобы обеспечить быстрый поиск ребер и вершин.

Вы добавляете к нему две другие матрицы: одну для ребер и другую для вершин.

Вы считаете шестиугольник в точке (x, y), ограниченный вершинами в положениях (x, 2y), (x, 2y + 1), (x, 2y + 2), (x + 1,2y), ( x + 1,2y + 1) и (x + 1,2y + 2), для четного xs. Для нечетных xs добавьте 1 к координате y. Кромки, окружающие его, равны (2x, 2y), (2x, 2y + 1), (2x + 1, 2y), (2x + 1,2y + 2), (2x + 2,2y) и (2x + 2,2y + 1), с дополнительной настройкой на y, добавив один, если x нечетно.

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

С помощью нескольких простых формул вы можете искать ребра из вершин, гексов из вершин и других поисков, которые вам могут понадобиться для игры.

Таким образом, вы можете представлять плату только с массивами и выполнять поиск с помощью простой математики для преобразования между "координатами шестиугольника", "краевыми координатами" и "координатами вершин".

Поскольку плата не будет идеально соответствовать (прямоугольной) матрице, вам нужно будет заполнить пару ячеек некоторым "пустым" или "недопустимым" значением, чтобы представить пару пограничных ячеек, которые не соответствуют шестиугольной форме доска.

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

Вот пример кода С#:

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],
        };
    }
}

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

Ответ 2

Одна из возможностей - это технология "кирпичной стены", которая использует квадратную сетку с каждой сметой строки на половину квадрата от верхней и нижней рядов. Это топологически то же самое, что и гексагонная сетка, но проще в использовании.

У вас всегда могут быть элементы данных шестиугольника и вершин, связанные с указателями или ссылками, но это может не соответствовать вашим требованиям к масштабированию, и их будет сложнее разместить на экране.

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

Ответ 3

Если вы посмотрите на куб под углом 45 градусов (с углом, обращенным к вам), вы увидите, что его силуэт - шестиугольник. Мы можем получить большой пробег, рассматривая шестиугольники как двумерные проекции кубов для алгоритмических целей.

Для получения дополнительной информации о подходе с шестиугольником, см. Amit post. Это окончательный ответ на реализацию гексагональных сеток в играх.

Ответ 4

Поскольку это двумерная структура, мы всегда можем делать только два измерения, которые в этом случае не находятся под углом 90 °, а 60 ° друг к другу. Однако расчет расстояний (в терминах пройденных гексов) в этом параметре несколько сложнее.

Множество wargames использует гексагональные структуры, но пытается посмотреть на реализацию чего-то вроде Vassal и VASL для идей может быть немного излишним.

Ответ 5

Вы можете найти этот пост в блоге (и другие в серии), полезные для некоторых фоновых идей.

Ответ 6

Здесь альтернатива главному голосовавшему ответу, потому что мы нашли много ошибок в этой реализации, внедряя собственный AI для Settlers of Catan. Кстати, здесь много гексагональной структуры сетки можно найти здесь: http://www.redblobgames.com/grids/hexagons/

Код в 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