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

Question

Некоторое время назад кто-то спросил меня, знаю ли я хороший способ кодирования информации для игры Settlers of Catan. Это потребовало бы хранения гексагональной сетки таким образом, чтобы каждый гекс мог иметь данные, связанные с ней. Что еще более важно, однако, мне понадобится какой-то способ эффективного поиска вершин и ребер по бокам этих шестиугольников, так как именно в этом заключается все действие.

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

Answer 1

Простая структура для хранения гексагональной сетки, когда вы заботитесь только о шестиугольниках, представляет собой матрицу с шестиугольником в точке (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 нечетно.

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

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

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

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

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

Вот пример кода 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],
        };
    }
}

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

Answer 2

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

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

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

Answer 3

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

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

Answer 4

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

Answer 5

Вот альтернатива ответу, получившему наибольшее количество голосов, потому что мы обнаружили много ошибок в этой реализации при реализации нашего собственного ИИ для Поселенцев Катана. Кстати, много ресурсов можно найти по структуре гексагональной сетки здесь: 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

Answer 6

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

Другая идея состояла бы в том, чтобы сохранить позиции в виде триплетов (x,y,z) вдоль трех осей, которые естественным образом имеет шестиугольник, и при необходимости нормализовать одну из координат до 0.

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