給貓看的遊戲AI實戰（四）眼見為實——讓AI的思考過程可視化

上一節我們學習了AI狀態機的基本使用方法，讓AI具有了進攻、追擊、回退等基本功能。本來今天是想繼續深入狀態機的，但是其實未來狀態機AI相對來說不再是技術發展的主流，在複雜AI的項目中，它的地位被行為樹取代了許多。

不久之後我們會用行為樹的方法再看看複雜AI行為的設計，由於行為樹的設計比較複雜，對初學者很不友好 ╮(╯▽╰)╭。所以今天我們先換一個方向突破——AI尋路，但是本文的重點並不在尋路演算法本身。先展示一下今天要做的最終效果：

1、演算法可視化

圖像可以幫助理解抽象的概念，這是顯然的。但是如果只把圖像理解為幫助理解的工具，就太膚淺了。舉個例子：

一個物體的速度從10開始，一直勻速降低。先降低到0，繼續降低到-10為止。這個圖像表示了一個怎樣的情景呢？放一個動圖：

如圖，就是簡單的拋一個硬幣而已，只要定義速度的方向向上為正，向下為負，那麼硬幣的速度-時間曲線，就是上面的直線了。想一想，拋個硬幣試試，是不是很反直覺呢？（ 不要問我和炮姐有什麼關係，只是扔個硬幣而已 (￣y▽￣)~* 。）

所以說，圖像並不僅僅是一種輔助工具，它可以幫助我們換一個角度理解世界。很多時候，我們實現了一個很牛的演算法，A*尋路、碰撞檢測、三角剖分等等，但是也僅僅是按照前人的方法實現了而已，而對演算法的理解，還停留在很低的層面上。如果這時候從不同的角度讓演算法直觀地表現出來，那麼演算法存在的缺陷、優化的方法、適用的範圍等等一系列深度問題，都會顯而易見了。

如果你還是不知道這個方法好玩在哪，建議翻到本文最後第5段，裡面有很多好玩的例子。本文最後面有工程下載地址，也可以先運行工程試試。

那麼我們先來畫個迷宮。

2、圖形化顯示數組內容

1、定義地圖大小，並創建一個二維數組map代表地圖裡的元素（空地、牆、起點、終點等等）

const int Height = 20;nconst int Width = 30;nint[,] map = new int[Height, Width];nn// 在map里填寫以下數字，代表開始點、結束點、牆nconst int START = 8;nconst int END = 9;nconst int WALL = 1;n

2、在Unity中放置一個平面，代表地面，大小和位置可以在我們畫出地圖後再調節也可以。

3、以下代碼可以將數組裡的牆顯示出來，map的前一個元素是Y坐標，第二個元素是X坐標：

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

4、現在我們的數組內容都是默認的0，我們可以用很多方法初始化數組的值，這裡提供一個直接編寫文本文件來定義地圖的方法：

public void ReadMapFile()n {n string path = Application.dataPath + "//" + "map.txt";n if (!File.Exists(path))n {n return;n }n FileStream fs = new FileStream(path, FileMode.Open, FileAccess.Read);n StreamReader read = new StreamReader(fs, Encoding.Default);nn string strReadline = "";n int y = 0;nn // 跳過第一行n read.ReadLine();n strReadline = read.ReadLine();nn while (strReadline!=null && y<H)n {n for (int x=0; x<W && x<strReadline.Length; ++x)n {n int t;n switch(strReadline[x])n {n case 1:n t = 1;n break;n case 8:n t = 8;n break;n case 9:n t = 9;n break;n default:n t = 0;n break;n }n // Debug.Log("x, y"+ x +" " + y);n map[y, x] = t;n }n y += 1;n strReadline = read.ReadLine();n }n read.Dispose();//文件流釋放 n fs.Close();n }n

在Unity的Assets目錄中新建一個map.txt文件，可以用記事本直接畫地圖，空格代表空白，1代表牆，第一行不包含在內。注意行數、列數和代碼中的定義一致。類似下面這樣：

----+----+----+----+----+----+n 1 11111111 $n 1 $n 1 $n 1 $n $n1111111111111 11111111 $n 1 $n 1 $n 1 $n 1 $n 1 $n 1 $n 1 $n 1 $n 11111111111111 $n $n $n $n $n $n

$用來標記每行末尾，沒有特別的意思。這樣初始化地圖就變得很簡單了。注意編輯器一定要用記事本之類的等寬字體編輯哦，否則字元寬度不同就麻煩了 （￣工￣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，代表位置。整數npublic class Posn{n public int x = 0;n public int y = 0;n// 多個初始化函數是為了方便使用n public Pos()n {n }nn public Pos(Pos p)n {n x = p.x;n y = p.y;n }nn public Pos(int x, int y)n {n this.x = x;n this.y = y;n }n// 定義了Equals函數，判斷相等時比較方便。p.Equals(q)，就可以判斷p和q是否相等了。n public bool Equals(Pos p)n {n return x == p.x && y == p.y;n }n}n

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()n{n bfs = new int[map.GetLength(0),map.GetLength(1)];n 將bfs每個元素賦值為int.MaxValue; bfs_search[i, j] = short.MaxValue;n List<Pos> queue = new List<Pos>();n bfs[startPos.y, startPos.x] = 0;n queue.Add(startPos);nn while (queue.Count > 0)n {n Pos cur = queue[0]; // cur是當前方格n queue.RemoveAt(0);n 處理上方方格;n 處理下方方格;n 處理左邊方格;n 處理右邊方格;n }n}n

如果要每探索出一個方格，都停頓1幀或者零點幾秒，可以改成如下形式：

IEnumerator BFS()n{n bfs = new int[map.GetLength(0),map.GetLength(1)];n 將bfs每個元素賦值為int.MaxValue; bfs_search[i, j] = short.MaxValue;n List<Pos> queue = new List<Pos>();n bfs[startPos.y, startPos.x] = 0;n queue.Add(startPos);nn while (queue.Count > 0)n {n Pos cur = queue[0]; // cur是當前方格n queue.RemoveAt(0);n 處理上方方格;n 處理下方方格;n 處理左邊方格;n 處理右邊方格;n RefreshPath(bfs); // 刷新場景n yield return new WaitForSeconds(0.05f); // 暫停0.05秒n }n yield return null;n}n

只加了三句話，一個RefreshPath調用，兩個yield分別代表暫停和結束；還修改了函數返回值為IEnumerator。這個被改寫過的函數調用時要這麼寫：

StartCoroutine(BFS());n

關於協程就這樣簡單講解一下。協程在Unity中非常有用，可以把順序邏輯改為分時間執行。編寫時參考示例工程，或者看一下更詳細的Unity入門文章吧 ￣?￣。

2、顯示搜索過的路線。

void Refresh()n {n // 刪除所有格子n GameObject[] all_go = GameObject.FindGameObjectsWithTag("Path");n foreach (var go in all_go)n {n Destroy(go);n }nn // 創建起點和終點n for (int i = 0; i < H; i++)n {n for (int j = 0; j < W; j++)n {n if (map[i, j] == START)n {n Debug.Log("START "+ prefab_start);n var go = Instantiate(prefab_start, new Vector3(j * 1, 0.5f, i * 1), Quaternion.identity, pathParent.transform);n go.tag = "Path";n }n if (map[i, j] == END)n {n var go = Instantiate(prefab_end, new Vector3(j * 1, 0.5f, i * 1), Quaternion.identity, pathParent.transform);n go.tag = "Path";n }n }n }n }nn void RefreshPath(short[,] temp_map)n {n Refresh();n // 顯示探索過的部分n for (int i = 0; i < H; i++)n {n string line = "";n for (int j = 0; j < W; j++)n {n line += temp_map[i, j] + " ";n if (map[i,j]==0 && temp_map[i, j] != short.MaxValue)n {n var go = Instantiate(prefab_path, new Vector3(j * 1, 0.1f, i * 1), Quaternion.identity, pathParent.transform);n go.tag = "Path";n }n }n }n }n

我的這個做法效率很低，先刪除所有格子，然後把數組裡的起點、終點、探索過的部分都重新生成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

我們的微信公眾號：皮皮關