如何在内存中表示六边形/六边形网格？

Question

假设我正在建造一个六边形网格的桌游，就像卡坦岛一样：

请注意每个顶点和边缘都可能有一个属性（如上面的道路和定居点）。

我应该如何创建一个代表这个游戏板的数据结构？访问每个图块的邻居、边缘和顶点的模式是什么？

- a paid nerd

---

你也可以使用希尔伯特曲线，它们是一种间隔填充曲线，使得平面上的邻接在线性编码中保持不变。了解空间索引以及它们的用途！非常有趣。 - pbordeaux

Answer 1

Amit Patel发布了一篇关于六边形网格的 惊人 页面。它非常全面和精彩，需要成为这个问题的旨在回答：Hexagonal Grids

- a paid nerd

---

谢谢 :) 那个页面没有涵盖边和顶点，但我在我的网格文章的“部分之间关系”中涵盖了它们，该文章位于http://www-cs-students.stanford.edu/~amitp/game-programming/grids/（图表包括轴向六边形网格的公式，但图示仅适用于方形网格）。 - amitp

我发现这篇博客非常令人困惑，使用了x、y、z和q、r、s，然后实现库又切换了轴，这让我的大脑再次混乱。你还进行轴向->立方体->轴向的转换来进行四舍五入，这也让我感到困惑，因为如果你忽略s变量，轴向理论上可以一直是立方体，为什么两种类型都存在呢？ - WDUK

谢谢你，你救了我的Code day 24！将六边形作为立方体进行导航不是我自己能想出来的。 - CodingNagger

Answer 2

这样的网格可以用二维数组表示：

如果

   2
7     3
   1   
6     4
   5

如果想在六边形网格中将数字与其相邻的数字进行比较，则可以将其放入二维数组中，如下所示：

2 3
7 1 4
  6 5

显然，在这个网格中，邻居关系不仅取决于水平或垂直相邻，而且还可以使用一个对角线。

如果你喜欢的话，也可以使用图表。

- Joey

---

很好。那么边缘和顶点的数据呢？ - a paid nerd

我可能会将它们分开存储。无论您主要查看瓷砖还是边缘/顶点，另一半数据存储起来要么痛苦，要么多余。 - Joey

请参阅Amit Patel在“a paid nerd”中的文章。 - aredridel

Answer 3

这篇文章介绍了如何设置一个等角/六边形网格游戏。我建议您查看“强制等角和六边形地图进入矩形网格”部分以及移动部分。虽然它与您所寻找的内容不同，但可以帮助您构思您想要实现的方法。

- zfedoran

Answer 4

您可以创建一个二维数组，然后将有效的位置考虑为：

- 在偶数行（0,2,4，...）：奇数编号的单元格。 - 在奇数行（1,3,5，...）：偶数编号的单元格。

对于每个单元格，它的邻居将是：

- 同一列，向上2行 - 同一列，向下2行 - 左边1个+上面1个 - 左边1个+下面1个 - 右边1个+上面1个 - 右边1个+下面1个

演示：

x标记代表六边形。 对角线上的x是相邻的。 | 连接垂直邻居。

- yman

Answer 5

我曾经处理过很多十六进制的情况。在这种情况下，您需要跟踪六个点以确定十六进制边界。这样可以轻松地绘制它。

您将拥有一个代表十六进制的对象数组。每个十六进制对象还有6个“指针”（或者是指向另一个数组的索引），指向另一个“边缘”数组。对于“顶点”也是同样的情况。当然，顶点将具有3个指向相邻十六进制的指针，而边将具有2个指针。

所以，一个十六进制可能类似于： X，Y，Point（6），Vertices（6），Sides（6）

然后您将拥有一个十六进制数组，顶点数组和边数组。

然后，找到十六进制或其他对象的顶点/边就非常简单了。

当我说指针时，它也可以很容易地成为指向顶点或边数组中元素的整数。当然，数组可以是列表或任何其他类型。

- Nobody Inparticular

Answer 6

我建议使用以下类似的方式（我将使用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;

每个六边形都有六条边和六个顶点。每条边跟踪其两个相邻的六边形，每个顶点跟踪其三个相邻的六边形（地图边缘上的六边形将是一个特殊情况）。

当然，有许多不同的方法可以做到这一点。您可以使用指针而不是数组，您可以使用对象而不是记录，并且您可以像其他回答者建议的那样将您的六边形存储在二维数组中。

希望这能给您一些思路来解决问题。

- Incredulous Monk

Answer 7

   2
7     3
   1   
6     4
   5

你也可以尝试将地图的行“压平”。对于这个例子，它会变成：

  2
7 1 3
6 5 4

有时候把行放在一行里更有用：P

- qba

---

这段代码可能会有一些混乱的邻居检查，因为例如1和6是相邻的，但3和5不是，然而它们具有相同的相对位置。 - Bernhard Barker

Answer 8

我正在利用我的空闲时间编写有趣的十六进制编码程序。它是这样的……我会告诉你它在文字上看起来像什么。

1. 六边形：它有六个相邻的六边形。它可以为每个相邻的六边形瓷砖提供参考。它可以告诉你它由什么组成（水，岩石，尘土）。它可以连接自己和其他六边形，并且反之亦然。它甚至可以自动连接周围的其他六边形，创建更大的领域或确保所有领域都可以被其邻居访问。
2. 建筑物参考了三条道路和三个六边形瓷砖。它们可以告诉你它们是哪些。
3. 道路参考了两个六边形瓷砖和其他道路，当它们被相邻的瓷砖访问时。它们可以告诉你它们连接到哪些瓷砖、道路或建筑物。

这只是我如何处理它的一个想法。

- Raphael Denken

Answer 9

我们为一个课程项目实现了一个《卡坦岛》AI，并修改了this答案中有缺陷的代码，以创建具有常数时间随机访问顶点和边缘的棋盘。这是一个有趣的问题，但棋盘花费了很多时间，所以如果有人仍在寻找简单的实现，这里是我们的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

- ghopper

---

这个回答很糟糕。你只是粘贴了大量代码，没有解释任何内容（除了谁编写了代码）。即使在这里这样做可以接受，代码本身也很糟糕。没有文档字符串，几乎没有注释，而且包含的少数注释也难以理解（逻辑是认为它是说getEdgesOfVertex，然后对于每条边获取顶点端点，取出三个等于vertex的顶点）。 - Carl Smith