经典“大片”的解决方案

一种简单的图形算法 Flood fill 可以做到这一点。

它也可以通过简单的多通道方法来实现——Blockbuster板太小了,我不认为多次访问每个单元会对性能产生任何明显的影响——所以我建议首先尝试这种方法:

对于每个玩家,循环遍历所有单元格;如果单元格归玩家所有,并且与一个单元格相邻(如果单元格的六个边与此填充例程“标记”的单元格相邻),则单元格也会被标记。再次循环遍历所有单元格,直到没有单元格标记到当前播放机为止。以下是一些伪代码:

for player in players:
  # those on the starting edge that the player owns get 'marked'
  for cells in cells.start_edge(player):
    if cell.owner = player:
      cell.mark = player
  do:
    count = 0
    for cell in cells:
      if cell.mark == None && cell.owner == player:
        for adjacent in cell.neighbours:
          if adjacent.mark == player
            cell.owner = player
            count += 1
            break
  while count
  for cell in cells.stop_edge(player):
     if cell.mark == player
       player won!!

此时,如果板的适当一侧的任何单元格属于播放器,则播放器到达板的该一侧。

技巧是为每个块分配坐标。

你能做的就是把它看成一个简单的4x 4平方网格,X坐标在0到4,Y坐标在0到3之间。

绘图算法的职责是将奇数的X单元(1和3)偏移到六边形半径的一半,以便它们正确地装配在一起。

想一想 isAdjacent(other) 每个单元格的方法。在一个方格中,您可以通过一个简单的检查来判断是否相邻:如果self.x==other.x±1和self.x==other.x±1。有8个相关的组合-1,0,1代表X,-1,0,1代表Y需要检查。

在六角形网格中,相邻有点不同。如果self.y==other.y±1和self.x==other.x是它的一部分。但是x的邻接关系取决于自我所在的列。如果x是偶数列(0,2,4),则相邻单元格位于奇数列中,这意味着self.y==other.y或self.y==other.y+1。同样,如果x是奇数列(1,3),则相邻的单元格位于偶数列中。我会把它留给你去解决剩下的问题。

“边缘怎么办”?容易的。在您的 grid.get() 方法。对于越界坐标,返回一个从未被占用的特殊虚拟单元格。这使得比较更简单。

好吧,给 isAdjacent() 如何找到水平或垂直的连接路径?

实际上,您需要两种相邻的枚举形式。您要创建 enum_adjacent_vert(y_offset) 和 enum_adjacent_horiz(x_offset) . 枚举垂直相邻的生成三个值 (self.x-1, self.y+y_offset), (self.x, self.y+y_offset), (self.x+1, self.y+y_offset) . 要枚举水平相邻的,如果self.x在奇数列中,则生成两个值: (self.x+x_offset, self.y), (self.x+x_offset, self.y+1) . 如果self.x在偶数列中: (self.x+x_offset, self.y), (self.x+x_offset, self.y-1) .

这是相对直接的。对于边缘单元,您希望在特定方向上“穿过”或“向下”板到相邻单元。

假设从左到右(增加x)。您希望在 enum_adjacent_horiz 列表。要从上到下(增加y),可以在 enum_adjancent_vert 名单。

您的问题转化为两个节点是否连接在一个图中。

• 你可以把电路板看作一个无方向的“图形”。节点是单元格,如果它们是相邻单元格,则具有边。
• 边也是图中的节点,这些边与它们相邻的单元格有边。
• 以您可以使用的节点的子图为例(如果检查该播放器,则包括顶部和底部)
• 检查顶部和底部是否使用DFS连接