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

最新 08-31

GIF/1K

關注我們可以獲取最新遊戲開發資訊解悶。

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

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

GIF/1K

1、演算法可視化

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

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

GIF/1K

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

GIF/1K

所以說，圖像並不僅僅是一種輔助工具，它可以幫助我們換一個角度理解世界。很多時候，我們實現了一個很牛的演算法，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方法。先說數據結構：

關鍵的數據結構共有三個。

首先是地圖map二維數組本身，這個畫地圖時已經用到了。

其次是保存每格里的步數的二維數組 int bfs[Height, Width]，前面的標記了數字的圖就是。

最後是關鍵性的，一個任務隊列，用List表示即可。List

queue = new List

();

Pos代表每一個格子，由於格子坐標是整數（整數可以直接做數組索引），不能用Vector2，定義如下：

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的偽代碼：

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

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

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

2、顯示搜索過的路線。

我的這個做法效率很低，先刪除所有格子，然後把數組裡的起點、終點、探索過的部分都重新生成Cube顯示出來。但是對「演算法可視化」的目標來說，這種方法極其方便，通用性很強，可以讓畫圖的過程和演算法無關。學習過程中不要考慮效率，記住我們的目標是為了更好的理解演算法。

GIF/1K

5、修改並理解更多演算法

寫了這麼多功能，只用來學習BFS不覺得很虧嗎？咱們再加點料。

1、在BFS中，只要改變從queue中取元素的順序，就可以實現各種666的演算法：

如果從queue的後面開始取，就是類似深度優先搜索的演算法（另類的DFS）。

如果從queue中選擇離終點最近的元素，就實現了有指導的DFS，這種演算法在某些特定地圖上比AStar還快。

口說無憑，看動圖：

1、輕微修改BFS做成的DFS，實際效果和DFS完全一致。

GIF/1K

2、有距離指導的DFS，在路線直接的情況下非常快：

GIF/1K

3、AStar，可以看到AStar並不能說絕對的「快」，但是兼顧了廣度和深度，絕大多數情況下表現更好：

GIF/1K

4、福利。連連看演算法，起點和終點之間最多只能有兩次折線。這個演算法和尋路完全不一樣，是用十字射線相交的方法實現的：

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

6、總結

本章主要就是演示演算法可視化，讓大家體會這種方法的樂趣。演算法實現的過程雖然辛苦，但是滿足感也是巨大的。

尋路演算法做出來之後，怎樣將它融合到AI的移動過程中，又是一個新的問題了，好在這個問題並不難，會在未來的文章中一筆帶過。遊戲開發中，很少有一招鮮、吃遍天的情況，任何演算法都有它的適應範圍，為了讓遊戲有更好的體驗，AI演算法也必須要相應修正。

現在流行的即時戰略遊戲比如《星際爭霸2》中，AI已經有了長足的進步，不僅能在進攻時自動排成隊形，儘可能讓所有人都能輸出傷害，還能在多個友軍部隊向不同方向前進時，自動錯開位置躲避對方。這都是多種演算法的綜合應用，不用覺得這些方法有多麼複雜，關鍵是深入理解基本演算法，在實際項目中做出關鍵性的調整，才是AI學習的重點。

就啰嗦這麼多吧，下次咱們再研究新的問題，下次再見 (′?ω?`) 。

GIF/1K