游戏行业的人工智能设计（二）：路径搜寻和感知
文 / Donald Kehoe
在上一篇文章(第一部分)中，我們討論了如何管理智能代理可能作出的基本決策——因為人工智能 (AI) 研究涉及到使用人工智能的實體。 在本文中，我為游戲男主角(或怪物或任何類型的游戲?qū)嶓w)作出的決策提供了一些背景。 智能代理需要確定游戲領(lǐng)域的興趣點，然后明確如何達(dá)到目標(biāo)。 最后，本文還將介紹如何優(yōu)化這些方法并提供管理它們的方法，以說明多線程。
本文非常接近真正的人工智能 (AI)。 所有智能代理都需要具備感知環(huán)境的基本能力，并擁有在周圍世界(無論是真實世界還是虛擬世界)中導(dǎo)航和移動的一些手段。 盡管方法有很大不同，但您的實體也需要具備這樣的能力。 您也可以投機(jī)取巧，以確保一切快速順暢地運行。
人工智能的感知方法
讓代理作出武斷決定適用于某些游戲，但如果您需要更多能力呢？ 如果您的代理將作出適當(dāng)?shù)臎Q策，那么它需要了解周圍發(fā)生的事情。 在人工智能的機(jī)器人應(yīng)用中，做了大量關(guān)于計算機(jī)視覺方面的研究，為機(jī)器人提供了以真實、立體的三維 (3D) 視覺感知周圍環(huán)境的能力，就像人類一樣。這種成熟水平對于我們來說是完全多余的。
相較于真實世界的人工智能機(jī)器人，大多數(shù)游戲所用的虛擬世界擁有巨大優(yōu)勢。 我們世界中的一切都是已知量： 游戲中有一個列表，其中包含游戲里的一切。 您可以在這一列表中搜索任何標(biāo)準(zhǔn)，然后立即獲取代理所用的信息，以制定更有意義的決策。
視覺
偽造實體視覺是為代理提供感知能力的最基本層次。 您可以通過在實體列表中搜索特定范圍內(nèi)的一切來做到這一點。 您既可以獲取代理感興趣的首要事件，也可以獲取范圍之內(nèi)的事件列表，以便您的代理針對周圍環(huán)境作出最佳決策。
這一設(shè)置適用于簡單游戲，但當(dāng)您的游戲風(fēng)格較復(fù)雜時，如間諜游戲或第一人稱的戰(zhàn)術(shù)射擊游戲 (FPS)，您的代理將需要在“看到”的內(nèi)容上更具有選擇性。 如果您不希望代理眼觀四面，您可以針對超過實體視線范圍之外的任意內(nèi)容的潛力篩選出一個列表。 只需用一點數(shù)學(xué)知識就可以快速完成這一工作：
從代理的位置減去目標(biāo)位置，計算考慮中的代理和實體之間的矢量。
計算矢量和代理所看方向之間的角度。(如果已經(jīng)不是一個矢量，您也可以計算出數(shù)值)。
如果角度的絕對值大于代理的預(yù)設(shè)視角，您的代理看不到實體。
在較復(fù)雜的游戲中，您可能需要考慮某種遮蔽物隱藏的玩家或其他實體。 對于此類游戲，您可能需要執(zhí)行光線追蹤 (有時稱為光線投射)，以了解是否有東西阻擋了潛在目標(biāo)。 光線追蹤是一種檢查光線是否貫穿任何東西的數(shù)學(xué)方法，從一個點開始，以固定方向移動。 游戲引擎提供了光線追蹤功能，但如果您想要了解其詳情，請參見“三個臭皮匠抵一個諸葛亮”。
之前的方法告訴您是否有東西遮蓋了目標(biāo)中心，但可能不足以阻止您的代理。 有可能代理的中心被遮蔽，但代理的上部在遮蔽物上方伸出。 在目標(biāo)上的特定關(guān)注點使用多個光線追蹤不僅可以幫助確定 能否擊中目標(biāo)，還可以確定能夠擊中目標(biāo)的哪個位置。
聲音
乍看起來，它可能像是與視線無異的聲音。 如果您可以看到實體，您肯定也能聽到。 的確，如果您的代理發(fā)現(xiàn)了實體，代理可以主動檢測實體所作的任何事情，直到從視線中完全消失。 但是，為代理添加額外的聽覺水平可幫助視覺更有效地工作。 跟蹤實體發(fā)出的作為感知水平的噪聲對于任何隱蔽類游戲都至關(guān)重要。
和視覺一樣，您需要獲取一個附近實體的列表以便核對。 您可以再次通過簡單的距離檢查完成這項工作，但篩選這一列表的方式不同。
實體執(zhí)行的每個操作需要有一些與其相關(guān)的聲級。 您可以預(yù)設(shè)聲級(以優(yōu)化游戲平衡)，或者將操作所播放音效的實際能耗作為聲級的基礎(chǔ)。 如果產(chǎn)生的聲音在閾值范圍之內(nèi)，您的代理將感知到該實體。
如果您想要考慮障礙，則可以再一次篩選這一列表：對環(huán)境執(zhí)行光線追蹤，了解是否有東西阻擋聲音。 由于很少有材料是完全隔音的，因此您需要以更具創(chuàng)造性的方式從列表中刪除實體。
其他感官
為代理提供視覺和聽覺所需的基本功能可以很輕松地應(yīng)用到模擬其他感官上。 這里有一個其他潛在感覺的列表，如果設(shè)計需要，您可以添加到游戲中：
味覺。使命召喚 4*等最近推出的游戲中添加了讓智能代理按照嗅覺跟蹤玩家的概念。 為游戲添加氣味相對簡單： 為游戲中的每個實體提供一個不同的氣味編號和強(qiáng)度。 氣味強(qiáng)度決定著兩個因素：氣味的半徑和留下的氣味線索的大小。 活躍的玩家實體通常會出于一些原因記錄其最后的幾個位置(本文稍后將在線索中介紹更多信息)。 其中一個原因是幫助有氣味的實體。 隨著玩家實體更新線索，氣味的強(qiáng)度隨著線索的”淡化“而逐步減小。 當(dāng)更新有氣味的代理時，它需要像檢查聲音那樣檢查氣味：檢查半徑和墻面。 有了氣味，成功的因素便立足于氣味的強(qiáng)度和代理的嗅覺，這些將對照實體和實體的線索進(jìn)行檢查。
雷達(dá)。有些游戲為玩家提供個人雷達(dá)，這使得感知變得更簡單。 只需一個簡單的半徑檢查即可。 隨后人工智能便可以驗證結(jié)果，了解其影響。 對于團(tuán)隊游戲，雷達(dá)本身可以變得更加有趣。 為了匯總基于團(tuán)隊的人工智能，每個團(tuán)隊需要制定一個包含雷達(dá)發(fā)現(xiàn)的實體的雷達(dá)列表。 然后團(tuán)隊的每個成員便可以只針對已知實體的列表執(zhí)行半徑檢查，以確定團(tuán)隊是否應(yīng)該做出響應(yīng)。 團(tuán)隊可以使用雷達(dá)設(shè)備(如深入敵后： 雷神戰(zhàn)爭*游戲中)，按照添加“看到”的任何內(nèi)容的每個團(tuán)隊編號添加至列表中。 這一行為可幫助實體作為一個部隊工作，因為每個實體都會將其看到的內(nèi)容告知其他實體。
觸摸。這種感覺比較輕而易舉，因為游戲引擎的碰撞系統(tǒng)會自動涵蓋它。 您只需確保智能代理能夠響應(yīng)損壞和碰撞事件即可。
味覺。我不確定這種感覺如何運作。 它可能是氣味的一種屬性，但需要代理主動“品嘗”其發(fā)現(xiàn)的東西。
能夠感知周圍世界當(dāng)然很好，但代理應(yīng)該感知到什么呢？ 您需要指定并能夠確定通過代理的設(shè)置進(jìn)行觀察的事物。 當(dāng)您認(rèn)出看到的事物，您的代理可以根據(jù)管理實體的規(guī)則對其作出響應(yīng)。
臨時實體
臨時實體有時也稱為粒子、貼標(biāo)或特效，是游戲世界中的視覺效果。 它們與實體類似，因為一個總體類結(jié)構(gòu)定義所有潛在臨時實體，但它們又不同于實體，因為它們不思考和響應(yīng)游戲世界中的實體，也不與實體互動或相互響應(yīng)或互動。 他們唯一的目的就是為了美觀，在一段時間內(nèi)為游戲世界提供額外細(xì)節(jié)，然后就會死去。 臨時實體用于子彈軌跡、煙霧、火花、血噴甚至腳印等事物。
臨時實體的性質(zhì)意味著處理很少且無碰撞檢測(超出非常簡單的世界碰撞)。 問題在于，有些臨時實體為玩家提供了有關(guān)已發(fā)生事件的視覺線索(彈孔和燒傷痕跡表示最近發(fā)生過戰(zhàn)斗，雪地上的腳印可幫助找到潛在目標(biāo))，那么為何您的智能代理也不能使用它呢？
此問題有兩種解決方法： 您既可以通過增強(qiáng)臨時實體系統(tǒng)來支持光線追蹤(會破壞一個臨時實體系統(tǒng)的整點)，也可以在臨時實體的一般臨近區(qū)域投下一個空實體。 這一空白實體沒有思考能力，也沒有與其相關(guān)的圖像，但您的代理能夠檢測到它，并且臨時實體擁有為代理提供“英特爾”的相關(guān)信息。 因此，當(dāng)一灘散血效果掉落在地上時，您可以在那里投下一個無形實體，讓您的代理知道有不尋常的事情發(fā)生了。 對于腳印的問題，您已經(jīng)有掩護(hù)它的線索了。
掩護(hù)
在很多射擊游戲中，如果您的代理可以聰明地躲在掩護(hù)后面，而不是只是站在空地處等著被擊中，那真是太好了。 這個問題比我之前介紹的其他問題更專業(yè)一些。 您的代理如何確定是否有可以躲藏的可用掩護(hù)？
?
實際上，這一窘境是兩個問題： 如何從實際幾何結(jié)構(gòu)方面確定掩護(hù)物，以及如何從實際實體方面確定掩護(hù)物(如上述的漫畫所示)。 如要確定一個實體是否能夠阻擋攻擊，您可以簡單地驗證一下，比較一下選中的掩護(hù)物的邊框尺寸。 然后，驗證一下您的實體是否能夠躲在它后面。 驗證方法是，從射擊者和掩護(hù)物的不同位置創(chuàng)建一束光。 利用這束光來確定(從射擊者)穿過掩護(hù)物的點是否不會造成影響，然后將該區(qū)域標(biāo)記為代理的下一個目標(biāo)。
?
AI 導(dǎo)航
目前為止，我已經(jīng)聊了許多人工智能如何做決定及其如何知道將會發(fā)生什么(以便做出更好的決定)。 現(xiàn)在，我們來了解一下人工智能如何執(zhí)行這些決定。 接下來是要確定如何從 A 點到 B 點。您可以使用多種方法，具體取決于游戲的性質(zhì)和性能需求的級別。
碰撞和轉(zhuǎn)彎
碰撞和轉(zhuǎn)彎是產(chǎn)生實體運動最基本的方式之一。 下面介紹一下它的工作原理：
在目標(biāo)方向移動。
如果撞到一面墻，轉(zhuǎn)向讓你距離目標(biāo)最近的方向。 如果沒有明顯更好的選擇，請隨機(jī)選擇一個。
這種方法對于簡單的游戲非常有效。 數(shù)不勝數(shù)的游戲使用這種方法來控制怪獸如何追趕玩家。 碰撞和轉(zhuǎn)彎導(dǎo)致實體在追趕玩家時卡在凹陷的墻或角落中，因此，對于有僵尸或沒有這種地貌的游戲，這種方法非常理想。
但是，如果游戲要求代理更機(jī)敏，您可以對簡單的碰撞和轉(zhuǎn)彎進(jìn)行更詳細(xì)地介紹，為您的代理賦予一些記憶。 如果代理能夠記住他們到過哪里，買二手QQ平臺則可對如何轉(zhuǎn)彎做出更有意義的決定。 轉(zhuǎn)完所有彎后，代理將可原路返回，做不同的決定。 因此，您的代理能夠系統(tǒng)搜索一個目標(biāo)的路線。 下面介紹一下它的工作原理：
向目標(biāo)移動。
遇到叉路時做選擇。
發(fā)現(xiàn)死路時，原路返回到上一選擇，再做其他選擇。
探索全部可行路線后，放棄。
這種方法在處理方面不會耗費大量資源，這表示，您支持大量代理也不會降低游戲速度。 這種方法還非常適合處理多線程。 這種方法的缺點是會浪費大量空間，因為每位代理都可能會追蹤包括全部可行路線在內(nèi)的整個地圖。
幸運的是，讓代理在共享內(nèi)存中記錄路線，將可避免這一浪費。 但是，可能會產(chǎn)生線程沖突的問題;因此需要將實體路線保存在一個所有代理都能夠在移動時向其發(fā)送請求，在發(fā)現(xiàn)新路線時向其發(fā)送更新的單獨模塊中。 然后，路線地圖模塊還需要能夠解析發(fā)現(xiàn)的路線，以避免出現(xiàn)沖突。
路線查找
通過碰撞和轉(zhuǎn)彎生成地圖是適應(yīng)不斷變化的地圖的好方法。 在策略游戲中，玩家不能坐等設(shè)備來查找他們的方位。 而且，這些路線圖可能會變得非常龐大，這樣，在其中搜尋正確的路線將會成為瓶頸。 查找救援路線。
路線查找問題在游戲開發(fā)中基本上已經(jīng)解決。 像最初的星際爭霸 (Starcraft)* (美國暴雪娛樂公司 (Blizzard Entertainment*))一樣老的游戲都可以處理大量游戲?qū)嶓w，在大型的復(fù)雜地圖中找到道路。
查找路線的核心算法是 'A*' (讀為 [?; stɑ?])，可用于查找圖表(在本案例中為地圖)上任意兩點間的最佳路線。 進(jìn)行簡單的在線查找即可發(fā)現(xiàn)包含 F、G 和 H 等描述性術(shù)語的 clean 算法。 請允許我更清楚地解釋一下。
首先，必須建立兩個列表：一個包含尚未核實的節(jié)點的列表(未核實)，一個包含已核實的節(jié)點的列表(已核實)。 每個列表包含一個位置節(jié)點、與目標(biāo)之間的預(yù)估距離及其母節(jié)點(確保其位于列表中的節(jié)點)的參數(shù)。 列表最初為空。
接下來，將起點添加到未核實列表中，無母節(jié)點。 然后，輸入算法：
從列表中選擇外觀最佳的節(jié)點。
如果該節(jié)點是目標(biāo)，則操作即可完成。
如果該節(jié)點不是目標(biāo)，則需要將其添加至已核實列表。
對于與該節(jié)點相鄰的每個節(jié)點：
如果節(jié)點無法行走，則忽略它。
如果節(jié)點已在列表中(無論是已核實或未核實)，則忽略它。
接下來，將其添加到未核實列表中，將該節(jié)點設(shè)置為母節(jié)點，并預(yù)估其到目標(biāo)的距離(粗略的距離檢查即可)。
實體到達(dá)目標(biāo)圖塊后，通過追蹤不包含母節(jié)點的母節(jié)點(起始節(jié)點)即可構(gòu)建路線。 這可為實體提供最佳路線，以便其進(jìn)行查找。 由于該流程僅當(dāng)代理收到命令或自行決定運動時才會發(fā)生，所以它能夠從多線程處理獲得巨大益處。 代理可以發(fā)送路線線程請求，當(dāng)系統(tǒng)發(fā)現(xiàn)該路線時便會向代理提供，而不會影響人工智能的性能。 大多數(shù)情況下，系統(tǒng)可以快速獲取結(jié)果;但是如果有大量路線請求負(fù)載，代理便只能空等，或向適合的方向行進(jìn)(它可能可以使用碰撞和轉(zhuǎn)彎的方法)。 在極大型的地圖中，系統(tǒng)可以劃分為多個區(qū)域，區(qū)域間的所有可行路線(或停留點)均可提前進(jìn)行計算。 在這種情況下，查找路線的人僅需查找最佳路線即可，因而能夠快速獲得結(jié)果。 路線地圖僅需關(guān)注地圖上的變化即可，如當(dāng)玩家建造了一面墻，僅需根據(jù)需要重新運行路線檢查即可。 算法使用單獨的線程運算，因此可輕松調(diào)整，而不會影響游戲中其他部分的性能。
在路線查找子系統(tǒng)中，多線程處理還可提高系統(tǒng)的性能。 它非常適合實時策略 (RTS) 游戲，或包含大量實體且每個實體都在尋找不同路線的系統(tǒng)。 可同時在不同線程內(nèi)查找到多條路線。 當(dāng)然，系統(tǒng)需要記錄發(fā)現(xiàn)的路線。 同一條路線無需多次發(fā)現(xiàn)。
代碼示例
以下展示了一個僅在 C 語言中部署的 A* 示例。簡便起見，我在示例中并未考慮支持函數(shù)，因為它們需要針對不同的部署風(fēng)格進(jìn)行定制。 本示例基于一個簡單的 tile 網(wǎng)格，其中每個 tile 都可以進(jìn)一步處理，也可不處理。 這僅允許移動到相鄰 tile，但是，如果進(jìn)行微小的改動，便能夠允許作對角移動，或者六角形游戲布局。
上述代碼段可處理已驗證和未驗證列表的初始化，并將起始節(jié)點放入未驗證列表。 借助此代碼集，算法的其他部分可在循環(huán)中運行。
?
上述代碼段展示了未驗證列表中距離目標(biāo)最近的節(jié)點。GetBestUnchecked()可用于驗證每個節(jié)點與目標(biāo)之間的預(yù)估距離。 如果該 tile 是目標(biāo)，則循環(huán)停止，流程完成。
下文展示了距離的算法：獲取 X 和 Y 方向上與目標(biāo)之間的預(yù)估距離，并將其相加。 一開始，您可能會想使用勾股定理 (a^2 + b^2 = c^2 )，但是完全沒必要。 您只需要相對距離，而非確切距離。 處理器處理加減運算的速度比處理乘運算的速度快許多倍，而處理處理乘運算的速度比處理除運算的速度快許多倍。 由于該代碼段在一幀中將會處理許多次，所以優(yōu)化是關(guān)鍵。
?
在上述代碼段中，該函數(shù)在當(dāng)前節(jié)點的左側(cè)處理 tile。 如果它未添加到已驗證或未驗證列表中，系統(tǒng)將會嘗試將其添加至列表。 TileValid() 是另一個需要定制以滿足游戲需求的函數(shù)。 如果它通過 TileValid() 驗證，將會調(diào)用 NewToList()，這將會向未驗證列表中添加一個新 tile。 以下三個代碼段執(zhí)行相同的流程，但是指稱不同的方向：右、上和下。
?
該迭代中需要做的最后一件事情是將未驗證列表從當(dāng)前代碼中刪除。 不再需要該 tile。
?
最后一段代碼可通過從目標(biāo)原路返回來構(gòu)建路線。 一定能夠找到返回起始位置的路線，因為路線中的每個代碼都會記錄將其放入列表中的代碼。 然后，返回最終路線(通過參數(shù))。 以下函數(shù)可返回新路線的長度。
?
總結(jié)
智能代理需要觀察其周圍的世界。 可以使用簡單的范圍檢查和光纖追蹤使根據(jù)視覺和聽覺所做的觀察快速成形，幫助代理在游戲過程中以更貼近人類思維的方式做決定。 確定目標(biāo)后，代理需要尋找路線，去往他們想去的地方。 碰撞和轉(zhuǎn)彎等快速方式適用于短期任務(wù)和簡單地圖，而更復(fù)雜的游戲需要分析地圖來查找最佳路線。 您可以對這些方法進(jìn)行優(yōu)化，以充分利用多線程部署，確保游戲流暢運行，即使需要處理大量實體和復(fù)雜地圖也是如此。
總結(jié)
以上是生活随笔為你收集整理的游戏行业的人工智能设计（二）：路径搜寻和感知的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 设计面向游戏的人工智能（三）：战术和战略
- 下一篇： 游戏行业的人工智能设计：AI的设计和实施