3D游戲開發(fā)技術(shù)-第三章游戲開發(fā)中的人工智能詳解課件

1、第三章 游戲開發(fā)中的人工智能技術(shù)授課人：張勇提綱AI的基本概念游戲中簡(jiǎn)單的AI模式游戲中常用的AI技術(shù)有限狀態(tài)機(jī)模糊邏輯等A*算法神經(jīng)網(wǎng)絡(luò)遺傳算法提綱AI的基本概念游戲中簡(jiǎn)單的AI模式游戲中常用的AI技術(shù)有限狀態(tài)機(jī)模糊邏輯等A*算法神經(jīng)網(wǎng)絡(luò)遺傳算法簡(jiǎn)介（1）AI的定義計(jì)算機(jī)或其他機(jī)器有能力執(zhí)行那些通常認(rèn)為需要智慧才能做的事。創(chuàng)建擁有智慧的機(jī)器的過程或科學(xué)。Game AI使得游戲表現(xiàn)出與人的智能行為/ 活動(dòng)相類似，或者與玩家的思維/感知相符合的特性。融合娛樂性。簡(jiǎn)介（2）游戲中涉及的AI技術(shù)有限狀態(tài)機(jī)基于規(guī)則的系統(tǒng)，有限個(gè)狀態(tài)連接成一有向圖，每一條邊稱為一個(gè)轉(zhuǎn)移。專家系統(tǒng)知識(shí)表示專家的經(jīng)驗(yàn)，并在

2、此基礎(chǔ)上作自動(dòng)推理。案例式推理將輸入與數(shù)據(jù)庫中已有的案例進(jìn)行比較，選取最為相近的案例，其已有的解決方法即為輸出。簡(jiǎn)介（3）游戲中涉及的AI技術(shù)（續(xù)）產(chǎn)生式系統(tǒng)包含多個(gè)產(chǎn)生式，每一條產(chǎn)生式由條件和動(dòng)作兩部分組成，當(dāng)產(chǎn)生式的條件滿足時(shí)，系統(tǒng)就執(zhí)行相應(yīng)的動(dòng)作。決策樹給定輸入，從樹的根部開始，將輸入與當(dāng)前結(jié)點(diǎn)相比較，選擇當(dāng)前結(jié)點(diǎn)的某一個(gè)子結(jié)點(diǎn)作為下一次比較的對(duì)象。當(dāng)?shù)竭_(dá)樹的葉子時(shí)，則給出相應(yīng)的決策。搜索方法找到一列動(dòng)作（或狀態(tài)轉(zhuǎn)移），使得最終的結(jié)果滿足某一特定目標(biāo)。簡(jiǎn)介（4）游戲中涉及的AI技術(shù)（續(xù)）多Agent研究在多個(gè)相互競(jìng)爭(zhēng)相互合作的智能體之間所產(chǎn)生的交互智能行為。人工生命多agent系統(tǒng)一種，

3、試圖將生命系統(tǒng)中一些普遍規(guī)律應(yīng)用到虛擬世界的人工智能體上。群組行為(Flocking)人工生命的一類，研究協(xié)同移動(dòng)技術(shù)，例如人工智能體如何在大量的羊群中移動(dòng)。簡(jiǎn)介（5）游戲中涉及的AI技術(shù)（續(xù)）Robotics讓機(jī)器在自然環(huán)境下交互的工作遺傳算法直接模擬生物進(jìn)化過程，通過隨機(jī)選擇、雜交和突變等對(duì)程序、算法或者一系列參數(shù)進(jìn)行操作神經(jīng)網(wǎng)絡(luò)模擬動(dòng)物神經(jīng)系統(tǒng)功能的機(jī)器學(xué)習(xí)方法通過反復(fù)調(diào)節(jié)系統(tǒng)內(nèi)部中各個(gè)神經(jīng)元之間的連接參數(shù)，使得訓(xùn)練得到的系統(tǒng)在大多數(shù)情況下作出優(yōu)或者近似優(yōu)的反應(yīng)簡(jiǎn)介（6）游戲中涉及的AI技術(shù)（續(xù)）模糊邏輯與傳統(tǒng)二值（對(duì)-錯(cuò)）邏輯不同，模糊邏輯用實(shí)數(shù)表示物體隸屬于某一類的可能性置信網(wǎng)絡(luò)提供

4、建立不同現(xiàn)象之間內(nèi)在因果關(guān)系的工具，并利用概率理論處理未知的和不完全的知識(shí)對(duì)當(dāng)前狀態(tài)作出判斷，并決定下一步可能的動(dòng)作以及其帶來的后果簡(jiǎn)介（7）GAME AI技術(shù)的分類定性定性行為或其表現(xiàn)是特定的，并且可預(yù)測(cè)，沒有不確定性。非定性非定性行為有某種不確定性，有點(diǎn)不可預(yù)測(cè)。具體實(shí)例是，讓NPC學(xué)習(xí)到適應(yīng)玩家的作戰(zhàn)戰(zhàn)術(shù)。提綱AI的基本概念游戲中簡(jiǎn)單的AI模式游戲中常用的AI技術(shù)有限狀態(tài)機(jī)模糊邏輯等A*算法神經(jīng)網(wǎng)絡(luò)遺傳算法定性AI算法確定性算法指預(yù)先編入代碼當(dāng)中的可預(yù)測(cè)的行為從最簡(jiǎn)單的算法開始例如，系統(tǒng)中有一顆小行星，以某一速度作勻速直線運(yùn)動(dòng)，它在任意時(shí)刻的位置由下列公式?jīng)Q定：某種程度上，它們是智能的，

5、但是這種智能是確定的，可預(yù)測(cè)的追逐/閃躲AI當(dāng)智能體找到目標(biāo)后，一心一意向其移動(dòng)，而不考慮任何其他的因素，例如障礙物、另外的目標(biāo)等非常機(jī)械化在每一幀中，智能體計(jì)算其到目標(biāo)的前進(jìn)方向，并根據(jù)其速度，前進(jìn)一段距離磚塊環(huán)境基本追逐算法if(predatorX preyX)predatorX -;else if (predatorX preyY)predatorY -;else if (predatorY predatorX)preyX +;else if (preyX predatorY)preyY +;else if (preyY predatorY)prey -;改進(jìn)的Tracking算法：在每

6、一幀中，智能體仍然首先計(jì)算其到目標(biāo)的前進(jìn)方向這時(shí)，智能體的速度允許發(fā)生變化，并根據(jù)更新后的速度，計(jì)算下一幀的位置速度有一個(gè)上限，超過這個(gè)上限，智能體的速度將減慢，直到重新加速為止追逐/閃躲AI連續(xù)環(huán)境連續(xù)環(huán)境運(yùn)動(dòng)=幾何變換（2D?）追逐/閃躲AI群聚算法1987年，Craig Reynolds在SIGGRAPH論文Flocks, Herbs, and Schools: A Distributed Behavioral Model中第一次提到了群聚算法，這個(gè)算法在日后廣泛地被人們使用，用來仿真整群的鳥、魚或其他生物群。Reynolds的鳥群運(yùn)動(dòng)三條規(guī)則是：（1）凝聚：每只鳥都向它鄰近同伴的平均位

7、置移動(dòng)。（2）對(duì)齊：每只鳥都把自己前進(jìn)的方向和它鄰近同伴的平均方向保持一致。（3）分隔：每只鳥在飛行時(shí)都要避免碰上身邊其它同伴。 就這么簡(jiǎn)單!然而簡(jiǎn)單的規(guī)則卻保證了鳥群紛繁地、優(yōu)雅地飛行而隊(duì)形不散。群聚算法為了分析我們這個(gè)群聚算法，我們需要理解一些基本的概念：（1）單位的視野，我們以r為單位的視野半徑，以為視野角度，落在這個(gè)圓弧內(nèi)的所有物體都是可見的。（2）避開規(guī)則（Avoidance rule），單位不會(huì)被彼此撞上。（3）凝聚規(guī)則，單位離得太遠(yuǎn)就應(yīng)該靠近一點(diǎn)，這個(gè)規(guī)則和避開規(guī)則合在一起，從而形成了群聚。群聚算法群聚算法單位的視野寬視野VS窄視野以勢(shì)函數(shù)實(shí)現(xiàn)移動(dòng)Lenard-Jones勢(shì)函數(shù)代

8、表分子間的吸引和排斥的勢(shì)能，取該勢(shì)函數(shù)的導(dǎo)數(shù)，可得代表力的函數(shù)。追逐、閃躲、避碰、群聚追逐、閃躲避開障礙物 引力強(qiáng)度A設(shè)置為0，只保留斥力分量。同時(shí)調(diào)整B，決定斥力強(qiáng)度，以及m來決定衰減。群聚 通過引力分量控制。以勢(shì)函數(shù)實(shí)現(xiàn)移動(dòng)以勢(shì)函數(shù)實(shí)現(xiàn)移動(dòng)提綱AI的基本概念游戲中簡(jiǎn)單的AI模式游戲中常用的AI技術(shù)有限狀態(tài)機(jī)模糊邏輯等A*算法神經(jīng)網(wǎng)絡(luò)遺傳算法有限狀態(tài)機(jī)（FSM）狀態(tài)（要采取的行為）追擊隨機(jī)走動(dòng)巡邏吃轉(zhuǎn)移（發(fā)生轉(zhuǎn)移的原因）時(shí)間片結(jié)束發(fā)生某個(gè)事件完成某個(gè)行為伐木將木頭運(yùn)往最近的倉庫足夠多木材放下木頭:返回林場(chǎng)到倉庫到林場(chǎng)有限狀態(tài)機(jī)（FSM）條件定義發(fā)生轉(zhuǎn)移的先決條件輸入和事件允許狀態(tài)機(jī)對(duì)環(huán)境變化

9、作出反應(yīng)動(dòng)作作為狀態(tài)的一部分，或者伴隨轉(zhuǎn)移出現(xiàn)狀態(tài)空間圖有向圖每個(gè)結(jié)點(diǎn)表示系統(tǒng)狀態(tài)模型，每條弧表示狀態(tài)轉(zhuǎn)移所伴隨的動(dòng)作行為結(jié)點(diǎn)可以是無窮多個(gè)有些結(jié)點(diǎn)之間可能沒有弧相連接FSM設(shè)計(jì)步驟狀態(tài)的設(shè)置。設(shè)置一個(gè)開始狀態(tài)。創(chuàng)建一個(gè)映射，每個(gè)輸入對(duì)應(yīng)一個(gè)狀態(tài)間轉(zhuǎn)換函數(shù)。編寫狀態(tài)轉(zhuǎn)換函數(shù)。模糊邏輯傳統(tǒng)邏輯把思維過程絕對(duì)化，從而達(dá)到精確、嚴(yán)格的目的舉例：一個(gè)被討論的對(duì)象X，要么屬于某一個(gè)集合A，要么不屬于該集合，兩者比居其一，而且兩者僅居其一，決不模棱兩可對(duì)于命題：張三的性格穩(wěn)重，如何判斷這一命題的真假？模糊邏輯對(duì)于上述的例子，模糊邏輯允許我們用一個(gè)0,1的實(shí)數(shù)表示X屬于A的隸屬程度。傳統(tǒng)邏輯即隸屬程度只能從

10、0和1之間選擇的情況對(duì)于“性格穩(wěn)重”這個(gè)模糊概念，能夠用“一點(diǎn)而也不穩(wěn)重”、“不太穩(wěn)重”、“不好說”、“有點(diǎn)穩(wěn)重”、“挺穩(wěn)重”、“很穩(wěn)重”等沒有明確界限的詞語形容模糊邏輯的應(yīng)用將重心轉(zhuǎn)移至物體屬于某個(gè)集合的隸屬程度上在AI領(lǐng)域的主要應(yīng)用為決策行為選擇輸入、輸出過濾符合邏輯操作設(shè)A,B,C均為U中的模糊集模糊并若對(duì)8x2U，均有c=max(A(x),B(x)，則稱C為A與B的模糊并模糊交若對(duì)8x2U，均有c=min(A(x),B(x)，則稱C為A與B的模糊交例子大約6英尺長(zhǎng)的高的人歸屬度函數(shù)與或非模糊控制實(shí)例舉例：車輛駕駛前提：兩輛車之間不能相撞在模糊邏輯中的實(shí)現(xiàn)：用兩個(gè)變量描述每一輛車當(dāng)前時(shí)刻

11、，車與前面一輛車之間的距離d當(dāng)前時(shí)刻與前一時(shí)刻距離的差d模糊控制實(shí)例If d=0且d=兩個(gè)車位長(zhǎng)，保持現(xiàn)有速度If d0且d0且d兩個(gè)車位長(zhǎng)，加快速度模糊的有限狀態(tài)機(jī)將模糊邏輯和有限狀態(tài)機(jī)結(jié)合狀態(tài)之間的遷移不再是確定的同時(shí)有多個(gè)狀態(tài)FSMFuSM路徑規(guī)劃狀態(tài)智能體在空間的位置其他離散空間體素室內(nèi)位置局部區(qū)塊（tile）操作從一個(gè)位置移動(dòng)到其他位置路徑規(guī)劃算法必須對(duì)狀態(tài)空間進(jìn)行搜索，才能轉(zhuǎn)移至目標(biāo)狀態(tài)完全性如果目標(biāo)狀態(tài)存在，算法是否能夠?qū)⑵湔业?？時(shí)間復(fù)雜度空間復(fù)雜度能夠找到最優(yōu)解搜索策略如何評(píng)價(jià)搜索算法時(shí)間：多長(zhǎng)時(shí)間能夠找到解找到的解是最優(yōu)、次優(yōu)還是其他盲目搜索沒有先驗(yàn)知識(shí)僅僅知道目標(biāo)狀態(tài)是什么

12、經(jīng)驗(yàn)搜索用經(jīng)驗(yàn)公式表示擁有的先驗(yàn)知識(shí)“經(jīng)驗(yàn)”只能作相對(duì)簡(jiǎn)單、低級(jí)的決策啟發(fā)式圖搜索過程利用所處理問題的啟發(fā)信息引導(dǎo)搜索，稱為啟發(fā)式搜索，可以達(dá)到減少搜索范圍，降低問題復(fù)雜度的目的。啟發(fā)式圖搜索算法A基本思想：如果既考慮從起始節(jié)點(diǎn)到節(jié)點(diǎn)n的路徑費(fèi)用，又考慮從節(jié)點(diǎn)n到達(dá)目標(biāo)節(jié)點(diǎn)的費(fèi)用，即定義一個(gè)評(píng)價(jià)函數(shù)f，對(duì)當(dāng)前的搜索狀態(tài)進(jìn)行評(píng)估，找出一個(gè)最有希望的節(jié)點(diǎn)來擴(kuò)展。其形式為：f (n)= g (n)+ h (n) n為被評(píng)價(jià)的節(jié)點(diǎn)。 用此函數(shù)來排列Open表中節(jié)點(diǎn)順序的圖搜索算法稱為A算法。 最佳圖搜索算法A* 在算法A中，當(dāng)h(n)h*(n)時(shí)，我們把這個(gè)算法稱為A*算法，A*算法具有如下的性質(zhì)：完

13、備性：如果問題有解，則算法一定能找到解。可采納性：如果問題有解，則算法一定能找到最佳解。即算法總能找到一條從S到目標(biāo)節(jié)點(diǎn)的最佳路徑。 最優(yōu)性：對(duì)兩個(gè)算法A*算法A1和A2，若對(duì)所有非目標(biāo)節(jié)點(diǎn)均有 h1(n) h2(n)h*(n)則算法 A1展開的節(jié)點(diǎn)數(shù)目至少和A2一樣多。（啟發(fā)函數(shù)和A*算法的關(guān)系） 不同啟發(fā)函數(shù)對(duì)比 下表為不同啟發(fā)函數(shù)，應(yīng)用A*算法求最佳解時(shí)所擴(kuò)展和生成的節(jié)點(diǎn)數(shù)。啟發(fā)式函數(shù)的選取影響搜索效率。A*路徑規(guī)劃假設(shè)從A點(diǎn)移動(dòng)到一墻之隔的B點(diǎn)，綠色的是起點(diǎn)A，紅色是終點(diǎn)B，藍(lán)色方塊是中間的墻。A*路徑規(guī)劃f (n)= g (n)+ h (n)g(n)為從起點(diǎn)A沿著產(chǎn)生的路徑，移動(dòng)到網(wǎng)

14、格上指定方格的移動(dòng)耗費(fèi)（水平或者垂直移動(dòng)的耗費(fèi)為10，對(duì)角線方向耗費(fèi)為14）h(n)為從網(wǎng)格上那個(gè)方格移動(dòng)到終點(diǎn)B的預(yù)估移動(dòng)耗費(fèi)（曼哈頓距離）A*路徑規(guī)劃A*路徑規(guī)劃AI設(shè)計(jì)技巧對(duì)于行為簡(jiǎn)單的物體，使用簡(jiǎn)單的確定性AI技術(shù)對(duì)于不是主要角色，但是需要一點(diǎn)智能行為的物體，可以對(duì)其設(shè)定幾種模式，并加上一點(diǎn)隨機(jī)的因素?cái)_動(dòng)即可對(duì)于比較重要的角色，可以使用有限狀態(tài)機(jī)技術(shù)，加上另外一些輔助技巧對(duì)于最最重要的角色，你需要利用一切可能利用的技術(shù)狀態(tài)驅(qū)動(dòng)，使用條件邏輯、概率、以及經(jīng)歷過的狀態(tài)等控制狀態(tài)轉(zhuǎn)移如果狀態(tài)轉(zhuǎn)移條件滿足，物體要能夠發(fā)生強(qiáng)制性狀態(tài)轉(zhuǎn)移動(dòng)作A*路徑規(guī)劃建議使用更小的地圖或者更少的尋路者。不要同時(shí)給多個(gè)對(duì)象尋路。路徑規(guī)劃的層次細(xì)節(jié)模型。預(yù)處理地圖。平滑路徑。不規(guī)則區(qū)域。神經(jīng)網(wǎng)絡(luò)監(jiān)督學(xué)習(xí) 輸入學(xué)習(xí)樣本，隨機(jī)給定初始值，根據(jù)目標(biāo)輸出，使用反向傳播算法對(duì)網(wǎng)絡(luò)的權(quán)值和偏置進(jìn)行反復(fù)的調(diào)整訓(xùn)練，使輸出的向量與期望向量盡可能地接近，當(dāng)網(wǎng)絡(luò)輸出層的誤差平方和小于指定的誤差時(shí)訓(xùn)練完成。自動(dòng)