前言

最近一直没有做自己的项目，也没有和以前一样开很多新坑。主要是以前的自己总是眼高手低，心里想的很简单动起手来却实现不了，这其实是很致命的一件事。
所以最近一直在造轮子，扫雷、消消乐、炸弹人等一些简单的练手项目。在这些项目的重复造轮子过程中，也遇到了一些有趣的事情，比如说关于这个“扫雷算法”。

示例

其实把这个叫做“扫雷算法”是我自己起的名字，严格说，这个东西应该叫做洪水填充法（Flood Fill），以扫雷为例，其解决的问题效果如下：

常见的场景有扫雷中的区域清除，点击某一个非雷块，要翻开由该点开始的能翻开的非雷块。
常见的填充方法有四向填充与八向填充，这两种填充方法区别如下图所示：

本文以四向填充为例，八向填空可以根据本文思路自行写出。

原理与实现

这一算法的原理非常简单

给定一个起点，填充由该起点开始的周围结点，直到填充满一个给定规则（如触碰到已经访问过的结点）的区域。

本文使用C#语言在Unity中实现该算法。
这一算法实现方法分为递归与非递归实现，其中非递归本质是基于栈的搜索算法，本文使用递归方式实现。
使用递归的话，需要给定递归出口，这里以画图软件“油漆桶”工具为例讲述该算法的实现。

假设在一副图画中，有一圈封闭的曲线，现在需要填充该封闭区域。如下图所示，黑色方块代表该方块为曲线方块：

现在需要将中心区域填充为橙色。我们使用一个二维数组来保存这一幅图。边界标记为true，其余标记为false。
现在实现填充算法，首先我们在点击某一个块的时候我们需要得到该块在二维数组中的位置。所以在初始化的时候需要将每一个块的位置计算出来，这不是本文讲述重点暂且不表。
其核心代码如下：

public void FloodFill(int x, int y, bool[,] visted)
{
    if (x >= 0 && y >= 0 && x < 10 && y < 10)
    {
        if (visted[x, y]) return;          

        visted[x, y] = true;
        buttons[x, y].image.color = aimColor;

        FloodFill(x, y - 1, visted);
        FloodFill(x - 1, y, visted);
        FloodFill(x + 1, y, visted);
        FloodFill(x, y + 1, visted);
    }
}

其中x,y参数代表该块的位置，visted数组保存访问过的结点。递归是上下左右四个方向进行递归。 其运行结果如下图：

应用场景

除上文所说的扫雷与图画中油漆桶的实现之外，这一算法还可以应用于其他游戏中，如消灭星星游戏中的同一色块消除，炸弹人中的炸弹爆炸效果等等。
准确来说这一算法应用的场景就是需要实现一个区域填充或者区域检测的情况。
使用Unity制作的扫雷小游戏源码地址：https://github.com/GhostYii/MiniMinesweeper