扫雷游戏生成背后的算法是什么？

Question

扫雷游戏生成背后的算法是什么？

19

我曾经浏览了很多教如何解决它的网站，但我想知道如何创建它。我对它的编码方面不太感兴趣，但想更多地了解其背后的算法。例如，当生成包含10个地雷的网格时，我会使用任意随机函数在网格上分布地雷，但我该如何设置与之相关的数字并决定打开哪个方块呢？我无法构思出通用算法来完成这项工作。

- Rahul

1

每个地雷应该只增加不是地雷的相邻单元。 - cthom06

这解决了所有的1，但是3和4怎么办？我该如何将这些数字合并？如果我现在的解析方式只适用于单个1。 - Rahul

可能是Minesweeper算法的重复问题。 - BoltClock

@boltcock，我确实阅读了那个帖子，但它更侧重于求解器而不是制造商。 - Rahul

4个回答

5

您只需种植地雷，然后遍历每个单元格并计算相邻的地雷数量。

或者您可以将每个计数器设置为0，并随着每个种植的地雷，增加所有相邻单元格的计数器。

- phimuemue

3

如果你想在N个方格上放置m个地雷，并且你可以使用随机数生成器，那么你只需要遍历剩余的方格，对于每个方格计算（剩余地雷数量）/（剩余方格数量），如果随机数小于或等于该值，则放置地雷。

现在，如果你想给每个方格标上相邻地雷的数量，你可以直接这样做：

count(x,y) = sum(
  for i = -1 to 1
    for j = -1 to 1
      1 if (x+i,y+j) contains a mine
      0 otherwise
)

或者你可以选择从一个由零组成的数组开始，在中心有地雷的3x3方块中逐个递增。（为拥有地雷的方块编号不会有任何影响。）

这将产生一个纯随机且正确标注地雷位置的扫雷游戏。然而，有些随机游戏可能不是有趣的游戏；选择随机但有趣的游戏是一项更具挑战性的任务。

- Rex Kerr

我可以创建网格并使用任意随机函数来放置雷，但是真正的挑战在于，当我尝试将数字与这些雷相联系时，我不知道该如何处理它们。 - Rahul

我提供了伪代码（没有边界检查），可以完美实现这个功能。（注意总和——您将加起来9个值，这些值要么是1，要么是0，具体取决于该位置是否有地雷。） - Rex Kerr

2

一个强大的算法

这里是一个扫雷算法的实现。该算法考虑了一些条件来生成地图，并执行一个求解器算法，以确保生成的地图至少有一个可能的解决方案。

这个示例的实现过程太长了，无法作为代码发布，因此将通过一些示例进行说明，以便其他人可以在所需的编程语言中复制它。在这个示例中，使用了Python。

主循环

首先，我们需要创建一个主循环，在其中执行任意数量的地图生成尝试，包括每次尝试结束时的求解器算法验证。该循环将具有max_fails限制，以确保它不会成为一个无限循环。请注意，我们稍后将使用更多的继承循环，所有这些循环都必须设置自己的限制。

当一个fail发生时，意味着一个地雷放置尝试失败或者生成的地图没有可能的解决方案。通过这种方法，我们可以尝试动态地生成地图，无论生成尝试有多大或者做了多少次。如果达到了max_fails，它总是会停止尝试地图生成。这意味着如果网格很小，在达到限制之前可能会进行很多次尝试，另一方面，如果网格很大，则可能只进行少量尝试。我们还可以根据网格的面积动态地定义max_fails限制，以允许更大的网格在需要时执行更长时间。

同样，在这里，我们应该定义地雷数量，这可以使用网格的面积动态地完成，也可以使用difficulty变量...或同时使用两者！

mines = int((height * width)//(15 - difficulty))

max_fails = 500 #<- This could be defined dynamically using exponential functions.

possible_solution_found = False
fails = 0
while not possible_solution_found and fails < max_fails:

1. 网格生成

我们需要创建一个网格的矩阵表示，通常在给定的维度值内完成。这可以通过迭代这些维度值来创建一个矩阵的列表列表表示来完成。首先在Y轴上创建行列表，然后在X轴上将0值添加到行列表中。

最好创建一个寄存器的矩阵副本。我们需要向每个单元格添加单元格的位置，而不是添加0值。例如，它可以是坐标的元组。(x, y)

寄存器对于稍后优化放置地雷的随机选择过程非常有用，这将防止在同一单元格上两次失败。

matrix = list()
matrix_register = list()
for row_index in range(height):
    row = list()
    row_register = list()
    for cell_index in range(width):
        row.append(0)
        row_register.append((cell_index, row_index))
    matrix.append(row)
    matrix_register.append(row_register)

2. 雷区放置

循环

这里我们应该开始进行循环，在这里将进行雷区放置尝试。如果不再需要放置地雷或达到了 max_fails 的限制，此循环应结束。

total_mines = mines
while total_mines > 0 and fails < max_fails:
    # subtract 1 to total_mines each time a mine is placed correctly.

随机选择

现在，我们需要随机选择一个单元格作为地雷。如果您已经实现了它，您应该从注册矩阵中选择单元格，并且无论它是否成功设置为地雷，都要将其删除。这样就不可能再选择一个已经是地雷或永远不会成为地雷的单元格。否则，如果您没有实现注册矩阵，则只需从主矩阵中随机选择。但请注意，这将增加失败尝试并使算法性能降低。

请注意，如果您选择实现注册矩阵，则还必须捕获注册矩阵为空时发生的异常。

在继续之前，我们应该确保所选单元格不是已经是地雷。

如果您正在实时游戏中构建算法，则可能希望添加一些其他功能。例如，您应该在玩家实际点击游戏开始时执行选择过程和后续步骤。这可以确保玩家不会在第一次点击时点击到地雷。此外，如果您愿意，您可以确保玩家在空单元格上进行第一次点击，以便良好的开局。这些是实时游戏附加功能的一些示例，可以使您的游戏更好、更具响应性和趣味性。在这种情况下，我们不使用这些功能，因为我们只是为通用目的构建生成器，例如 Discord 机器人小游戏。

在这个例子中，使用了寄存器矩阵：

try:
    row_choice: list = random.choice(matrix_register)
except IndexError:
    # No more mines can be placed!
    break

cell_coordinates: dict = random.choice(row_choice)

row_index = cell_coordinates[0]
column_index = cell_coordinates[1]

value = matrix[row_index][column_index]

条件的评估

现在我们选择将一个单元格放置为地雷，需要评估该单元格是否有效以成为地雷。在这种情况下，我们将评估两个主要条件：周围合法空单元格的数量和如果选择该单元格作为地雷时所有连续的地雷仍然有效。

为了进行这些评估，我们需要能够访问给定单元格的周围单元格（周围的8个单元格）。这可以通过计算周围单元格的范围来完成。为此，我们需要计算范围的左上角和右下角单元格。必须正确执行此操作，否则可能会导致索引错误。其中一种实现方式是检查给定单元格的位置。例如，如果给定单元格不在矩阵的第一行，则可以将top_left_y设置为给定单元格Y轴坐标的前一个位置，如果在第一行，则应将top_left_y设置为给定单元格的Y轴坐标。对于四个方向，可以这样做：top_left_x、top_left_y、bottom_right_x和bottom_right_y。

top_left_x = column_index
top_left_y = row_index
bottom_right_x = column_index
bottom_right_y = row_index

if column_index >= 1:
    top_left_x -= 1

if row_index >= 1:
    top_left_y -= 1

if column_index <= width-2:
    bottom_right_x += 1

if row_index <= height -2:
    bottom_right_y += 1

for y in range(top_left_y, bottom_right_y +1):
    for x in range(top_left_x, bottom_right_x +1):

周围有效空单元格：首先，此条件将评估所选单元格的周围（这意味着其周围的8个单元格）是否至少有一个任意数量的有效空单元格，在本例中至少为三个，但您可以根据需要设置数字。 有效空单元格是指被至少一个任意数量的空单元格包围的单元格，在本例中至少为四个，但您可以根据需要设置数字。因此，基本上，我们迭代周围的空单元格，并递归地迭代它们周围的空单元格。此递归仅执行一次，这意味着我们不检查我们正在检查的空单元格周围的空单元格是否也有效。例如，一个有效空单元格有四个周围的空单元格，但这些空单元格没有其他四个周围的空单元格，因此它们可能无效，但我们不检查。出于性能原因，当达到所需数量的周围有效空单元格和它们周围的空单元格时，不应再进行迭代以搜索有效空单元格，因为我们已经满足条件。如果所选单元格位置没有足够的周围有效空单元格，则被丢弃为无效以放置地雷。
所有连续的地雷仍然有效：此第二个条件将评估在将所选单元格放置为地雷的情况下，所有连续的地雷是否仍然有效。此条件应在与周围有效空单元格相同的迭代中进行检查。但是这里有一个区别，此条件将递归地评估，直到达到mine_concatenation_limit或所有地雷仍然有效。在这种情况下，mine_concatenation_limit设置为三，这意味着永远不应该有超过三个地雷在一起，但您可以根据需要设置数字。当我们评估此条件时，对于每个连接的地雷，我们再次检查周围有效空单元格条件。如果一个地雷无效，则所选单元格将被丢弃为无效以放置地雷。
如果所有条件都满足，则我们可以将所选单元格放置为地雷。如果没有，则将失败尝试计数器加1。

退出循环

一旦我们退出循环，我们需要检查原因。如果所有的地雷都被放置，那么我们可以继续。 如果没有，那么我们应该重新开始循环，再次尝试。这将重复进行，直到正确的地图生成或达到max_fails。

3. 完成地图

现在我们有了一个正确的地图生成，我们应该通过添加围绕所有地雷的数字并向玩家提供关于它们位置的信息来完成它。这可以通过再次迭代所有单元格来完成，在每个单元格上，如果它不是地雷，则将1添加到每个周围单元格的当前值中。这将得到一个地图，其中包含地雷及其周围所有单元格的数字。

for y in range(top_left_y, bottom_right_y +1):
    for x in range(top_left_x, bottom_right_x +1):

        # If the coordinates x & y are the mine cell itself...
        if x == column_index and y == row_index:
            continue

        # Value of the surrounding cell.
        value = matrix[y][x]

        # If the surrounding cell does not contain a mine...
        if value != -1:
            matrix[y][x] += 1

4. 运行验证器

现在我们完成了地图，需要确保它至少有一个可能的解决方案。虽然我们按照一定的条件放置地雷，但这并不足以确保地图至少有一个可能的解决方案。这些条件帮助我们使地雷的位置更加分散、有趣，并增加地图具有至少一个可能的解决方案的可能性。如果求解器无法解决生成的地图，则我们重新开始，注意我们仍然在主循环中。如果求解器实际上解决了生成的地图，则我们退出主循环并准备进行有效载荷或更新游戏等操作。

验证器

验证器不会被解释为一个单独的算法，但至少会对那些想知道我们是如何做到的人进行总结。

我们的验证器由两部分组成：逻辑操作和矩阵操作。

逻辑运算：首先，验证器使用逻辑运算来简化和解决大多数情况。通常这会使游戏接近完成。但如果发现一个复杂的情况，验证器就会切换到使用矩阵运算。
矩阵运算：使用矩阵和数学（解线性矩阵方程组）来确定哪些单元格可能是地雷，如果情况太复杂，它可能会使用预测和近似（最小二乘法解线性矩阵方程组）。在使用预测的情况下，如果算法失败并“输掉了游戏”，则求解器确定生成的地图没有至少一个可能的解。与逻辑运算相比，矩阵运算的灵活性要低得多，但在最复杂的情况下计算速度更快，效果更好。

总结

这是一种构建强大且高效算法的好方法，它考虑了某些条件并进行某些验证，以确保生成的MineSweeper地图不仅可以解决，而且还要有趣和具有挑战性。此实现动态生成地图，允许许多配置，例如难度或算法执行时间。该算法非常灵活，适用于小游戏（网格区域只有9个单元格）以及对面积为数千个单元格的巨大网格也强大且高效。

如果您有任何问题，请随时提问！

- Angel KS

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

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

- Yanick Rochon · Accepted Answer

也许可以这样写：

grid = [n,m]   // initialize all cells to 0
for k = 1 to number_of_mines
   get random mine_x and mine_y where grid(mine_x, mine_y) is not a mine
   for x = -1 to 1
      for y = -1 to 1
         if x = 0 and y = 0 then
            grid[mine_x, mine_y] = -number_of_mines  // negative value = mine
         else 
            increment grid[mine_x + x, mine_y + y] by 1

就这样了...

** 编辑 **

由于该算法可能导致某些地雷分组过于密集，或者更糟糕的是非常分散（因此无聊），因此在生成mine_x和mine_y数量时可以添加额外的验证。例如，要确保至少有3个相邻单元格不是地雷，甚至可能限制过于相距的地雷数量，等等。

** 更新 **

我已经尝试使用 JS bin 并创建了一个功能性的扫雷游戏演示，仅是为了展示本答案中描述的算法。我没有优化生成的地雷位置的随机性，因此有些游戏可能会变成不可能或者太容易。而且，在网格中没有限制地雷数量的验证，因此您可以创建一个 2x2 的网格，有 1000 个地雷...但是这只会导致无限循环 :) 好好享受吧！