寻路算法探讨

前言

        我想我可能很长的一段时间都不会在这上面继续研究了，因为我之后的项目大概率是用不上了。我想趁着现在我还记得，且仍然有兴趣，我想对迄今为止我所了解到的寻路算法做一个总结。同时这样也算是给自己之前的工作做整理。

        本文讨论的所有算法都只给出在二维情景下的例子，这当然是因为我自己的项目中也只需要在二维情景下进行寻路。所以这里例子中也只给出二维情景下的例子。

图论

        既然要讨论寻路算法，那么就不得不提到图论。一些寻路算法是需要图论对应的知识。所以我在这里先简单介绍一下图论。如果你已经对图论很熟悉，那么可以直接跳过这部分。

        图论是离散数学的一个分支，研究图（Graph）的性质和应用。图由顶点（Vertex）和连接这些顶点的边（Edge）组成。这里我简单说明一下图论的一些基本概念，后面我们结合具体案例来进行分析。

基本概念

  1. 顶点（Vertex）：图中的基本单位，表示某个事物或对象。顶点也称为节点、结点等。
  2. 边（Edge）：连接顶点的线条，表示顶点之间的关系。边可以是有向的（Directed Edge）或无向的（Undirected Edge）。
  3. 有向图和无向图（Directed Graph and Undirected Graph）：有向图中的边有方向，无向图中的边没有方向。
  4. 权重（Weight）：边的权重表示边的值，如距离、成本等。
  5. 路径：路径是从一个顶点到另一个顶点的路线。而最短路径则是此顶点到对应顶点权重（代价）最小的路径。

        实际上，图的基本概念不只上述的5点，但是因为后续案例中不需要，所以这里就不再赘述了。

具体案例

        现在我们直接结合具体案例来进行分析。

案例设定

        既然我们要讨论案例，那我们先确定一下案例中的一些设定。下面所有的例子都是在二维情景下进行的。场景中的地图信息被存储在一个二维数组中，数组中的每个元素代表一个格子。每个格子都有一个权重值，代表进入这个格子所要付出的代价。如果代价小于等于0，则表示这个格子的代价是无限的，即不可通过。这里设定此二维数组的名称为mapInfo。理论上，在这样的地图上走动，角色可以上下左右移动，也可以对角移动。但是这里我为了案例方便只考虑上下左右的移动。这里我给出的寻路算法为了寻求最短代价的路径。当然如果你只想找到可通过的最短路径，那么只需要所以正向的代价设置为1就好了（代价小于等于0表示不可通过）。

        下面是Unity中Vector2Int示例，并非Unity本身的实现。下面的代码中我会用到这个类来简化一些代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
// Vector2Int示例，并非Unity本身的实现
public class Vector2Int
{
    public Vector2Int(int x,int y)
    {
        this.x = x;
        this.y = y;
    }
    int x;
    int y;
}

Vector2Int.zero = new Vector2Int(0, 0);

之后用到的类似Vector3Int也是差不多的逻辑实现。

基础算法

        这部分是我认为寻路中最基础的算法，它可以实现一些简单的寻路需求。但是其具体的性能和表现或许就不太如意了。但是在一些简单的场景中，它仍然可以提供一个比较好的解决方案。

深度优先和广度优先搜索

        关于广度优先搜索（BFS），我之前还写过对应的文章，算法—-广度优先搜索。文章中还有对应的例题。当然我仍然会在这里再次介绍一下，但是我不会像上面的文章一样给出例题。

        广度优先搜索（Breadth First Search，简称BFS），又称为宽度优先搜索。它和深度优先搜索（Depth First Search，简称DFS）一样，是一种图形搜索算法，用来遍历或搜索树或图的算法，从而找到最短路径。它们主要的不同在于它们寻路的决策，正如其名称所示，深度优先搜索会优先探索不同层的节点，而广度优先搜索会优先探索同一层的节点。下图就很明显可以看出它们决策的区别。

上图左边是广度优先搜索，右边是深度优先搜索。绿色的线表示他们的路径。

        以我们上面给出的案例为例：角色可以上下左右移动。对于BFS而言，对于当前角色所在位置，它优先考虑左右，然后再考虑上下。而对于DFS而言，它优先考虑上下，然后再考虑左右。这时候会产生一个问题，我们会多次访问同一个格子。比如我们这时候在[1,1]格子上，那么BFS会优先考虑[1,2]格子，而在[1,2]格子时，BFS又会再考虑[1,1]格子，DFS也是如此。因此我们需要一个东西来记录我们已经访问过的格子，从而避免重复访问。

        本文讨论的寻找路径不是得到一个最短的路径，而是要得到一个代价最小的路径（当然如果所有的路径的代价都是一样的，那么我们就是求最短的路径）。因此我们可能会存在重复访问的情况。但是我们要避免无节制的重复访问。既然我们是要求最小代价的路径，那么我们只需要记录到达对应节点最小的代价。当进入这个节点的代价小于之前记录的代价时，我们才重复访问这个节点。既然要记录每一个节点的最小代价，那么我们就需要一个和mapInfo一样大小的数组来记录每一个节点的最小代价。这个数组我们就叫做globalPrice。具体代码如下:

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
private void Bfs(int[][] mapInfo, int[][] globalPrice, List<Vector2Int> curPath, Vector2Int pos)
{
    if (pos == target)
    {
        this.curPath = new List<Vector2Int>(curPath);
        return;
    }
    int row = mapInfo.Length;
    int col = mapInfo[0].Length;
    int r = pos.x, c = pos.y;

    for (int j = -1; j < 2; j += 2)
    {
        int curC = c + j;
        if (curC >= 0 && curC < col && mapInfo[r][curC] > 0 && globalPrice[r][c] + mapInfo[r][curC] < globalPrice[r][curC])
        {
            globalPrice[r][curC] = globalPrice[r][c] + mapInfo[r][curC];
            Vector2Int curPos = new Vector2Int(r, curC);
            curPath.Add(curPos);
            Bfs(mapInfo, globalPrice, curPath, curPos);
            curPath.RemoveAt(curPath.Count - 1);
        }
    }

    for (int i = -1;i < 2; i+=2)
    {
        int curR = r + i;
        if(curR >= 0 && curR < row && mapInfo[curR][c] > 0 && globalPrice[r][c] + mapInfo[curR][c] < globalPrice[curR][c])
        {
            globalPrice[curR][c] = globalPrice[r][c] + mapInfo[curR][c];
            Vector2Int curPos = new Vector2Int(curR, c);
            curPath.Add(curPos);
            Bfs(mapInfo, globalPrice, curPath, curPos);
            curPath.RemoveAt(curPath.Count - 1);
        }
    }
}

private void Dfs(int[][] mapInfo, int[][] globalPrice, List<Vector2Int> curPath, Vector2Int pos)
{
    if (pos == target)
    {
        this.curPath = new List<Vector2Int>(curPath);
        return;
    }
    int row = mapInfo.Length;
    int col = mapInfo[0].Length;
    int r = pos.x, c = pos.y;

    for (int i = -1; i < 2; i += 2)
    {
        int curR = r + i;
        if (curR >= 0 && curR < row && mapInfo[curR][c] > 0 && globalPrice[r][c] + mapInfo[curR][c] < globalPrice[curR][c])
        {
            globalPrice[curR][c] = globalPrice[r][c] + mapInfo[curR][c];
            Vector2Int curPos = new Vector2Int(curR, c);
            curPath.Add(curPos);
            Dfs(mapInfo, globalPrice, curPath, curPos);
            curPath.RemoveAt(curPath.Count - 1);
        }
    }

    for (int j = -1; j < 2; j += 2)
    {
        int curC = c + j;
        if (curC >= 0 && curC < col && mapInfo[r][curC] > 0 && globalPrice[r][c] + mapInfo[r][curC] < globalPrice[r][curC])
        {
            globalPrice[r][curC] = globalPrice[r][c] + mapInfo[r][curC];
            Vector2Int curPos = new Vector2Int(r, curC);
            curPath.Add(curPos);
            Dfs(mapInfo, globalPrice, curPath, curPos);
            curPath.RemoveAt(curPath.Count - 1);
        }
    }
}

你会发现BFS和DFS代码几乎是一样的。因为最终我们要获取到对应的路径，所以我这里使用记忆化搜索的方法在找对目标后将对应路径保存在一个全局的'curPath'中。

        BFS和DFS在实现上并不困难，但是它们的性能并不让人满意。大多数情况都是在数据不大且只需要知道是否点位是否可达的情况下。

进阶

迪斯卡算法

        迪斯卡（Dijkstra）算法也是一个经典的最短路径算法。它的主要思想是贪心策略，每次选择当前距离起点最近的节点进行扩展。我们也需要globalPrice（前文说明的数据类型）来记录起点到达其他点位的代价。整体步骤如下：

  1. 指定初始点位，即起点。
  2. 将所有的点位代价默认设定为无穷大。
  3. 将起点加入到优先队列中，这个优先队列以起点到达此处的代价进行排列。
  4. 以队列中最新的点位作为标准，更新此点到达其他点的代价，并将这些点加入到优先队列中。
  5. 重复步骤4。直到找到终点。

因为每次我们是选择代价最小的点位，所以当我们找到终点的时候，那就是其代价最小的时候。这里我将迪斯卡算法作为进阶算法，是因为他其实也有深度搜索和广度搜索的思想。这就要看你觉得代价是深度还是广度了。

        上面的步骤基本上是网络上或者教材上所介绍的迪斯卡算法的步骤。下面的实现中，我进行了一些改动。为了更好展示迪斯卡算法的思想，下面代码是计算起始点位到达全图任意点位的最小路径。我额外增加了一个参数Vector2Int[][] pathOffset。这个参数是用来记录进入这个点的上一个点位是哪个。在一开始默认pathOffset中的每一个元素都是Vector2Int.zero这样我们就可以通过这个参数来记录路径了。下面的用这个参数获取路径的办法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private Stack<Vector2Int> GetPath(Vector2Int[][] pathOffset,Vector2Int target)
{
    int x = target.x;
    int y = target.y;

    Stack<Vector2Int> path = new();
    path.Push(target);
    while (pathOffset[x][y] != Vector2Int.zero)
    {
        int curX = x;
        int curY = y;
        x += pathOffset[curX][curY].x;
        y += pathOffset[curX][curY].y;
        path.Push(new Vector2Int(x, y));
    }
    return path;
}

        迪斯卡算法也依然会存在重复访问的问题，因此我们仍然需要globalPrice来帮助我们排重，且我们也可以得到对应的路径代价。完整代码如下：

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
private void DijkstraFun(int[][] mapInfo, int[][] globalPrice, Vector2Int[][] pathOffset, Vector2Int startPos)
{
    int row = mapInfo.Length;
    int col = mapInfo[0].Length;
    List<Vector2Int> priQueue = new List<Vector2Int>();
    priQueue.Add(startPos);
    globalPrice[startPos.x][startPos.y] = 0;
    while (priQueue.Count > 0)
    {
        var curVal = priQueue[priQueue.Count - 1];
        priQueue.RemoveAt(priQueue.Count - 1);
        for (int i = -1; i < 2; i += 2)
        {
            int x = curVal.x + i;
            int y = curVal.y;
            if (x > -1 && x < row && mapInfo[x][y] > 0 && globalPrice[curVal.x][curVal.y] + mapInfo[x][y] < globalPrice[x][y])
            {
                globalPrice[x][y] = globalPrice[curVal.x][curVal.y] + mapInfo[x][y];
                priQueue.Add(new Vector2Int(x, y));
                pathOffset[x][y] = new Vector2Int(-i, 0);
            }
        }

        for (int i = -1; i < 2; i += 2)
        {
            int x = curVal.x;
            int y = curVal.y + i;
            if (y > -1 && y < col && mapInfo[x][y] > 0 && globalPrice[curVal.x][curVal.y] + mapInfo[x][y] < globalPrice[x][y])
            {
                globalPrice[x][y] = globalPrice[curVal.x][curVal.y] + mapInfo[x][y];
                priQueue.Add(new Vector2Int(x, y));
                pathOffset[x][y] = new Vector2Int(0, -i);
            }
        }

        priQueue.Sort((x, y) =>
        {
            return globalPrice[y.x][y.y].CompareTo(globalPrice[x.x][x.y]);
        });
    }
}

因为当前我使用的Unity版本（2022.3.54f1c1）并不支持Csharp的优先队列，所以我这里使用List来模拟优先队列。代码上确实很“难看”，但是大家这里明白对应的逻辑就行了。下面是我使用上面代码改造后的示例：

迪斯卡算法也可以如上文提到的深（广）度遍历一样，到达目标点位后，我们就可以退出逻辑得到对应的路径。与深（广）度遍历不同的是，迪斯卡算法是贪心算法，因此它只要到达目标点位那得到的路径一定是代价最小的路径。

A Star算法

        A Star算法又称A星算法（A*算法），它是迪斯卡算法的改进版本。它与迪斯卡算法的区别在于，A星算法提出了一个启发函数的概念。它对于节点优先级的计算，不仅仅只考虑了节点对应的代价，还考虑了其他因素。因此它可以更快的找到最短且代价最小的路径。这个其他因素就是启发函数。

        网上大多数介绍A星算法都会用曼哈顿距离来作为启发函数。但是曼哈顿距离并不一定是最佳的启发函数，这个要考虑到你实际的项目情况。当你可以8个方向进行位移的时候，曼哈顿距离就不太行了。

        我个人在用A星算法的时候，我只考虑了曼哈顿距离，因为我项目中除了不可达节点外，其他的节点权重一致。当然路径中代价的计算本来也是要考虑的一环，因此这里我使用曼哈顿+代价做为启发函数。下面A星算法的实现也是从上面的迪斯卡算法进行改进。

        在实现中，我们需要当前值额外对应的启发函数值。代码中的启发函数，我参照了《路径规划之 A* 算法》这篇文章的实现。实现如下：

1
2
3
4
private int HeuristicFun(int price,Vector2Int curNodePos,Vector2Int targetPos)
{
    return price * (Mathf.Abs(curNodePos.x - targetPos.x) + Mathf.Abs(curNodePos.y - targetPos.y));
}

最终完整的A星算法如下：

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
56
57
58
59
60
61
62
63
64
65
66
67
68
private void AStarFun(int[][] mapInfo, int[][] globalPrice, Vector2Int[][] pathOffset, Vector2Int startPos, Vector2Int targetPos)
{
    int row = mapInfo.Length;
    int col = mapInfo[0].Length;
    List<Vector3Int> priQueue = new List<Vector3Int>();
    priQueue.Add(new Vector3Int(startPos.x,startPos.y,0));
    curNode = startPos;
    globalPrice[startPos.x][startPos.y] = 0;
    while (priQueue.Count > 0)
    {
        var curVal = priQueue[priQueue.Count - 1];
        curNode = new Vector2Int(curVal.x,curVal.y);
        if (curNode == targetPos)
            break;

        priQueue.RemoveAt(priQueue.Count - 1);
        for (int i = -1; i < 2; i += 2)
        {
            int x = curVal.x + i;
            int y = curVal.y;
            var curNodePos = new Vector2Int(x, y);
            if (x > -1 && x < row)
            {
                if (mapInfo[x][y] > 0)
                {
                    if (mapInfo[x][y] + globalPrice[curVal.x][curVal.y] < globalPrice[x][y])
                    {
                        globalPrice[x][y] = mapInfo[x][y] + globalPrice[curVal.x][curVal.y];
                        priQueue.Add(new Vector3Int(x, y, HeuristicFun(mapInfo[x][y], curNodePos, targetPos)));
                        pathOffset[x][y] = new Vector2Int(-i, 0);
                    }
                }
                else
                {
                    globalPrice[x][y] = int.MinValue;
                }
            }
        }

        for (int i = -1; i < 2; i += 2)
        {
            int x = curVal.x;
            int y = curVal.y + i;
            var curNodePos = new Vector2Int(x, y);
            if (y > -1 && y < col)
            {
                if (mapInfo[x][y] > 0)
                {
                    if (mapInfo[x][y] + globalPrice[curVal.x][curVal.y] < globalPrice[x][y])
                    {
                        globalPrice[x][y] = mapInfo[x][y] + globalPrice[curVal.x][curVal.y];
                        priQueue.Add(new Vector3Int(x, y, HeuristicFun(mapInfo[x][y], curNodePos, targetPos)));
                        pathOffset[x][y] = new Vector2Int(0, -i);
                    }
                }
                else
                {
                    globalPrice[x][y] = int.MinValue;
                }
            }
        }

        priQueue.Sort((x, y) =>
        {
            return y.z.CompareTo(x.z);
        });
    }
}

        A星存在一个问题，如果我们只是寻到对应的目标节点就退出那不一定是最小代价的路径。这条路径只能说是在我们启发函数的规则下，最小代价的路径。如果我们需要真正的最小代价路径，那么A星并不能符合我们的需求。比如下面这种情况：

左边是上面A星算法给出的答案，右边则是最优路径。出现这样的情况就是因为现在的启发函数计算优先级便是如此。所以如果你需要快速得到一条可达目标点的路径，且代价是你能接受的（这取决于你如何使用启发函数），那么A星算法是可以满足你的需求的。

扩展:其他的寻路算法

弗洛伊德算法：文章链接:一文彻底搞懂Floyd算法（弗洛伊德算法）

上面这些算法是我在项目研发中看到的，但是我觉得不行。因此我不在这篇文章中说明了，只是贴出对应的文章。如果后续我继续做这个项目，遇到了新的寻路算法，那么再补充上去。

参考文章

碎语闲言

        我本来是想做弗洛伊德算法的，但是我发现真的要把它应用在游戏上很困难，因此我就放弃了。这篇文章，主要还是为了记录A星算法的实现。之前没接触的时候，我真的觉得A星算法很高大上的样子。现在我明白了，真正厉害的不是A星的思想，而是对应的启发函数。怪不得在游戏中，大家都是用A星来做寻路的，差距一个天，一个地。恰好这篇文章在四月份写完了，今年4月份的文章有着落了。