经典游戏《坦克大战》的解决方案

Question

经典游戏《坦克大战》的解决方案

algorithmpuzzle

3

在英国的80年代和90年代（我相信70年代也是！），有一个经典的电视节目叫做“Blockbuster”，它展示了一个蜂窝网格状的六边形，就像这样（对不起，图片有点模糊！）：

_{（来源：ukgameshows.com）} 如您所见，有五列字母和四行。一个人或团队试图横向旅行，另一个人或团队试图纵向旅行。回答问题可以赢得一个六边形，并且答案将以该六边形中显示的字母开头。

获胜的个人或团队是第一个“连接线”的人 - 请注意，这可能会回到自己身上（例如，如果被对方团队赢得该六边形所阻挡），因此有许多可能的获胜组合。

多年前，当我刚开始编程时，我写了一个基于这个谜题的会议游戏（我们将其改成了交替的八边形和正方形以避免版权侵犯！）但我一直苦恼于检查何时完成一条完整线的算法。简单的很容易，但是上下、来回的情况我真的卡住了！

最终，我基本上编写了一个巨大的蛮力循环，但仍然无法涵盖所有情况。因此，我不得不在会议组织者的屏幕上放置一个按钮，以使他们能够快速声明获胜者，如果逻辑未能检测到它！可谓是肮脏的hack...

现在，我回想起我曾经需要解决的这个谜题，我想知道你们中是否有人愿意提出更优雅的解决方案？当然，语言无关（包括伪代码）。

编辑：存储数据的方式随意。我把它放在了一个数组中。

- h4xxr

1

啊，没错，Blockbuster... "什么 S是程序员常用的问答网站？" - Martin B

1

是的，这里是那些激励人心的喜剧作品如“我想要P，请Bob”诞生的地方！... - h4xxr

原始游戏名为六角棋（Hex）：http://en.wikipedia.org/wiki/Hex_%28board_game%29。此外还有许多变种，最有趣的是Twixt。 - starblue

3个回答

1

你的问题可以转化为判断图中两个节点是否相连。

你可以将棋盘看作一个无向“图”。每个格子都是一个节点，如果它们相邻，则它们之间有边缘。
棋盘的边缘也是图中的节点，它们与相邻的格子之间有边缘。
选择你可以使用的节点子图（包括顶部和底部，如果检查该玩家）。
使用深度优先搜索算法检查顶部和底部是否相连。

- yairchu

它与Will的答案不等价，洪水填充是广度优先搜索。 - starblue

1

关键是为每个块分配坐标。

你可以将其视为一个简单的4x4方格，其中x坐标范围在0到4之间，y坐标范围在0到3之间。

绘图算法的责任是将奇数x单元格（1和3）向下偏移半个六边形半径，以便它们正确拼合。

考虑为每个单元格创建一个isAdjacent(other)方法。在正方形网格中，您可以通过一个微不足道的检查来推理出isAdjacent：如果self.x == other.x ± 1且self.x == other.x ± 1，则为真。需要检查8个相关的组合，包括x的-1、0、1和y的-1、0、1。

在六边形网格中，相邻性有所不同。如果self.y == other.y ± 1且self.x == other.x是其中的一部分。但x相邻性取决于self位于哪一列。如果x是偶数列（0、2、4），则相邻单元格位于奇数列，这意味着self.y == other.y或self.y == other.y + 1。同样，如果x是奇数列（1、3），则相邻单元格位于偶数列。我会让你自己解决isAdjacent的其余部分。

“边缘怎么办？”很容易。将它们包含在您的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)。要枚举水平相邻，则在自身x为奇数列时产生两个值：(self.x+x_offset, self.y), (self.x+x_offset, self.y+1)。如果自身x在偶数列中：(self.x+x_offset, self.y), (self.x+x_offset, self.y-1)。

这相对简单。给定一个边缘单元格，您想要沿着棋盘“横向”或“向下”走到特定方向的相邻单元格。

假设您从左到右（增加x）移动。您想在enum_adjacent_horiz列表中找到相邻的单元格。要从上到下（增加y），请在enum_adjancent_vert列表中找到相邻的单元格。

- S.Lott

非常感谢您提供的全面答案。我的旧算法失败的情况是当“路径”从左到右时，会“回到自己”，例如横穿底部，然后向左上方对角线返回，再横穿顶部连接。如果您从左到右（增加x）进行操作，它是否仍然能够捕捉到这些情况？ - h4xxr

这就是关键所在。如果x始终在增加，那么你就不可能回头了。你的单元格的enum_adjacent_horiz方法绝对保证了x的单调变化。同样地，enum_adjacent_horiz也绝对保证了y的单调变化。 - S.Lott

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Will · Accepted Answer

一种简单的图形算法称为Flood fill可以实现这一点。

也可以采用简单的多遍方法 - 模块板很小，我认为访问每个单元格多次不会对性能产生任何显着影响 - 因此我建议首先尝试这种方法：

对于每个玩家，循环遍历所有单元格; 如果该单元格归属于该玩家，并且在其六个侧面之一上相邻于由此填充程序“标记”的单元格，则该单元格也会被标记。再次循环遍历所有单元格，直到没有单元格被标记为当前玩家为止。以下是一些伪代码：

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!!

此时，如果棋盘适当一侧的任何一个单元格属于该玩家，则该玩家已经到达了棋盘的那一侧。