给猫看的游戏AI实战（四）眼见为实——让AI的思考过程可视化

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

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

1、算法可视化

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

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

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

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

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

那么我们先来画个迷宫。

2、图形化显示数组内容

1、定义地图大小，并创建一个二维数组map代表地图里的元素（空地、墙、起点、终点等等）（奶牛关的文本编辑器实在是···我这里用截图的方式呈现代码，大家将就看吧，文章最下面有完整的代码链接）

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

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

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

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

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

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的伪代码：

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

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

StartCoroutine(BFS());

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

2、显示搜索过的路线。

我的这个做法效率很低，先删除所有格子，然后把数组里的起点、终点、探索过的部分都重新生成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工程地址：

GitHub GameMap

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

对游戏开发感兴趣的同学，欢迎围观：【皮皮关游戏开发教育】 定期更新各种教程，干货。对咱有信心的，还可以直接来围观咱的线下教育：）

官网地址：http://levelpp.com/

游戏开发技术交流群：610475807

微信公众号：皮皮关