給貓看的游戲AI實(shí)戰(zhàn)（四）眼見為實(shí)——讓AI的思考過程可視化
上一節(jié)我們學(xué)習(xí)了AI狀態(tài)機(jī)的基本使用方法，讓AI具有了進(jìn)攻、追擊、回退等基本功能。本來今天是想繼續(xù)深入狀態(tài)機(jī)的，但是其實(shí)未來狀態(tài)機(jī)AI相對(duì)來說不再是技術(shù)發(fā)展的主流，在復(fù)雜AI的項(xiàng)目中，它的地位被行為樹取代了許多。
不久之后我們會(huì)用行為樹的方法再看看復(fù)雜AI行為的設(shè)計(jì)，由于行為樹的設(shè)計(jì)比較復(fù)雜，對(duì)初學(xué)者很不友好 ╮(╯▽╰)╭。所以今天我們先換一個(gè)方向突破——AI尋路，但是本文的重點(diǎn)并不在尋路算法本身。先展示一下今天要做的最終效果：
1、算法可視化
圖像可以幫助理解抽象的概念，這是顯然的。但是如果只把圖像理解為幫助理解的工具，就太膚淺了。舉個(gè)例子：
一個(gè)物體的速度從10開始，一直勻速降低。先降低到0，繼續(xù)降低到-10為止。這個(gè)圖像表示了一個(gè)怎樣的情景呢？放一個(gè)動(dòng)圖：
如圖，就是簡(jiǎn)單的拋一個(gè)硬幣而已，只要定義速度的方向向上為正，向下為負(fù)，那么硬幣的速度-時(shí)間曲線，就是上面的直線了。想一想，拋個(gè)硬幣試試，是不是很反直覺呢？（ 不要問我和炮姐有什么關(guān)系，只是扔個(gè)硬幣而已 (￣y▽￣)~* 。）
所以說，圖像并不僅僅是一種輔助工具，它可以幫助我們換一個(gè)角度理解世界。很多時(shí)候，我們實(shí)現(xiàn)了一個(gè)很牛的算法，A*尋路、碰撞檢測(cè)、三角剖分等等，但是也僅僅是按照前人的方法實(shí)現(xiàn)了而已，而對(duì)算法的理解，還停留在很低的層面上。如果這時(shí)候從不同的角度讓算法直觀地表現(xiàn)出來，那么算法存在的缺陷、優(yōu)化的方法、適用的范圍等等一系列深度問題，都會(huì)顯而易見了。
如果你還是不知道這個(gè)方法好玩在哪，建議翻到本文最后第5段，里面有很多好玩的例子。本文最后面有工程下載地址，也可以先運(yùn)行工程試試。
那么我們先來畫個(gè)迷宮。
2、圖形化顯示數(shù)組內(nèi)容
1、定義地圖大小，并創(chuàng)建一個(gè)二維數(shù)組map代表地圖里的元素（空地、墻、起點(diǎn)、終點(diǎn)等等）
const int Height = 20;
const int Width = 30;
int[,] map = new int[Height, Width];
// 在map里填寫以下數(shù)字，代表開始點(diǎn)、結(jié)束點(diǎn)、墻
const int START = 8;
const int END = 9;
const int WALL = 1;
2、在Unity中放置一個(gè)平面，代表地面，大小和位置可以在我們畫出地圖后再調(diào)節(jié)也可以。
3、以下代碼可以將數(shù)組里的墻顯示出來，map的前一個(gè)元素是Y坐標(biāo)，第二個(gè)元素是X坐標(biāo)：
void InitMap0()
{
// 新建一個(gè)GameObject walls作為所有墻的父節(jié)點(diǎn)
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、現(xiàn)在我們的數(shù)組內(nèi)容都是默認(rèn)的0，我們可以用很多方法初始化數(shù)組的值，這里提供一個(gè)直接編寫文本文件來定義地圖的方法：
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<H)
{
for (int x=0; x<W && x<strReadline.Length; ++x)
{
int t;
switch(strReadline[x])
{
case '1':
t = 1;
break;
case '8':
t = 8;
break;
case '9':
t = 9;
break;
default:
t = 0;
break;
}
// Debug.Log("x, y"+ x +" " + y);
map[y, x] = t;
}
y += 1;
strReadline = read.ReadLine();
}
read.Dispose();//文件流釋放
fs.Close();
}
在Unity的Assets目錄中新建一個(gè)map.txt文件，可以用記事本直接畫地圖，空格代表空白，1代表墻，第一行不包含在內(nèi)。注意行數(shù)、列數(shù)和代碼中的定義一致。類似下面這樣：
----+----+----+----+----+----+
1 11111111 $
1 $
1 $
1 $
$
1111111111111 11111111 $
1 $
1 $
1 $
1 $
1 $
1 $
1 $
1 $
11111111111111 $
$
$
$
$
$
$用來標(biāo)記每行末尾，沒有特別的意思。這樣初始化地圖就變得很簡(jiǎn)單了。注意編輯器一定要用記事本之類的等寬字體編輯哦，否則字符寬度不同就麻煩了 （￣工￣lll）。
5、測(cè)試看看。如果地面對(duì)的不齊，只要調(diào)整地面位置就可以了。
3、廣度優(yōu)先搜索（BFS）
廣度優(yōu)先搜索是尋路算法的基礎(chǔ)。所謂廣度優(yōu)先，就是在搜索時(shí)，先盡可能把一定距離內(nèi)的點(diǎn)全部探索完畢，然后再探索稍微遠(yuǎn)一點(diǎn)的所有點(diǎn)，以此類推，直到達(dá)到足夠遠(yuǎn)的地方發(fā)現(xiàn)終點(diǎn)。
如圖，數(shù)字代表探索的順序。探索是從入口開始，先探索所有附近1格的節(jié)點(diǎn)，然后是2格、3格，依次類推，和本文開頭的動(dòng)圖是一致的。
1、本文不再一步一步講解BFS細(xì)節(jié)的實(shí)現(xiàn)，只是提示一些細(xì)節(jié)，你就可以實(shí)現(xiàn)自己的BFS方法。先說數(shù)據(jù)結(jié)構(gòu)：
關(guān)鍵的數(shù)據(jù)結(jié)構(gòu)共有三個(gè)。
首先是地圖map二維數(shù)組本身，這個(gè)畫地圖時(shí)已經(jīng)用到了。
其次是保存每格里的步數(shù)的二維數(shù)組 int bfs[Height, Width]，前面的標(biāo)記了數(shù)字的圖就是。
最后是關(guān)鍵性的，一個(gè)任務(wù)隊(duì)列，用List表示即可。List<Pos> queue = new List<Pos>();
Pos代表每一個(gè)格子，由于格子坐標(biāo)是整數(shù)（整數(shù)可以直接做數(shù)組索引），不能用Vector2，定義如下：
// Pos代替Vector2，代表位置。整數(shù)
public class Pos
{
public int x = 0;
public int y = 0;
// 多個(gè)初始化函數(shù)是為了方便使用
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函數(shù)，判斷相等時(shí)比較方便。p.Equals(q)，就可以判斷p和q是否相等了。
public bool Equals(Pos p)
{
return x == p.x && y == p.y;
}
}
2、數(shù)據(jù)結(jié)構(gòu)之后，描述一下算法：
初始化bfs數(shù)組全部為short.MaxValue，初始值是0會(huì)帶來很多麻煩。
初始點(diǎn)步數(shù)為0，設(shè)置bfs[start.y, start.x] = 0，然后將start這個(gè)點(diǎn)加入到queue最后面去。queue.Add(start);
下面開始循環(huán)。從queue中取出第一個(gè)元素p，并從queue中刪除它。
如果p就是終點(diǎn)，那么我們的任務(wù)就完成了。設(shè)置終點(diǎn)的步數(shù)后退出循環(huán)。
依次判斷p的上、下、左、右四個(gè)相鄰元素。相鄰的元素q不能超出地圖范圍，不能是墻；如果q已經(jīng)被探索過了，那么也不再考慮它（這是BFS特有的處理方式）。
對(duì)上一步發(fā)現(xiàn)的新的合理的格子q，設(shè)置bfs[q.y, q.x] = bfs[p.y, p.x] + 1; 即步數(shù)+1。并將q插入隊(duì)列queue。
回到第3步，如果隊(duì)列為空就代表探索完畢，沒有發(fā)現(xiàn)終點(diǎn)（比如終點(diǎn)被擋死了）。
重點(diǎn)是第5步中，如果某個(gè)點(diǎn)已經(jīng)被探索過、標(biāo)記過步數(shù)，那么后來再探索到它的時(shí)候，步數(shù)一定大于等于原來的值，也就不需要再考慮它了，只有BFS才有這個(gè)性質(zhì)。未來做其他尋路算法時(shí)，要注意如果新的步數(shù)小于原來標(biāo)記的步數(shù)，就要執(zhí)行第6步（設(shè)置新的步數(shù)并把該點(diǎn)加入queue）。
3、最后描述一下得到了bfs表之后，怎樣獲得最短路徑。
初始化一個(gè)path列表代表路徑，List<Pos> path = new List<Pos>();
從終點(diǎn)開始，設(shè)置p為終點(diǎn)，步數(shù)為n。
從p的上下左右四個(gè)點(diǎn)中找到任意一個(gè)步數(shù)為n-1的點(diǎn)，加入到path中，將p賦值為這個(gè)點(diǎn)。重復(fù)本步驟即可，直至p是起點(diǎn)。
完畢，path即代表最短路徑。
4、探索過程的可視化
一般來說，函數(shù)的執(zhí)行要么是一次執(zhí)行完畢，要么是每幀執(zhí)行一次。在算法做可視化的時(shí)候，這是個(gè)很頭疼的問題。
1、Unity提供的協(xié)程機(jī)制可以很方便地讓函數(shù)變?yōu)槊繋瑘?zhí)行1到n步，可以隨意控制。為了說明方便，這里寫一個(gè)BFS的偽代碼：
void BFS()
{
bfs = new int[map.GetLength(0),map.GetLength(1)];
將bfs每個(gè)元素賦值為int.MaxValue; bfs_search[i, j] = short.MaxValue;
List<Pos> queue = new List<Pos>();
bfs[startPos.y, startPos.x] = 0;
queue.Add(startPos);
while (queue.Count > 0)
{
Pos cur = queue[0]; // cur是當(dāng)前方格
queue.RemoveAt(0);
處理上方方格;
處理下方方格;
處理左邊方格;
處理右邊方格;
}
}
如果要每探索出一個(gè)方格，都停頓1幀或者零點(diǎn)幾秒，可以改成如下形式：
IEnumerator BFS()
{
bfs = new int[map.GetLength(0),map.GetLength(1)];
將bfs每個(gè)元素賦值為int.MaxValue; bfs_search[i, j] = short.MaxValue;
List<Pos> queue = new List<Pos>();
bfs[startPos.y, startPos.x] = 0;
queue.Add(startPos);
while (queue.Count > 0)
{
Pos cur = queue[0]; // cur是當(dāng)前方格
queue.RemoveAt(0);
處理上方方格;
處理下方方格;
處理左邊方格;
處理右邊方格;
RefreshPath(bfs); // 刷新場(chǎng)景
yield return new WaitForSeconds(0.05f); // 暫停0.05秒
}
yield return null;
}
只加了三句話，一個(gè)RefreshPath調(diào)用，兩個(gè)yield分別代表暫停和結(jié)束；還修改了函數(shù)返回值為IEnumerator。這個(gè)被改寫過的函數(shù)調(diào)用時(shí)要這么寫：
StartCoroutine(BFS());
關(guān)于協(xié)程就這樣簡(jiǎn)單講解一下。協(xié)程在Unity中非常有用，可以把順序邏輯改為分時(shí)間執(zhí)行。編寫時(shí)參考示例工程，或者看一下更詳細(xì)的Unity入門文章吧 ￣?￣。
2、顯示搜索過的路線。
void Refresh()
{
// 刪除所有格子
GameObject[] all_go = GameObject.FindGameObjectsWithTag("Path");
foreach (var go in all_go)
{
Destroy(go);
}
// 創(chuàng)建起點(diǎn)和終點(diǎn)
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";
}
}
}
}
我的這個(gè)做法效率很低，先刪除所有格子，然后把數(shù)組里的起點(diǎn)、終點(diǎn)、探索過的部分都重新生成Cube顯示出來。但是對(duì)“算法可視化”的目標(biāo)來說，這種方法極其方便，通用性很強(qiáng)，可以讓畫圖的過程和算法無關(guān)。學(xué)習(xí)過程中不要考慮效率，記住我們的目標(biāo)是為了更好的理解算法。
5、修改并理解更多算法
寫了這么多功能，只用來學(xué)習(xí)BFS不覺得很虧嗎？咱們?cè)偌狱c(diǎn)料。
1、在BFS中，只要改變從queue中取元素的順序，就可以實(shí)現(xiàn)各種666的算法：
如果從queue的后面開始取，就是類似深度優(yōu)先搜索的算法（另類的DFS）。
如果從queue中選擇離終點(diǎn)最近的元素，就實(shí)現(xiàn)了有指導(dǎo)的DFS，這種算法在某些特定地圖上比AStar還快。
口說無憑，看動(dòng)圖：
1、輕微修改BFS做成的DFS，實(shí)際效果和DFS完全一致。
2、有距離指導(dǎo)的DFS，在路線直接的情況下非?？欤?/p>
3、AStar，可以看到AStar并不能說絕對(duì)的“快”，但是兼顧了廣度和深度，絕大多數(shù)情況下表現(xiàn)更好：
4、福利。連連看算法，起點(diǎn)和終點(diǎn)之間最多只能有兩次折線。這個(gè)算法和尋路完全不一樣，是用十字射線相交的方法實(shí)現(xiàn)的：
以上算法在示例工程中都有。
6、總結(jié)
本章主要就是演示算法可視化，讓大家體會(huì)這種方法的樂趣。算法實(shí)現(xiàn)的過程雖然辛苦，但是滿足感也是巨大的。
尋路算法做出來之后，怎樣將它融合到AI的移動(dòng)過程中，又是一個(gè)新的問題了，好在這個(gè)問題并不難，會(huì)在未來的文章中一筆帶過。游戲開發(fā)中，很少有一招鮮、吃遍天的情況，任何算法都有它的適應(yīng)范圍，為了讓游戲有更好的體驗(yàn)，AI算法也必須要相應(yīng)修正。
現(xiàn)在流行的即時(shí)戰(zhàn)略游戲比如《星際爭(zhēng)霸2》中，AI已經(jīng)有了長(zhǎng)足的進(jìn)步，不僅能在進(jìn)攻時(shí)自動(dòng)排成隊(duì)形，盡可能讓所有人都能輸出傷害，還能在多個(gè)友軍部隊(duì)向不同方向前進(jìn)時(shí)，自動(dòng)錯(cuò)開位置躲避對(duì)方。這都是多種算法的綜合應(yīng)用，不用覺得這些方法有多么復(fù)雜，關(guān)鍵是深入理解基本算法，在實(shí)際項(xiàng)目中做出關(guān)鍵性的調(diào)整，才是AI學(xué)習(xí)的重點(diǎn)。
就啰嗦這么多吧，下次咱們?cè)傺芯啃碌膯栴}，再見 (′?ω?`) 。
GameMap工程地址：
https://github.com/mayao11/PracticalGameAI/tree/master/GameMap
————————————————————————————————————
對(duì)游戲開發(fā)感興趣的同學(xué)，歡迎圍觀我們：【皮皮關(guān)游戲開發(fā)教育】 ，會(huì)定期更新各種教程干貨，更有別具一格的線下小班教育~
我們的官網(wǎng)地址：http://levelpp.com/
我們的游戲開發(fā)技術(shù)交流群：610475807
我們的微信公眾號(hào)：皮皮關(guān)
