上一节我们学习了AI状态机的基本使用方法，让AI具有了进攻、追击、回退等基本功能。本来今天是想继续深入状态机的，但是其实未来状态机AI相对来说不再是技术发展的主流，在复杂AI的项目中，它的地位被行为树取代了许多。

不久之后我们会用行为树的方法再看看复杂AI行为的设计，由于行为树的设计比较复杂，对初学者很不友好 ╮(╯▽╰)╭。所以今天我们先换一个方向突破——AI寻路，但是本文的重点并不在寻路算法本身。先展示一下今天要做的最终效果：

1、算法可视化

图像可以帮助理解抽象的概念，这是显然的。但是如果只把图像理解为帮助理解的工具，就太肤浅了。举个例子：

一个物体的速度从10开始，一直匀速降低。先降低到0，继续降低到-10为止。这个图像表示了一个怎样的情景呢？放一个动图：

如图，就是简单的抛一个硬币而已，只要定义速度的方向向上为正，向下为负，那么硬币的速度-时间曲线，就是上面的直线了。想一想，抛个硬币试试，是不是很反直觉呢？（ 不要问我和炮姐有什么关系，只是扔个硬币而已 (￣y▽￣)~* 。）

所以说，图像并不仅仅是一种辅助工具，它可以帮助我们换一个角度理解世界。很多时候，我们实现了一个很牛的算法，A*寻路、碰撞检测、三角剖分等等，但是也仅仅是按照前人的方法实现了而已，而对算法的理解，还停留在很低的层面上。如果这时候从不同的角度让算法直观地表现出来，那么算法存在的缺陷、优化的方法、适用的范围等等一系列深度问题，都会显而易见了。

如果你还是不知道这个方法好玩在哪，建议翻到本文最后第5段，里面有很多好玩的例子。本文最后面有工程下载地址，也可以先运行工程试试。

那么我们先来画个迷宫。

2、图形化显示数组内容

1、定义地图大小，并创建一个二维数组map代表地图里的元素（空地、墙、起点、终点等等）

const int Height = 20;
const int Width = 30;
int[,] map = new int[Height, Width];

// 在map里填写以下数字，代表开始点、结束点、墙
const int START = 8;
const int END = 9;
const int WALL = 1;

2、在Unity中放置一个平面，代表地面，大小和位置可以在我们画出地图后再调节也可以。

3、以下代码可以将数组里的墙显示出来，map的前一个元素是Y坐标，第二个元素是X坐标：

void InitMap0()
   {
        // 新建一个GameObject walls作为所有墙的父节点
        var walls = new GameObject();
        walls.name = "walls";
        for (int i = 0; i < H; i++)
        {
            for (int j = 0; j < W; j++)
            {
                if (map[i, j] == WALL)
                {
                    var go = Instantiate(prefab_wall, new Vector3(j * 1, 0.5f, i * 1), Quaternion.identity, walls.transform);
                }
            }
        }
    }

4、现在我们的数组内容都是默认的0，我们可以用很多方法初始化数组的值，这里提供一个直接编写文本文件来定义地图的方法：

public void ReadMapFile()
    {
        string path = Application.dataPath + "//" + "map.txt";
        if (!File.Exists(path))
        {
            return;
        }
        FileStream fs = new FileStream(path, FileMode.Open, FileAccess.Read);
        StreamReader read = new StreamReader(fs, Encoding.Default);

        string strReadline = "";
        int y = 0;

        // 跳过第一行
        read.ReadLine();
        strReadline = read.ReadLine();

        while (strReadline!=null && y<H)
        {
            for (int x=0; x<W && x<strReadline.Length; ++x)
            {
                int t;
                switch(strReadline[x])
                {
                    case '1':
                        t = 1;
                        break;
                    case '8':
                        t = 8;
                        break;
                    case '9':
                        t = 9;
                        break;
                    default:
                        t = 0;
                        break;
                }
                // Debug.Log("x, y"+ x +" " + y);
                map[y, x] = t;
            }
            y += 1;
            strReadline = read.ReadLine();
        }
        read.Dispose();//文件流释放  
        fs.Close();
    }

在Unity的Assets目录中新建一个map.txt文件，可以用记事本直接画地图，空格代表空白，1代表墙，第一行不包含在内。注意行数、列数和代码中的定义一致。类似下面这样：

----+----+----+----+----+----+
          1      11111111     $
          1                   $
          1                   $
          1                   $
                              $
1111111111111 11111111        $
              1               $
              1               $
              1               $
              1               $
              1               $
              1               $
              1               $
              1               $
        11111111111111        $
                              $
                              $
                              $
                              $
                              $

$用来标记每行末尾，没有特别的意思。这样初始化地图就变得很简单了。注意编辑器一定要用记事本之类的等宽字体编辑哦，否则字符宽度不同就麻烦了 （￣工￣lll）。

5、测试看看。如果地面对的不齐，只要调整地面位置就可以了。

3、广度优先搜索（BFS）

广度优先搜索是寻路算法的基础。所谓广度优先，就是在搜索时，先尽可能把一定距离内的点全部探索完毕，然后再探索稍微远一点的所有点，以此类推，直到达到足够远的地方发现终点。

如图，数字代表探索的顺序。探索是从入口开始，先探索所有附近1格的节点，然后是2格、3格，依次类推，和本文开头的动图是一致的。

1、本文不再一步一步讲解BFS细节的实现，只是提示一些细节，你就可以实现自己的BFS方法。先说数据结构：

1. 关键的数据结构共有三个。
2. 首先是地图map二维数组本身，这个画地图时已经用到了。
3. 其次是保存每格里的步数的二维数组 int bfs[Height, Width]，前面的标记了数字的图就是。
4. 最后是关键性的，一个任务队列，用List表示即可。List<Pos> queue = new List<Pos>();
5. Pos代表每一个格子，由于格子坐标是整数（整数可以直接做数组索引），不能用Vector2，定义如下：

// Pos代替Vector2，代表位置。整数
public class Pos
{
    public int x = 0;
    public int y = 0;
// 多个初始化函数是为了方便使用
    public Pos()
    {
    }

    public Pos(Pos p)
    {
        x = p.x;
        y = p.y;
    }

    public Pos(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
// 定义了Equals函数，判断相等时比较方便。p.Equals(q)，就可以判断p和q是否相等了。
    public bool Equals(Pos p)
    {
        return x == p.x && y == p.y;
    }
}

2、数据结构之后，描述一下算法：

1. 初始化bfs数组全部为short.MaxValue，初始值是0会带来很多麻烦。
2. 初始点步数为0，设置bfs[start.y, start.x] = 0，然后将start这个点加入到queue最后面去。queue.Add(start);
3. 下面开始循环。从queue中取出第一个元素p，并从queue中删除它。
4. 如果p就是终点，那么我们的任务就完成了。设置终点的步数后退出循环。
5. 依次判断p的上、下、左、右四个相邻元素。相邻的元素q不能超出地图范围，不能是墙；如果q已经被探索过了，那么也不再考虑它（这是BFS特有的处理方式）。
6. 对上一步发现的新的合理的格子q，设置bfs[q.y, q.x] = bfs[p.y, p.x] + 1; 即步数+1。并将q插入队列queue。
7. 回到第3步，如果队列为空就代表探索完毕，没有发现终点（比如终点被挡死了）。

重点是第5步中，如果某个点已经被探索过、标记过步数，那么后来再探索到它的时候，步数一定大于等于原来的值，也就不需要再考虑它了，只有BFS才有这个性质。未来做其他寻路算法时，要注意如果新的步数小于原来标记的步数，就要执行第6步（设置新的步数并把该点加入queue）。

3、最后描述一下得到了bfs表之后，怎样获得最短路径。

1. 初始化一个path列表代表路径，List<Pos> path = new List<Pos>();
2. 从终点开始，设置p为终点，步数为n。
3. 从p的上下左右四个点中找到任意一个步数为n-1的点，加入到path中，将p赋值为这个点。重复本步骤即可，直至p是起点。
4. 完毕，path即代表最短路径。

4、探索过程的可视化

一般来说，函数的执行要么是一次执行完毕，要么是每帧执行一次。在算法做可视化的时候，这是个很头疼的问题。

1、Unity提供的协程机制可以很方便地让函数变为每帧执行1到n步，可以随意控制。为了说明方便，这里写一个BFS的伪代码：

void BFS()
{
    bfs = new int[map.GetLength(0),map.GetLength(1)];
    将bfs每个元素赋值为int.MaxValue;  bfs_search[i, j] = short.MaxValue;
    List<Pos> queue = new List<Pos>();
    bfs[startPos.y, startPos.x] = 0;
    queue.Add(startPos);

    while (queue.Count > 0)
    {
        Pos cur = queue[0];    // cur是当前方格
        queue.RemoveAt(0);
        处理上方方格;
        处理下方方格;
        处理左边方格;
        处理右边方格;
    }
}

如果要每探索出一个方格，都停顿1帧或者零点几秒，可以改成如下形式：

IEnumerator BFS()
{
    bfs = new int[map.GetLength(0),map.GetLength(1)];
    将bfs每个元素赋值为int.MaxValue;  bfs_search[i, j] = short.MaxValue;
    List<Pos> queue = new List<Pos>();
    bfs[startPos.y, startPos.x] = 0;
    queue.Add(startPos);

    while (queue.Count > 0)
    {
        Pos cur = queue[0];    // cur是当前方格
        queue.RemoveAt(0);
        处理上方方格;
        处理下方方格;
        处理左边方格;
        处理右边方格;
        RefreshPath(bfs);      // 刷新场景
        yield return new WaitForSeconds(0.05f);  // 暂停0.05秒
    }
    yield return null;
}

只加了三句话，一个RefreshPath调用，两个yield分别代表暂停和结束；还修改了函数返回值为IEnumerator。这个被改写过的函数调用时要这么写：

StartCoroutine(BFS());

关于协程就这样简单讲解一下。协程在Unity中非常有用，可以把顺序逻辑改为分时间执行。编写时参考示例工程，或者看一下更详细的Unity入门文章吧 ￣ˍ￣。

2、显示搜索过的路线。

 void Refresh()
    {
        // 删除所有格子
        GameObject[] all_go = GameObject.FindGameObjectsWithTag("Path");
        foreach (var go in all_go)
        {
            Destroy(go);
        }

        // 创建起点和终点
        for (int i = 0; i < H; i++)
        {
            for (int j = 0; j < W; j++)
            {
                if (map[i, j] == START)
                {
                    Debug.Log("START "+ prefab_start);
                    var go = Instantiate(prefab_start, new Vector3(j * 1, 0.5f, i * 1), Quaternion.identity, pathParent.transform);
                    go.tag = "Path";
                }
                if (map[i, j] == END)
                {
                    var go = Instantiate(prefab_end, new Vector3(j * 1, 0.5f, i * 1), Quaternion.identity, pathParent.transform);
                    go.tag = "Path";
                }
            }
        }
    }

    void RefreshPath(short[,] temp_map)
    {
        Refresh();
        // 显示探索过的部分
        for (int i = 0; i < H; i++)
        {
            string line = "";
            for (int j = 0; j < W; j++)
            {
                line += temp_map[i, j] + " ";
                if (map[i,j]==0 && temp_map[i, j] != short.MaxValue)
                {
                    var go = Instantiate(prefab_path, new Vector3(j * 1, 0.1f, i * 1), Quaternion.identity, pathParent.transform);
                    go.tag = "Path";
                }
            }
        }
    }

我的这个做法效率很低，先删除所有格子，然后把数组里的起点、终点、探索过的部分都重新生成Cube显示出来。但是对“算法可视化”的目标来说，这种方法极其方便，通用性很强，可以让画图的过程和算法无关。学习过程中不要考虑效率，记住我们的目标是为了更好的理解算法。

5、修改并理解更多算法

写了这么多功能，只用来学习BFS不觉得很亏吗？咱们再加点料。

1、在BFS中，只要改变从queue中取元素的顺序，就可以实现各种666的算法：

1. 如果从queue的后面开始取，就是类似深度优先搜索的算法（另类的DFS）。
2. 如果从queue中选择离终点最近的元素，就实现了有指导的DFS，这种算法在某些特定地图上比AStar还快。

口说无凭，看动图：

1、轻微修改BFS做成的DFS，实际效果和DFS完全一致。

2、有距离指导的DFS，在路线直接的情况下非常快：

3、AStar，可以看到AStar并不能说绝对的“快”，但是兼顾了广度和深度，绝大多数情况下表现更好：

4、福利。连连看算法，起点和终点之间最多只能有两次折线。这个算法和寻路完全不一样，是用十字射线相交的方法实现的：

以上算法在示例工程中都有。

6、总结

本章主要就是演示算法可视化，让大家体会这种方法的乐趣。算法实现的过程虽然辛苦，但是满足感也是巨大的。

寻路算法做出来之后，怎样将它融合到AI的移动过程中，又是一个新的问题了，好在这个问题并不难，会在未来的文章中一笔带过。游戏开发中，很少有一招鲜、吃遍天的情况，任何算法都有它的适应范围，为了让游戏有更好的体验，AI算法也必须要相应修正。

现在流行的即时战略游戏比如《星际争霸2》中，AI已经有了长足的进步，不仅能在进攻时自动排成队形，尽可能让所有人都能输出伤害，还能在多个友军部队向不同方向前进时，自动错开位置躲避对方。这都是多种算法的综合应用，不用觉得这些方法有多么复杂，关键是深入理解基本算法，在实际项目中做出关键性的调整，才是AI学习的重点。

就啰嗦这么多吧，下次咱们再研究新的问题，再见 (′・ω・`) 。

GameMap工程地址：

https://github.com/mayao11/PracticalGameAI/tree/master/GameMap

————————————————————————————————————

对游戏开发感兴趣的同学，欢迎围观我们：【皮皮关游戏开发教育】 ，会定期更新各种教程干货，更有别具一格的线下小班教育。

我们的官网地址：http://levelpp.com/

我们的游戏开发技术交流群：610475807

我们的微信公众号：皮皮关