>>>  創業先鋒 眾人拾柴火焰高  >>>

簡體     傳統

　　文 / Donald Kehoe

　　在《游戲行業的人工智能設計：AI的設計和實施》中，我們討論了如何管理智能代理可能作出的基本決策——因為人工智能 (AI) 研究涉及到使用人工智能的實體。 在本文中，我為游戲男主角(或怪物或任何類型的游戲實體)作出的決策提供了一些背景。 智能代理需要確定游戲領域的興趣點，然后明確如何達到目標。 最后，本文還將介紹如何優化這些方法并提供管理它們的方法，以說明多線程。

　　本文非常接近真正的人工智能 (AI)。 所有智能代理都需要具備感知環境的基本能力，并擁有在周圍世界(無論是真實世界還是虛擬世界)中導航和移動的一些手段。 盡管方法有很大不同，但您的實體也需要具備這樣的能力。 您也可以投機取巧，以確保一切快速順暢地運行。

　　人工智能的感知方法

　　讓代理作出武斷決定適用于某些游戲，但如果您需要更多能力呢？ 如果您的代理將作出適當的決策，那么它需要了解周圍發生的事情。 在人工智能的機器人應用中，做了大量關于計算機視覺方面的研究，為機器人提供了以真實、立體的三維 (3D) 視覺感知周圍環境的能力，就像人類一樣。這種成熟水平對于我們來說是完全多余的。

　　相較于真實世界的人工智能機器人，大多數游戲所用的虛擬世界擁有巨大優勢。 我們世界中的一切都是已知量： 游戲中有一個列表，其中包含游戲里的一切。 您可以在這一列表中搜索任何標準，然后立即獲取代理所用的信息，以制定更有意義的決策。

　　視覺

　　偽造實體視覺是為代理提供感知能力的最基本層次。 您可以通過在實體列表中搜索特定范圍內的一切來做到這一點。 您既可以獲取代理感興趣的首要事件，也可以獲取范圍之內的事件列表，以便您的代理針對周圍環境作出最佳決策。

　　這一設置適用于簡單游戲，但當您的游戲風格較復雜時，如間諜游戲或第一人稱的戰術射擊游戲 (FPS)，您的代理將需要在“看到”的內容上更具有選擇性。 如果您不希望代理眼觀四面，您可以針對超過實體視線范圍之外的任意內容的潛力篩選出一個列表。 只需用一點數學知識就可以快速完成這一工作：

　　從代理的位置減去目標位置，計算考慮中的代理和實體之間的矢量。

　　計算矢量和代理所看方向之間的角度。(如果已經不是一個矢量，您也可以計算出數值)。

　　如果角度的絕對值大于代理的預設視角，您的代理看不到實體。

　　在較復雜的游戲中，您可能需要考慮某種遮蔽物隱藏的玩家或其他實體。 對于此類游戲，您可能需要執行光線追蹤 (有時稱為光線投射)，以了解是否有東西阻擋了潛在目標。 光線追蹤是一種檢查光線是否貫穿任何東西的數學方法，從一個點開始，以固定方向移動。 游戲引擎提供了光線追蹤功能，但如果您想要了解其詳情，請參見“三個臭皮匠抵一個諸葛亮”。

　　之前的方法告訴您是否有東西遮蓋了目標中心，但可能不足以阻止您的代理。 有可能代理的中心被遮蔽，但代理的上部在遮蔽物上方伸出。 在目標上的特定關注點使用多個光線追蹤不僅可以幫助確定 能否擊中目標，還可以確定能夠擊中目標的哪個位置。

　　聲音

　　乍看起來，它可能像是與視線無異的聲音。 如果您可以看到實體，您肯定也能聽到。 的確，如果您的代理發現了實體，代理可以主動檢測實體所作的任何事情，直到從視線中完全消失。 但是，為代理添加額外的聽覺水平可幫助視覺更有效地工作。 跟蹤實體發出的作為感知水平的噪聲對于任何隱蔽類游戲都至關重要。

　　和視覺一樣，您需要獲取一個附近實體的列表以便核對。 您可以再次通過簡單的距離檢查完成這項工作，但篩選這一列表的方式不同。

　　實體執行的每個操作需要有一些與其相關的聲級。 您可以預設聲級(以優化游戲平衡)，或者將操作所播放音效的實際能耗作為聲級的基礎。 如果產生的聲音在閾值范圍之內，您的代理將感知到該實體。

　　如果您想要考慮障礙，則可以再一次篩選這一列表：對環境執行光線追蹤，了解是否有東西阻擋聲音。 由于很少有材料是完全隔音的，因此您需要以更具創造性的方式從列表中刪除實體。

　　其他感官

　　為代理提供視覺和聽覺所需的基本功能可以很輕松地應用到模擬其他感官上。 這里有一個其他潛在感覺的列表，如果設計需要，您可以添加到游戲中：

　　味覺。使命召喚 4*等最近推出的游戲中添加了讓智能代理按照嗅覺跟蹤玩家的概念。 為游戲添加氣味相對簡單： 為游戲中的每個實體提供一個不同的氣味編號和強度。 氣味強度決定著兩個因素：氣味的半徑和留下的氣味線索的大小。 活躍的玩家實體通常會出于一些原因記錄其最后的幾個位置(本文稍后將在線索中介紹更多信息)。 其中一個原因是幫助有氣味的實體。 隨著玩家實體更新線索，氣味的強度隨著線索的”淡化“而逐步減小。 當更新有氣味的代理時，它需要像檢查聲音那樣檢查氣味：檢查半徑和墻面。 有了氣味，成功的因素便立足于氣味的強度和代理的嗅覺，這些將對照實體和實體的線索進行檢查。

　　雷達。有些游戲為玩家提供個人雷達，這使得感知變得更簡單。 只需一個簡單的半徑檢查即可。 隨后人工智能便可以驗證結果，了解其影響。 對于團隊游戲，雷達本身可以變得更加有趣。 為了匯總基于團隊的人工智能，每個團隊需要制定一個包含雷達發現的實體的雷達列表。 然后團隊的每個成員便可以只針對已知實體的列表執行半徑檢查，以確定團隊是否應該做出響應。 團隊可以使用雷達設備(如深入敵后： 雷神戰爭*游戲中)，按照添加“看到”的任何內容的每個團隊編號添加至列表中。 這一行為可幫助實體作為一個部隊工作，因為每個實體都會將其看到的內容告知其他實體。

　　觸摸。這種感覺比較輕而易舉，因為游戲引擎的碰撞系統會自動涵蓋它。 您只需確保智能代理能夠響應損壞和碰撞事件即可。

　　味覺。我不確定這種感覺如何運作。 它可能是氣味的一種屬性，但需要代理主動“品嘗”其發現的東西。

　　能夠感知周圍世界當然很好，但代理應該感知到什么呢？ 您需要指定并能夠確定通過代理的設置進行觀察的事物。 當您認出看到的事物，您的代理可以根據管理實體的規則對其作出響應。

　　臨時實體

　　臨時實體有時也稱為粒子、貼標或特效，是游戲世界中的視覺效果。 它們與實體類似，因為一個總體類結構定義所有潛在臨時實體，但它們又不同于實體，因為它們不思考和響應游戲世界中的實體，也不與實體互動或相互響應或互動。 他們唯一的目的就是為了美觀，在一段時間內為游戲世界提供額外細節，然后就會死去。 臨時實體用于子彈軌跡、煙霧、火花、血噴甚至腳印等事物。

　　臨時實體的性質意味著處理很少且無碰撞檢測(超出非常簡單的世界碰撞)。 問題在于，有些臨時實體為玩家提供了有關已發生事件的視覺線索(彈孔和燒傷痕跡表示最近發生過戰斗，雪地上的腳印可幫助找到潛在目標)，那么為何您的智能代理也不能使用它呢？

　　此問題有兩種解決方法： 您既可以通過增強臨時實體系統來支持光線追蹤(會破壞一個臨時實體系統的整點)，也可以在臨時實體的一般臨近區域投下一個空實體。 這一空白實體沒有思考能力，也沒有與其相關的圖像，但您的代理能夠檢測到它，并且臨時實體擁有為代理提供“英特爾”的相關信息。 因此，當一灘散血效果掉落在地上時，您可以在那里投下一個無形實體，讓您的代理知道有不尋常的事情發生了。 對于腳印的問題，您已經有掩護它的線索了。

　　掩護

　　在很多射擊游戲中，如果您的代理可以聰明地躲在掩護后面，而不是只是站在空地處等著被擊中，那真是太好了。 這個問題比我之前介紹的其他問題更專業一些。 您的代理如何確定是否有可以躲藏的可用掩護？

Penny Arcade* 諷刺了敵人人工智能和掩護物的問題。

　　實際上，這一窘境是兩個問題： 如何從實際幾何結構方面確定掩護物，以及如何從實際實體方面確定掩護物(如上述的漫畫所示)。 如要確定一個實體是否能夠阻擋攻擊，您可以簡單地驗證一下，比較一下選中的掩護物的邊框尺寸。 然后，驗證一下您的實體是否能夠躲在它后面。 驗證方法是，從射擊者和掩護物的不同位置創建一束光。 利用這束光來確定(從射擊者)穿過掩護物的點是否不會造成影響，然后將該區域標記為代理的下一個目標。

在本示例中，代理確定了綠星是能夠避開傷害的安全點。

　　AI 導航

　　目前為止，我已經聊了許多人工智能如何做決定及其如何知道將會發生什么(以便做出更好的決定)。 現在，我們來了解一下人工智能如何執行這些決定。 接下來是要確定如何從 A 點到 B 點。您可以使用多種方法，具體取決于游戲的性質和性能需求的級別。

　　碰撞和轉彎

　　碰撞和轉彎是產生實體運動最基本的方式之一。 下面介紹一下它的工作原理：

　　在目標方向移動。

　　如果撞到一面墻，轉向讓你距離目標最近的方向。 如果沒有明顯更好的選擇，請隨機選擇一個。

　　這種方法對于簡單的游戲非常有效。 數不勝數的游戲使用這種方法來控制怪獸如何追趕玩家。 碰撞和轉彎導致實體在追趕玩家時卡在凹陷的墻或角落中，因此，對于有僵尸或沒有這種地貌的游戲，這種方法非常理想。

　　但是，如果游戲要求代理更機敏，您可以對簡單的碰撞和轉彎進行更詳細地介紹，為您的代理賦予一些記憶。 如果代理能夠記住他們到過哪里，則可對如何轉彎做出更有意義的決定。 轉完所有彎后，代理將可原路返回，做不同的決定。 因此，您的代理能夠系統搜索一個目標的路線。 下面介紹一下它的工作原理：

　　向目標移動。

　　遇到叉路時做選擇。

　　發現死路時，原路返回到上一選擇，再做其他選擇。

　　探索全部可行路線后，放棄。

　　這種方法在處理方面不會耗費大量資源，這表示，您支持大量代理也不會降低游戲速度。 這種方法還非常適合處理多線程。 這種方法的缺點是會浪費大量空間，因為每位代理都可能會追蹤包括全部可行路線在內的整個地圖。

　　幸運的是，讓代理在共享內存中記錄路線，將可避免這一浪費。 但是，可能會產生線程沖突的問題;因此需要將實體路線保存在一個所有代理都能夠在移動時向其發送請求，在發現新路線時向其發送更新的單獨模塊中。 然后，路線地圖模塊還需要能夠解析發現的路線，以避免出現沖突。

　　路線查找

　　通過碰撞和轉彎生成地圖是適應不斷變化的地圖的好方法。 在策略游戲中，玩家不能坐等設備來查找他們的方位。 而且，這些路線圖可能會變得非常龐大，這樣，在其中搜尋正確的路線將會成為瓶頸。 查找救援路線。

　　路線查找問題在游戲開發中基本上已經解決。 像最初的星際爭霸 (Starcraft)* (美國暴雪娛樂公司 (Blizzard Entertainment*))一樣老的游戲都可以處理大量游戲實體，在大型的復雜地圖中找到道路。

　　查找路線的核心算法是 'A*' (讀為 [ə; stɑː])，可用于查找圖表(在本案例中為地圖)上任意兩點間的最佳路線。 進行簡單的在線查找即可發現包含 F、G 和 H 等描述性術語的 clean 算法。 請允許我更清楚地解釋一下。

　　首先，必須建立兩個列表：一個包含尚未核實的節點的列表(未核實)，一個包含已核實的節點的列表(已核實)。 每個列表包含一個位置節點、與目標之間的預估距離及其母節點(確保其位于列表中的節點)的參數。 列表最初為空。

　　接下來，將起點添加到未核實列表中，無母節點。 然后，輸入算法：

　　從列表中選擇外觀最佳的節點。

　　如果該節點是目標，則操作即可完成。

　　如果該節點不是目標，則需要將其添加至已核實列表。

　　對于與該節點相鄰的每個節點：

　　如果節點無法行走，則忽略它。

　　如果節點已在列表中(無論是已核實或未核實)，則忽略它。

　　接下來，將其添加到未核實列表中，將該節點設置為母節點，并預估其到目標的距離(粗略的距離檢查即可)。

　　實體到達目標圖塊后，通過追蹤不包含母節點的母節點(起始節點)即可構建路線。 這可為實體提供最佳路線，以便其進行查找。 由于該流程僅當代理收到命令或自行決定運動時才會發生，所以它能夠從多線程處理獲得巨大益處。 代理可以發送路線線程請求，當系統發現該路線時便會向代理提供，而不會影響人工智能的性能。 大多數情況下，系統可以快速獲取結果;但是如果有大量路線請求負載，代理便只能空等，或向適合的方向行進(它可能可以使用碰撞和轉彎的方法)。 在極大型的地圖中，系統可以劃分為多個區域，區域間的所有可行路線(或停留點)均可提前進行計算。 在這種情況下，查找路線的人僅需查找最佳路線即可，因而能夠快速獲得結果。 路線地圖僅需關注地圖上的變化即可，如當玩家建造了一面墻，僅需根據需要重新運行路線檢查即可。 算法使用單獨的線程運算，因此可輕松調整，而不會影響游戲中其他部分的性能。

　　在路線查找子系統中，多線程處理還可提高系統的性能。 它非常適合實時策略 (RTS) 游戲，或包含大量實體且每個實體都在尋找不同路線的系統。 可同時在不同線程內查找到多條路線。 當然，系統需要記錄發現的路線。 同一條路線無需多次發現。

　　代碼示例

　　以下展示了一個僅在 C 語言中部署的 A* 示例。簡便起見，我在示例中并未考慮支持函數，因為它們需要針對不同的部署風格進行定制。 本示例基于一個簡單的 tile 網格，其中每個 tile 都可以進一步處理，也可不處理。 這僅允許移動到相鄰 tile，但是，如果進行微小的改動，便能夠允許作對角移動，或者六角形游戲布局。

1. /*Get Path will return -1 on failure or a number on distance to path
   

2. if a path is found, the array pointed to by path will be set with the path in Points*/
   

3. int GetPath(int sx,int sy,int gx,int gy,int team,Point *path,int pathlen)
   

4. {
   

5. int u,i,p;
   

6. memset(&Checked,0,sizeof(Checked));
   

7. memset(&Unchecked,0,sizeof(Unchecked));
   

8. Unchecked[0].s.x = sx;
   

9. Unchecked[0].s.y = sy;
   

10. Unchecked[0].d = abs(sx - gx) + abs(sy - gy);
    

11. Unchecked[0].p.x = -1;
    

12. Unchecked[0].p.y = -1;
    

13. Unchecked[0].used = 1;
    

14. Unchecked[0].steps = 0;

　　上述代碼段可處理已驗證和未驗證列表的初始化，并將起始節點放入未驗證列表。 借助此代碼集，算法的其他部分可在循環中運行。

1. do
   

2. {
   

3. u = GetBestUnchecked();
   

4. /*add */
   

5. AddtoList(Checked,Unchecked[u]);
   

6. if((Unchecked[u].s.x == gx)&&(Unchecked[u].s.y == gy))
   

7. {
   

8. break;
   

9. }

　　上述代碼段展示了未驗證列表中距離目標最近的節點。GetBestUnchecked()可用于驗證每個節點與目標之間的預估距離。 如果該 tile 是目標，則循環停止，流程完成。

　　下文展示了距離的算法：獲取 X 和 Y 方向上與目標之間的預估距離，并將其相加。 一開始，您可能會想使用勾股定理 (a^2 + b^2 = c^2 )，但是完全沒必要。 您只需要相對距離，而非確切距離。 處理器處理加減運算的速度比處理乘運算的速度快許多倍，而處理處理乘運算的速度比處理除運算的速度快許多倍。 由于該代碼段在一幀中將會處理許多次，所以優化是關鍵。

1. /*tile to the left*/
   

2. if((Unchecked[u].s.x - 1) >= 0)/*first, make sure we're on the map*/
   

3. {
   

4. if((IsInList(Unchecked,Unchecked[u].s.x - 1,Unchecked[u].s.y,NULL) == 0)&&(IsInList(Checked,Unchecked[u].s.x - 1,Unchecked[u].s.y,NULL) == 0))
   

5. /*make sure we don't repeat a search*/
   

6. {
   

7. if(TileValid(Unchecked[u].s.x - 1,Unchecked[u].s.y,team))
   

8. NewtoList(Unchecked,Unchecked[u].s.x - 1,Unchecked[u].s.y, Unchecked[u].s.x, Unchecked[u].s.y, abs((Unchecked[u].s.x - 1) - gx) + abs(Unchecked[u].s.y - gy), Unchecked[u].steps + 1);
   

9. }
   

10. }

　　在上述代碼段中，該函數在當前節點的左側處理 tile。 如果它未添加到已驗證或未驗證列表中，系統將會嘗試將其添加至列表。 TileValid() 是另一個需要定制以滿足游戲需求的函數。 如果它通過 TileValid() 驗證，將會調用 NewToList()，這將會向未驗證列表中添加一個新 tile。 以下三個代碼段執行相同的流程，但是指稱不同的方向：右、上和下。

1. /*tile to the right*/
   

2. if((Unchecked[u].s.x + 1) < WIDTH)/*first, make sure we're on the map*/
   

3. {
   

4. if((IsInList(Unchecked,Unchecked[u].s.x + 1,Unchecked[u].s.y,NULL) == 0)&&(IsInList(Checked,Unchecked[u].s.x + 1,Unchecked[u].s.y,NULL) == 0))
   

5. /*make sure we don't repeat a search*/
   

6. {
   

7. if(TileValid(Unchecked[u].s.x + 1,Unchecked[u].s.y,team))
   

8. NewtoList(Unchecked,Unchecked[u].s.x + 1,Unchecked[u].s.y, Unchecked[u].s.x, Unchecked[u].s.y, abs((Unchecked[u].s.x + 1) - gx) + abs(Unchecked[u].s.y - gy), Unchecked[u].steps + 1);
   

9. }
   

10. }
    

11. /*tile below*/
    

12. if((Unchecked[u].s.y + 1) < HEIGHT)/*first, make sure we're on the map*/
    

13. {
    

14. if((IsInList(Unchecked,Unchecked[u].s.x ,Unchecked[u].s.y + 1,NULL) == 0)&&(IsInList(Checked,Unchecked[u].s.x,Unchecked[u].s.y + 1,NULL) == 0))
    

15. /*make sure we don't repeat a search*/
    

16. {
    

17. if(TileValid(Unchecked[u].s.x,Unchecked[u].s.y + 1,team))
    

18. NewtoList(Unchecked,Unchecked[u].s.x,Unchecked[u].s.y + 1, Unchecked[u].s.x, Unchecked[u].s.y, abs(Unchecked[u].s.x - gx) + abs((Unchecked[u].s.y + 1) - gy), Unchecked[u].steps + 1);
    

19. }
    

20. }
    

21. /*tile above*/
    

22. if((Unchecked[u].s.y - 1) >= 0)/*first, make sure we're on the map*/
    

23. {
    

24. if((IsInList(Unchecked,Unchecked[u].s.x ,Unchecked[u].s.y - 1,NULL) == 0)&&(IsInList(Checked,Unchecked[u].s.x,Unchecked[u].s.y - 1,NULL) == 0))
    

25. /*make sure we don't repeat a search*/
    

26. {
    

27. if(TileValid(Unchecked[u].s.x,Unchecked[u].s.y - 1,team))
    

28. NewtoList(Unchecked,Unchecked[u].s.x,Unchecked[u].s.y - 1, Unchecked[u].s.x, Unchecked[u].s.y, abs(Unchecked[u].s.x - gx) + abs((Unchecked[u].s.y - 1) - gy), Unchecked[u].steps + 1);
    

29. }
    

30. }
    

31. memset(&Unchecked[u],0,sizeof(PNode));

　　該迭代中需要做的最后一件事情是將未驗證列表從當前代碼中刪除。 不再需要該 tile。

1. }
   

2. while(1);

　　最后一段代碼可通過從目標原路返回來構建路線。 一定能夠找到返回起始位置的路線，因為路線中的每個代碼都會記錄將其放入列表中的代碼。 然后，返回最終路線(通過參數)。 以下函數可返回新路線的長度。

1. IsInList(Checked,Unchecked[u].s.x,Unchecked[u].s.y,&u);
   

2. p = Checked[u].steps;
   

3. if(path != NULL)
   

4. {
   

5. for(i = (p - 1);i >= 0;i--)
   

6. {
   

7. path[i].x = Checked[u].s.x;
   

8. path[i].y = Checked[u].s.y;
   

9. IsInList(Checked,Checked[u].p.x,Checked[u].p.y,&u);
   

10. }
    

11. }
    

12. return p;
    

13. }

　　總結

　　智能代理需要觀察其周圍的世界。 可以使用簡單的范圍檢查和光纖追蹤使根據視覺和聽覺所做的觀察快速成形，幫助代理在游戲過程中以更貼近人類思維的方式做決定。 確定目標后，代理需要尋找路線，去往他們想去的地方。 碰撞和轉彎等快速方式適用于短期任務和簡單地圖，而更復雜的游戲需要分析地圖來查找最佳路線。 您可以對這些方法進行優化，以充分利用多線程部署，確保游戲流暢運行，即使需要處理大量實體和復雜地圖也是如此。

英特爾開發人員專區 授權

GameRes游資網 2015-08-23 08:54:39