給貓看的遊戲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