战棋游戏中使用 Flood Fill 算法计算行动范围

发表于 更新于 分类于 本文字数： 2.2k 阅读时长 ≈ 8 分钟
最近在做一款战棋类游戏, 使用到了经典的 Flood Fill 算法来实现计算行动范围

环境

文章中的项目是使用 Unity 创建的 2D 游戏项目, 代码是基于 Microsoft Visual Studio 编写, 使用的编程语言是 csharp.

思想

Flood Fill 算法翻译为中文可以叫: "洪水填充" 算法.

从起始位置开始, 不断向外围进行检测, 就像从中心一点向外不断蔓延的洪水一般.

话说这个蔓延方式也不像洪水啊, 不应该是核弹爆炸嘛~ 今天又是核平的一天呐~ 😅

实现原理

Flood Fill 算法的基本原理是基于一个待检查队列, 这个队列中存放接下来待检查的结点, 首先取出待检查队列中一个结点, 检查其坐标周围的四个结点,

Flood Fill 1

将这个四个结点中满足条件的结点添加到待检查队列, 之后从待检查队列中取出下一个待检查结点以同样的规则进行检查, 再将满足条件的结点添加到待检查队列, 如此反复,

Flood Fill 2

直到将待检查队列中的结点全部检查完毕!

定义待检查队列中的结点类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/// <summary>
/// Data Struct 范围结点
/// </summary>
public class DS_FloodFill_Node
{
    /// <summary>
    /// 结点的 X 坐标
    /// </summary>
    public int positionX;

    /// <summary>
    /// 结点的 Y 坐标
    /// </summary>
    public int positionY;

    /// <summary>
    /// 到达此结点时剩余的步数
    /// </summary>
    public int overStep;
}

定义两个 int 字段存储结点的坐标, 再定义一个 overStep, 表示从起始坐标到达此结点所在坐标时剩余的步数.

创建算法类

1
2
3
4
5
6
7
8
/// <summary>
/// 算法类: Flood Fill
/// 洪水填充
/// </summary>
public class AR_FloodFill
{
    // 算法具体内容
}

创建算法需要的临时变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/// <summary>
/// 地图数据
/// </summary>
private EM_Terrain[,] map;

/// <summary>
/// 1. 检查过的格子
/// 2. 可行动范围 (无其他数据)
/// </summary>
private bool[,] flagChecked;

/// <summary>
/// 可行动范围 (有其他数据)
/// </summary>
private readonly List<DS_FloodFill_Node> range = new List<DS_FloodFill_Node>();

/// <summary>
/// 1. 循环检查游标, 指明列表中 "当前待检查结点" 的位置
/// 2. 循环检查次数计数器
/// </summary>
private readonly int checkIndex = 0;

/// <summary>
/// 是否无视地形
/// </summary>
private bool isIgnoreTerrain;

  • map 是整张地图的数据, 虽然这里只是一个枚举数组, 但是项目中有一个字典变量, 通过这个枚举值便可以查到特定的地形类型所对应的全部数据, 包含地形名称, 地形提供的闪避率, 防御力, 攻击力, 生命回复等等. 全部的数据结构牵扯的东西比较多, 这里就不列出了.

  • flagChecked 用来标记算法在循环过程中哪些坐标已经被检查通过了, 这样可以避免重复检查. 另外, flagChecked 使用的存储方式是二维数组, 它是将检查过的位置标记在相应的坐标处, 且只标记通过的位置, 即 flagChecked 的值就是最终的行动范围, 但是它不附带其他的数据.

  • range 记录的也是被检查通过的结点, 但是它会将全部信息进行保存.

  • checkIndex 是待检查队列的游标, 表示当前检查到什么位置了.

  • isIgnoreTerrain 标识是否无视地形, 用于区分检测的是移动范围还是攻击范围.

实现 Flood Fill 算法

主方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/// <summary>
/// 洪水填充算法
/// </summary>
/// <param name="map">地图数据</param>
/// <param name="startPositionX">人物坐标 X</param>
/// <param name="startPositionY">人物坐标 Y</param>
/// <param name="minRange">最小直接行动范围</param>
/// <param name="maxRange">最大直接行动范围</param>
/// <param name="isIgnoreTerrain">是否无视地形</param>
/// <returns>可行动范围</returns>
public bool[,] FloodFill(EM_Terrain[,] map, int startPositionX, int startPositionY, int minRange, int maxRange, bool isIgnoreTerrain)
{
    // 地图
    this.map = map;

    // 是否无视地形
    this.isIgnoreTerrain = isIgnoreTerrain;

    // 初始化存放已检查格子的数组
    flagChecked = new bool[map.GetLength(0), map.GetLength(1)];
    for (int i = 0; i < flagChecked.GetLength(0); i++)
    {
        for (int j = 0; j < flagChecked.GetLength(1); j++)
        {
            flagChecked[i, j] = false;
        }
    }

    // 将起点存入 可行动范围
    DS_FloodFill_Node startPosition = new DS_FloodFill_Node
    {
        positionX = startPositionX,
        positionY = startPositionY,
        overStep = maxRange,
    };
    range.Add(startPosition);
    flagChecked[startPositionX, startPositionY] = true;

    // 扫描地图上特定坐标周围的格子, 计算行动范围
    ScanMap(checkIndex);

    // 判断是否去除起始坐标
    RemoveMinRange(minRange);

    // 返回数据
    return flagChecked;
}

这个方法做的事情不多 (读者: 整个 Flood Fill 算法做的事情也不多好吧! !), 首先初始化算法需要的数据, 之后将初始位置存入待检查队列等待第一次检查, 记得同时更新 range 和 flagChecked 的值, 然后便可以使用 ScanMap() 方法检查整张地图了, 最后判断一下是否需要移除起始坐标, 像使用物品是可以对自己使用的, 但是移动的时候原地移动是不算真正移动了的, 攻击也同样不能攻击自己, 最后将计算好的范围返回外部, 由外部进行处理.

ScanMap 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/// <summary>
/// 扫描地图上特定坐标周围的格子, 计算行动范围
/// </summary>
/// <param name="checkIndex">特定坐标的索引</param>
private void ScanMap(int checkIndex)
{
    // 只要还没有将所有的可移动范围检测完, 就继续检测
    while (checkIndex < range.Count)
    {
        int positionX = range[checkIndex].positionX;
        int positionY = range[checkIndex].positionY;
        int overStep = range[checkIndex].overStep;

        CheckMapPos(positionX, positionY + 1, overStep);
        CheckMapPos(positionX - 1, positionY, overStep);
        CheckMapPos(positionX, positionY - 1, overStep);
        CheckMapPos(positionX + 1, positionY, overStep);

        checkIndex++;
    }
}

ScanMap() 方法就是一个循环, 针对当前坐标计算出周围坐标, 然后使用 CheckMapPos() 方法检测特定坐标.

CheckMapPos() 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/// <summary>
/// 检查地图上特定坐标
/// </summary>
/// <param name="positionX">特定坐标 X 轴</param>
/// <param name="positionY">特定坐标 Y 轴</param>
/// <param name="overStep">剩余步数</param>
private void CheckMapPos(int positionX, int positionY, int overStep)
{
    // 判断是否越界
    if (positionX < 0 || positionX >= map.GetLength(0))
    {
        return;
    }

    // 判断是否越界
    if (positionY < 0 || positionY >= map.GetLength(1))
    {
        return;
    }

    // 判断是否可以到达当前单元格
    overStep = isIgnoreTerrain ? overStep - 1 : overStep - AD_Terrain.AD_Terrains[map[positionX, positionY]].BaseStepCost;
    if (overStep < 0)
    {
        return;
    }

    // 如果当前单元格已经在行动范围内了
    if (flagChecked[positionX, positionY])
    {
        int checkedRangeDataIndex = GetCheckedRangeDataIndex(positionX, positionY);
        if (overStep > range[checkedRangeDataIndex].overStep)
        {
            // 更新在行动范围内的数据
            DS_FloodFill_Node updatePosition = new DS_FloodFill_Node
            {
                positionX = positionX,
                positionY = positionY,
                overStep = overStep,
            };
            range[checkedRangeDataIndex] = updatePosition;
        }
    }
    else // 如果当前单元格没有在行动范围内
    {
        DS_FloodFill_Node currentPosition = new DS_FloodFill_Node
        {
            positionX = positionX,
            positionY = positionY,
            overStep = overStep,
        };
        range.Add(currentPosition);
        flagChecked[positionX, positionY] = true;
    }
}

CheckMapPos() 方法的重点就是退出条件.

退出条件

  1. 是否越界

由于我项目中地图的坐标是从 (0, 0) 开始设计的, 所以这里的越界判断自然就是这样的写法啦~

  1. 是否可以到达当前坐标

这里的判断使用了 'isIgnoreTerrain' 变量, 当无视地形时, 每移动一个位置消耗的步数为 1, 用于使用物品以及攻击范围的计算, 不无视地形时, 每移动一个位置消耗的步数需要根据地形类型进行判断, 用于计算移动范围.

[注] 另一个需要注意的是 overStep, 里面保存的值不一定是最大剩余步数.

这个问题是计算行动范围时会遇到的特殊情况. 由于每个坐标消耗的步数不同, 所以经常会出现这种情况:

Flood Fill 3

假设行动步数为 10 步, 翻越城镇城墙消耗 5 步, 进入城镇消耗 1 步, 那么:

路线1首先检测到了城镇入口, 到达时剩余步数为: 4;

路线2之后检测到了城镇入口, 到达时剩余步数为: 6;

于是单独写一个 if 进行判断, 如果结点已经检查过了, 那么比较两次路线的剩余步数, 并更新为大的剩余步数. 当然这个地方不写 (上面代码段中的最后一个 if else 逻辑) 也已经可以充分的实现计算行动范围了.

独立方法

最后便是提取出来的独立方法.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/// <summary>
/// 得到已经检查过的结点
/// </summary>
/// <param name="positionX">特定坐标 X 轴</param>
/// <param name="positionY">特定坐标 Y 轴</param>
/// <returns>结点索引</returns>
private int GetCheckedRangeDataIndex(int positionX, int positionY)
{
    // 已经检查过的就不用比较了, 因为已经检查过的剩余步数肯定已经最大了
    for (int i = checkIndex + 1; i < range.Count; i++)
    {
        if (range[i].positionX == positionX &&
            range[i].positionY == positionY)
        {
            return i;
        }
    }

    return 0;
}

/// <summary>
/// 移除小于最小范围的非法坐标
/// </summary>
/// <param name="minRange"></param>
private void RemoveMinRange(int minRange)
{
    // 记录下起始位置坐标
    int startPositionX = range[0].positionX;
    int startPositionY = range[0].positionY;

    if (minRange > 0)
    {
        for (int i = 0; i < range.Count; i++)
        {
            if (Math.Abs(startPositionX - range[i].positionX) + Math.Abs(startPositionY - range[i].positionY) < minRange)
            {
                flagChecked[range[i].positionX, range[i].positionY] = false;
                range.RemoveAt(i);
                i--;
            }
        }
    }
}

这样最终返回的 bool 数组便是可行动的范围!

参考文章

cocos creator 实现战棋类游戏移动范围效果