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

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

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

1、算法可视化

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

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

GIF

如图，就是简单的抛一个硬币而已，只要定义速度的方向向上为正，向下为负，那么硬币的速度-时间曲线，就是上面的直线了。想一想，抛个硬币试试，是不是很反直觉呢？（ 不要问我和炮姐有什么关系，只是扔个硬币而已 (￣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
在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方法。先说数据结构：
关键的数据结构共有三个。
首先是地图map二维数组本身，这个画地图时已经用到了。
其次是保存每格里的步数的二维数组 int bfs[Height, Width]，前面的标记了数字的图就是。
最后是关键性的，一个任务队列，用List表示即可。List queue = new List();
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、数据结构之后，描述一下算法： 
初始化bfs数组全部为short.MaxValue，初始值是0会带来很多麻烦。
初始点步数为0，设置bfs[start.y, start.x] = 0，然后将start这个点加入到queue最后面去。queue.Add(start);
下面开始循环。从queue中取出第一个元素p，并从queue中删除它。
如果p就是终点，那么我们的任务就完成了。设置终点的步数后退出循环。
依次判断p的上、下、左、右四个相邻元素。相邻的元素q不能超出地图范围，不能是墙；如果q已经被探索过了，那么也不再考虑它（这是BFS特有的处理方式）。
对上一步发现的新的合理的格子q，设置bfs[q.y, q.x] = bfs[p.y, p.x] + 1; 即步数+1。并将q插入队列queue。
回到第3步，如果队列为空就代表探索完毕，没有发现终点（比如终点被挡死了）。 
重点是第5步中，如果某个点已经被探索过、标记过步数，那么后来再探索到它的时候，步数一定大于等于原来的值，也就不需要再考虑它了，只有BFS才有这个性质。未来做其他寻路算法时，要注意如果新的步数小于原来标记的步数，就要执行第6步（设置新的步数并把该点加入queue）。
3、最后描述一下得到了bfs表之后，怎样获得最短路径。
初始化一个path列表代表路径，List path = new List();
从终点开始，设置p为终点，步数为n。
从p的上下左右四个点中找到任意一个步数为n-1的点，加入到path中，将p赋值为这个点。重复本步骤即可，直至p是起点。
完毕，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 queue = new List();
 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 queue = new List();
 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的算法：
如果从queue的后面开始取，就是类似深度优先搜索的算法（另类的DFS）。
如果从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