文 / Donald Kehoe

之前的所有本系列文章一直都在為本文奠定基礎(chǔ)。我們希望，您現(xiàn)在能夠清楚地了解到游戲人工智能 (AI) 是什么，并知道如何將其用于您的游戲中。如今，極具挑戰(zhàn)性的任務(wù)是，最大程度地提升您系統(tǒng)的性能。

無(wú)論您的系統(tǒng)有多好，但若它拖慢游戲速度，則一切毫無(wú)意義。高效的編程和優(yōu)化竅門所起作用比較有限；若您的目標(biāo)超出了單內(nèi)核的限制，那么您只能進(jìn)行并行處理(見(jiàn)圖 1)。
?

圖 1：在 Blizzard Entertainment 的《星際爭(zhēng)霸 2》* 中，大量單元在同一時(shí)間運(yùn)行自己的人工智能。多線程是最佳的處理方法。

若進(jìn)行處理時(shí)所用的系統(tǒng)具有一顆以上處理器或一顆多核處理器，您可將工作分配給多顆處理器。有兩種分配方式：任務(wù)并行化和數(shù)據(jù)并行化。

任務(wù)并行化

將您的應(yīng)用進(jìn)行多線程化處理的最輕松方法是，將它分解為多個(gè)特定的任務(wù)(見(jiàn)圖 2)。我們通常只使用幾種方法對(duì)組成游戲引擎的不同任務(wù)進(jìn)行封裝，以便其它系統(tǒng)可與它們進(jìn)行通信。
?

圖 2：功能并行化讓每個(gè)子系統(tǒng)利用各自的線程和內(nèi)核。遺憾的是，具有多個(gè)內(nèi)核而非任務(wù)的系統(tǒng)并未得到充分利用。

一個(gè)最好的例子是，該游戲引擎的音頻系統(tǒng)。音頻不需要與其它系統(tǒng)進(jìn)行交互。它只是按照命令進(jìn)行工作，即按需播音和混音。通信功能是用于播放和停止聲音的調(diào)用，可使音頻自動(dòng)、完美地適用于功能并行化。使用線程分析工具為該工作提供幫助，并通過(guò)您想在其自己的線程中運(yùn)行的代碼段之前和之后進(jìn)行的調(diào)用，音頻系統(tǒng)可被分解成自己的線程。

讓我們來(lái)了解下，您的人工智能系統(tǒng)如何運(yùn)用該功能并行化。根據(jù)您的游戲需要，您可能會(huì)有很多不同的任務(wù)，您可為它們提供自身線程。我們來(lái)了解下其中三種任務(wù)：路徑查找、戰(zhàn)略人工智能和實(shí)體系統(tǒng)本身。

路徑查找

您可以以這樣的方式實(shí)施您的路徑查找系統(tǒng)，即每個(gè)搜索路徑的實(shí)體可隨時(shí)按需調(diào)用自己的路徑。盡管本方法會(huì)起作用，但它意味著，每當(dāng)有路徑被請(qǐng)求時(shí)，引擎就要等待路徑查找器。若您將路徑查找重組為自己的系統(tǒng)，您可將它分解成它自己的線程。路徑查找器將會(huì)像資源管理器那樣運(yùn)行，在資源管理器中，新資源就是路徑。

想查找路徑的任何實(shí)體都可發(fā)出路徑查找請(qǐng)求，然后再立刻從路徑查找器取回一個(gè)“搜查令 (ticket)”。該搜查令就是一種路徑查找系統(tǒng)用來(lái)查找路徑的特殊句柄。這時(shí)實(shí)體可繼續(xù)運(yùn)行直至游戲循環(huán)到下一幀。實(shí)體可查驗(yàn)搜查令是否有效。若有效，實(shí)體找回路徑；否則，它可在繼續(xù)等待時(shí)繼續(xù)實(shí)施所需的任何操作。

在路徑查找系統(tǒng)中，搜查令用于記錄跟蹤路徑請(qǐng)求，而系統(tǒng)則對(duì)路徑請(qǐng)求進(jìn)行處理，不必?fù)?dān)心系統(tǒng)性能會(huì)受到影響。該類系統(tǒng)有一種積極效果，即自動(dòng)跟蹤發(fā)現(xiàn)的路徑。所以，當(dāng)收到對(duì)先前所發(fā)現(xiàn)的路徑的請(qǐng)求時(shí)，路徑查找器可為現(xiàn)有路徑提供搜查令。二手手機(jī)買賣在任何具有很多實(shí)體路徑的系統(tǒng)中，該方法都非常高效，因?yàn)槿魏温窂揭槐徽业骄涂赡軙?huì)被再次需要。

戰(zhàn)略人工智能

如上篇文章所述，全面管理游戲的人工智能系統(tǒng)與自身的線程匹配完美。它能分析游戲場(chǎng)并給不同實(shí)體發(fā)送命令，當(dāng)實(shí)體靠近游戲場(chǎng)時(shí)，它可分析命令。

在自身線程中的實(shí)體系統(tǒng)將很難為決策圖搜集信息。這些發(fā)現(xiàn)可發(fā)送到戰(zhàn)略人工智能系統(tǒng)，作為對(duì)決策圖的最新請(qǐng)求。當(dāng)戰(zhàn)略人工智能更新時(shí)，它可解析這些請(qǐng)求，更新該決策圖并進(jìn)行判斷調(diào)用。無(wú)論這兩個(gè)系統(tǒng)(戰(zhàn)略人工智能和實(shí)體)是否同步都是可以的：即使不同步，它們也不會(huì)影響人工智能的決策。(我們是在談?wù)?1/60 秒，玩家不會(huì)注意到人工智能反應(yīng)中的單幀延遲。)

數(shù)據(jù)并行化

數(shù)據(jù)并行化非常優(yōu)秀，并利用了具有多內(nèi)核的系統(tǒng)。但是有一個(gè)很大的弊端：功能并行化可能并未充分利用所有的可用內(nèi)核。當(dāng)您擁有的內(nèi)核數(shù)量多于任務(wù)時(shí)，您的程序?qū)⒉辉賾?yīng)用所有的可用處理能力(除非運(yùn)行程序的平臺(tái)對(duì)它進(jìn)行了處理，但最好不要依賴專用于通用應(yīng)用的功能)。輸入數(shù)據(jù)并行化(見(jiàn)圖 3)。

圖 3：數(shù)據(jù)并行化，某單一功能可利用所有可用內(nèi)核。

在功能并行化中，您利用一套完整的自動(dòng)單元，并為它提供和它一起運(yùn)行的自身線程。現(xiàn)在，您要將單一工作進(jìn)行分解，并將其分配給不同線程來(lái)完成。這樣做可達(dá)到與系統(tǒng)內(nèi)核一起按比例擴(kuò)大的優(yōu)點(diǎn)。您有帶八內(nèi)核的系統(tǒng)？很好。有 64 位的嗎？為什么沒(méi)有？雖然功能并行化支持您先指定要線程化的代碼段，再讓其自由運(yùn)行，但數(shù)據(jù)并行化可能還需一點(diǎn)額外工作以實(shí)現(xiàn)流暢運(yùn)行。例如，您可能會(huì)使用內(nèi)核線程(一種“主”線程)，它可跟蹤誰(shuí)在處理什么任務(wù)。子線程將需向主線程請(qǐng)求“工作”，以確保避免將同一任務(wù)執(zhí)行兩次。

實(shí)際上，使用內(nèi)核線程管理數(shù)據(jù)并行化是一種混合方法。內(nèi)核線程正使用功能并行化，然后該線程在用于數(shù)據(jù)并行化的不同內(nèi)核之間對(duì)數(shù)據(jù)進(jìn)行分解。

實(shí)施

線程工具如 OpenMP* (在大部分操作系統(tǒng)中免費(fèi)提供)，可助您比過(guò)去更輕松地將代碼分解成不同線程。只用編譯指令標(biāo)記可被分解的代碼段，用 OpenMP 處理其余的代碼段。要用工作模塊分解事物，您只需把線程調(diào)用放入遍歷所述資源的循環(huán)中。

在路徑查找系統(tǒng)示例中，路徑查找器會(huì)保存請(qǐng)求路徑列表。然后它會(huì)依次遍歷該列表并根據(jù)各個(gè)請(qǐng)求運(yùn)行實(shí)際的路徑查找功能，從而將它們保存在路徑列表中。可將該循環(huán)線程化，從而將循環(huán)的每次迭代分解成不同的線程。這些線程將會(huì)在第一可用內(nèi)核中運(yùn)行，支持最大程度地利用可用的處理能力。當(dāng)無(wú)任務(wù)可執(zhí)行時(shí)，內(nèi)核才會(huì)空閑。

用于多個(gè)請(qǐng)求以實(shí)施相同工作的那些系統(tǒng)潛力巨大。當(dāng)這些請(qǐng)求被間隔開(kāi)時(shí)，路徑查找器會(huì)自動(dòng)查驗(yàn)請(qǐng)求是否已得到處理。對(duì)于數(shù)據(jù)并行化，很可能會(huì)在同一時(shí)間發(fā)生對(duì)同一路徑的多個(gè)請(qǐng)求，這會(huì)導(dǎo)致冗余，破壞整個(gè)線程點(diǎn)。

為解決該冗余及其它冗余問(wèn)題，所述系統(tǒng)需跟蹤記錄正在進(jìn)行的任務(wù)都有哪些，而且只有在它們完成之后才能把它們從請(qǐng)求隊(duì)列中除去。所以，若收到的請(qǐng)求是針對(duì)已請(qǐng)求過(guò)的路徑，就需要先進(jìn)行檢查，然后再返回到搜查令指定的現(xiàn)有路徑。

不能隨便生成新線程。該過(guò)程將涉及對(duì)操作系統(tǒng) (OS) 的系統(tǒng)調(diào)用。當(dāng)該操作系統(tǒng)要完成它時(shí)，它會(huì)完成所需代碼，并創(chuàng)建線程。這可能會(huì)花費(fèi)很多時(shí)間(相對(duì)于處理速度來(lái)說(shuō))。這就是為何我們不想生成更多線程。如果正在請(qǐng)求的工作已得到處理，那么切勿運(yùn)行該任務(wù)。而且，如果該任務(wù)非常簡(jiǎn)單(例如從兩個(gè)非常近的點(diǎn)位之間查找路徑)，則不值得對(duì)其進(jìn)行過(guò)細(xì)分解。

下面介紹了路徑查找功能線程將要進(jìn)行的分解，并介紹了它如何將工作分解成數(shù)據(jù)線程：

請(qǐng)求路徑(開(kāi)始，目標(biāo))。從路徑查找器外部調(diào)用該功能，以得到一條線程。該功能：

遍歷完整的請(qǐng)求列表，確定該路徑(或其相似路徑)是否已被找到，然后再返回用于該路徑的搜查令。

(若路徑還未被找到)遍歷主動(dòng)請(qǐng)求列表以查找該路徑；若該路徑在該列表中，則該功能返回用于該待處理路徑的搜查令。

生成一條新請(qǐng)求并返回新搜查令(若以上方法均無(wú)效)。

檢查路徑(“搜查令”)。通過(guò)使用該搜查令，該功能遍歷完整的請(qǐng)求列表，并查找路徑，其中該搜查令對(duì)該路徑有效。它能夠返回路徑是否存在。

更新路徑查找器()。這是 shepherd 功能，可處理路徑查找線程的費(fèi)用。該功能可執(zhí)行以下任務(wù)：

解析新請(qǐng)求。相同路徑的多個(gè)請(qǐng)求可通過(guò)不同內(nèi)核同時(shí)生成。該段刪除了冗余，并將多個(gè)搜查令(來(lái)自不同請(qǐng)求)分配至相同請(qǐng)求。

通過(guò)主動(dòng)請(qǐng)求循環(huán)。該功能支持所有主動(dòng)請(qǐng)求并對(duì)它們進(jìn)行線程處理。每個(gè)循環(huán)開(kāi)始和結(jié)束時(shí)，代碼標(biāo)記為線程。每個(gè)線程將會(huì) (1) 查找請(qǐng)求的路徑，(2) 借助分配的搜查令將它保存在完成的路徑列表中，以及 (3) 將任務(wù)從主動(dòng)列表中刪除。

解決沖突

您可能已注意到這一設(shè)置可能造成災(zāi)難性后果。所有需要寫入請(qǐng)求隊(duì)列的不同線程，或所有需要添加某些內(nèi)容至已完成“樁”的數(shù)據(jù)線程，會(huì)導(dǎo)致寫入沖突，即一個(gè)線程將某內(nèi)容寫入插槽 A，而另一個(gè)線程將其他內(nèi)容同時(shí)寫入插槽 A。該沖突會(huì)導(dǎo)致眾所周知的“競(jìng)態(tài)條件”。

為避免寫入沖突，代碼段可標(biāo)記為“關(guān)鍵”。當(dāng)某內(nèi)容標(biāo)記為關(guān)鍵時(shí)，一次只有一個(gè)線程能夠訪問(wèn)該代碼段：所有想要執(zhí)行相同操作(訪問(wèn)相同內(nèi)容)的其他線程都需要等待。當(dāng)多個(gè)線程相互阻止訪問(wèn)內(nèi)容時(shí)，該行為會(huì)導(dǎo)致嚴(yán)重問(wèn)題，如崩潰。該設(shè)置可切實(shí)避免崩潰。線程工作完成后，方便時(shí)可訪問(wèn)內(nèi)存段，且無(wú)需關(guān)聯(lián)其他線程可能需要的其他段。

保持系統(tǒng)同步

因此，您讓所有的單獨(dú)人工智能子系統(tǒng)實(shí)現(xiàn)了自主，使它們能夠隨意使用找到的所有可用計(jì)算資源。運(yùn)行速度極快，但它們失去控制了嗎？

游戲需要提供結(jié)構(gòu)化用戶體驗(yàn)。引擎必須能夠保持系統(tǒng)同步。您不能讓部分游戲元素先于其他元素運(yùn)行 1-2 個(gè)幀。當(dāng)敵人開(kāi)始行動(dòng)時(shí)，您不能讓部隊(duì)無(wú)所事事地等待路徑。好父母需要公平對(duì)待子女。

主游戲引擎循環(huán)負(fù)責(zé)兩類操作：渲染和更新。串行編程可幫助輕松保持相關(guān)系統(tǒng)同步。首先所有更新執(zhí)行，然后渲染可繪制更新內(nèi)容。此外，相關(guān)信息可能不易理解。

最終，移動(dòng)更新(常常基于軌跡)的運(yùn)行速度可能比渲染器快幾幀。結(jié)果，動(dòng)畫會(huì)出現(xiàn)跳動(dòng)情況，即實(shí)體可能呈現(xiàn)跳動(dòng)和加速移動(dòng)的情況。路徑查找可能考慮實(shí)體位置快照，并可能運(yùn)行無(wú)效數(shù)據(jù)。

各種系統(tǒng)的同步解決方案具有出色的簡(jiǎn)單性。事實(shí)上，它可應(yīng)用于多數(shù)引擎。當(dāng)主游戲循環(huán)得到更新時(shí)，它可跟蹤全局時(shí)間索引。所有的線程將只需要處理當(dāng)前(和過(guò)去，而非未來(lái))的時(shí)間索引更新。

當(dāng)有關(guān)當(dāng)前時(shí)間索引的指定任務(wù)的工作全部完成，線程可處于睡眠狀態(tài)，直到新的時(shí)間索引生成。這一行為不僅可幫助確保系統(tǒng)相互同步，而且可確保線程不會(huì)使用多余的內(nèi)核。移動(dòng)工作能夠完美處理不斷出現(xiàn)的碰撞和移動(dòng)軌跡，并能在提前完成時(shí)共享處理能力。再次強(qiáng)調(diào)，您能夠充分利用可用內(nèi)核。

線程指南

以下是大家在設(shè)計(jì)多線程系統(tǒng)時(shí)需要了解的一些事情：

功能并行化：用于系統(tǒng)可以自主運(yùn)行的情況。一些功能需要配置在系統(tǒng)中以解決沖突和冗余問(wèn)題。

數(shù)據(jù)并行化：

用于實(shí)施批量操作的情況。

設(shè)計(jì)原則是確保回寫保持最少程度，并在流程結(jié)束時(shí)發(fā)生。

對(duì)最新信息(可在其他線程中編輯)的依賴度最低，或避免這種依賴。(我的戰(zhàn)略信息過(guò)時(shí) 1/60 秒會(huì)怎么樣？)

確保您在工作時(shí)對(duì)于另一個(gè)系統(tǒng)的使用需求不會(huì)阻妨礙線程運(yùn)行：“請(qǐng)求路徑”，“檢查路徑”，而非“獲取路徑”。

線程失效時(shí)

有時(shí)，線程可能無(wú)法正常運(yùn)行。借助 OpenMP 等工具，您可以輕松調(diào)整系統(tǒng)將即時(shí)把工作分解為線程的數(shù)量。借助英特爾? VTuneTM 性能分析器和英特爾? 線程調(diào)節(jié)器, 您能夠清晰了解系統(tǒng)在不同并行化級(jí)別中的有效性。在下面這些案例中，您可能希望避免線程操作，然而：

極度復(fù)雜的系統(tǒng)。如果子系統(tǒng)關(guān)聯(lián)過(guò)多其他系統(tǒng)，子系統(tǒng)或其他系統(tǒng)常常需要等待，此時(shí)，線程操作可能無(wú)濟(jì)于事。此外，系統(tǒng)本身可能獲益于重新設(shè)計(jì)。

原子工作負(fù)載。如果子系統(tǒng)的工作無(wú)法分解，您可能無(wú)法進(jìn)行并行化處理。音頻混合任務(wù)可能與線程一樣可以發(fā)揮重要作用，但該任務(wù)工作需要將多種聲音混合至最終傳輸至揚(yáng)聲器的頻道。如果您的系統(tǒng)在混合之前對(duì)單個(gè)音頻數(shù)據(jù)塊進(jìn)行了計(jì)算，那么它可能對(duì)其進(jìn)行線程處理。

高昂費(fèi)用。這些系統(tǒng)中部分需要實(shí)施額外的工作(如路徑查找)。如果線程帶來(lái)的效益不足以彌補(bǔ)相關(guān)費(fèi)用，那么可能需要避免實(shí)施或禁用線程處理。這可能適用于具有較少元素(實(shí)體、路徑等)的系統(tǒng)。

重復(fù)代碼。在某些情況下，多個(gè)線程會(huì)使用相同代碼，結(jié)果卻造成代碼部分浪費(fèi)或被忽略。在工作開(kāi)始之前，冗余檢查一般能避免這種情況。

多顆處理器和多核處理器(和多顆多核處理器)能夠顯著增強(qiáng)線程處理的重要性。任何程序員的目標(biāo)是充分利用可用的處理能力。系統(tǒng)人工智能愿景受到硬件發(fā)展現(xiàn)狀限制可以理解，但不能因?yàn)橛布吹玫匠浞掷枚磺啊＝柚軌蚝?jiǎn)化線程實(shí)施的現(xiàn)代工具，您完全應(yīng)該設(shè)計(jì)支持線程處理的代碼。

總結(jié)

開(kāi)發(fā)有趣的、可高效運(yùn)行的動(dòng)態(tài)人工智能系統(tǒng)非常簡(jiǎn)單。首先應(yīng)該提升效率和實(shí)施優(yōu)化。通過(guò)合理組織系統(tǒng)以充分利用任務(wù)和數(shù)據(jù)并行化，您能夠幫助確保系統(tǒng)實(shí)現(xiàn)最大運(yùn)行速度，并能夠隨著標(biāo)配計(jì)算內(nèi)核的日益增多不斷擴(kuò)展以滿足行業(yè)需求。

如本系列文章所述，游戲人工智能的人工特征比智能特征更為顯著。程序員有責(zé)任創(chuàng)建系統(tǒng)代理功能，以模擬真實(shí)對(duì)手的行為。從低級(jí)規(guī)則和路徑查找到高級(jí)戰(zhàn)術(shù)與戰(zhàn)略人工智能，基本組件并不會(huì)過(guò)度復(fù)雜。

總結(jié)

以上是生活随笔為你收集整理的发挥游戏人工智能的最大价值：线程化的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。