Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),*,*,人工智能,小組成員：,xx,人工智能,游戲中的人工智能,群聚,什么是群聚呢？,群聚，就是多個(gè)非玩家角色一起行動(dòng)，而不是個(gè)別行動(dòng)。比如說(shuō)：你看到的是一群大雁，它們的飛行是有一定的規(guī)律，而且你完全可以看出來(lái)它們會(huì)排成一字或者人字，不會(huì)是亂糟糟的飛行。那么，我們?cè)谟螒蛑?，諸如巡邏小隊(duì)之類(lèi)的移動(dòng)又是什么樣的呢？,1987,年，,Craig Reynolds,發(fā)表了一篇名為,Flocks,，,Herds and Schools,：,A Distributed Behavial Model,的論文，在這篇論文中，他提出了基本的群聚算法模型，甚至可以這樣說(shuō)，后續(xù)的一系列群聚算法都有這篇論文的身影。,那么我們來(lái)看看,Craig Reynolds,提到的,boids,類(lèi)鳥(niǎo)群的模擬群體。在這種類(lèi)鳥(niǎo)群里面，是沒(méi)有領(lǐng)導(dǎo)核心，它們都是跟著群體在走，而這個(gè)群體似乎是自己有自己的想法。,Reynolds,基本群聚算法核心,群體行為的核心是基本的群聚算法。,“,單位,”（,unit,）指代組成群體的個(gè)別實(shí)體。,凝聚,：每個(gè)單位都往其臨近單位的平均位置行動(dòng)。,對(duì)齊,：每個(gè)單位行動(dòng)時(shí)，都要把自己對(duì)齊在其臨近單位的平均方向上。,分隔,：每個(gè)單位行動(dòng)時(shí)，要避免撞上其臨近單位。,Reynolds,基本群聚算法是沒(méi)有,領(lǐng)導(dǎo)核心,的；就,某種意義而言，它們都跟著整個(gè)群體移動(dòng)。,每個(gè)單位都必須有行進(jìn)的能力；每個(gè)單位都,必須知道其局部周?chē)那闆r，即鄰近單位位,置、方向以及群體中與自身最靠近的單位之,間的距離。,在仿真物理環(huán)境中可以對(duì)仿真中的單位施加轉(zhuǎn)向,力使其改變方向；在磚塊環(huán)境中可以采用視線(xiàn)方,法讓單位改變方向或朝特定點(diǎn)移動(dòng)。,為了分析我們這個(gè)群聚系統(tǒng)，我們需要理解一些基本的概念：,1,，,單位的視野，我們以,r,為單位的視野半徑，以,為視野角度，落在這個(gè)圓弧內(nèi)的所有物體都是可見(jiàn)的。,2,，,避開(kāi)規(guī)則（,Avoidance rule,），單位不會(huì)被彼此撞上。,3,，,凝聚規(guī)則，單位離得太遠(yuǎn)就應(yīng)該靠近一點(diǎn)，這個(gè)規(guī)則和避開(kāi)規(guī)則合在一起，從而形成了群聚。,磚塊環(huán)境中的移動(dòng)模式,非確定性方法（加入隨機(jī)因素）：,1,、初始化路徑數(shù)組，移動(dòng)數(shù)組,2,、用,Bresenham,線(xiàn)段算法計(jì)算不同的移動(dòng)模式,3,、將模式標(biāo)準(zhǔn)化,4,、設(shè)定前進(jìn)速率，按照設(shè)定好的移動(dòng)模式移動(dòng)，當(dāng)?shù)竭_(dá)線(xiàn)段的端點(diǎn)時(shí)檢查移動(dòng)數(shù)組，以確定移動(dòng)方向。,到目前為止，我們討論的群聚規(guī)給大家留下了深刻印象。然而，像這樣的群聚行為如果在游戲中，這些單位以群體形態(tài)移動(dòng)式，還能避免撞上游戲世界里的物體，那就更實(shí)用了。,實(shí)際上加入避開(kāi)障礙物的行為其實(shí)相當(dāng)簡(jiǎn)單，我們所要做的就是提供某種機(jī)制給那些單位使用，讓他們看到前方，再施加適當(dāng)?shù)霓D(zhuǎn)向力，使其避開(kāi)路徑中的障礙物。,首先，我們運(yùn)算向量,a,，這只是該單位和障礙物位置間的差值，接著，取,a,和,v,的內(nèi)積，將,a,投射到,v,上，由此可得向量,p,，把向量,p,減去向量,a,，可得向量,b,，現(xiàn)在要測(cè)試,v,是否和圓的某處相交，得測(cè)試兩種情況。,1.p,的數(shù)值必須小于,v,的數(shù)值。,2.b,的數(shù)值必須小于該障礙物的半徑,r,。如果兩者都是如此，則需要校正轉(zhuǎn)向力，否則，該單位可繼續(xù)沿當(dāng)前方向前進(jìn)。,追隨領(lǐng)頭者,對(duì)基本群聚算法的修改不必只限于避開(kāi)障礙物。因?yàn)閬?lái)自于各種規(guī)則的轉(zhuǎn)向力都在同一變量中累加，然后一次施加，以控制該單位的方向，所以，我們還可以在考慮過(guò)的規(guī)則之上在疊加其他許多有效的規(guī)則。,其中一條有趣的外加規(guī)則，就是跟隨領(lǐng)頭者規(guī)則。如前所述，我們討論的群聚規(guī)則是沒(méi)有領(lǐng)頭者的，然而，如果我們把基本群聚算法和某些領(lǐng)頭者,AI,結(jié)合起來(lái)，就可以在游戲中使用群聚功能時(shí)，開(kāi)啟許多新的可能效果。,如果我們?cè)谄渲屑尤腩I(lǐng)頭者，就能讓群體的移動(dòng)更有目的性，或者看起來(lái)比較有智能。,我們來(lái)看看一個(gè)實(shí)際例子：,另一種群聚方法,簡(jiǎn)化集群技術(shù),Reynolds,的群聚算法已經(jīng)被很好地證明了，而且在生成若干組智能體的逼真動(dòng)作效果非常好。但是，該算法在計(jì)算上的開(kāi)銷(xiāo)大，尤其是在有大量智能體或者有復(fù)雜場(chǎng)景需要探測(cè)的時(shí)候。因此，他們有時(shí)候不適合實(shí)時(shí)的應(yīng)用程序，比如電視游戲。,所以我們有必要對(duì)集群技術(shù)進(jìn)一步的進(jìn)行簡(jiǎn)化。,群聚算法在模擬少量或中等數(shù)量的生物的自然行為時(shí)是完美的，尤其當(dāng)這些生物的運(yùn)動(dòng)（而不是生物和生物之間的影響、以及生物和場(chǎng)景之間的互動(dòng)）是主要的關(guān)注焦點(diǎn)的游戲中（例如任天堂的,Pikmin,）。,但是，隨著生物個(gè)數(shù)的增加，傳統(tǒng)的群聚算法開(kāi)銷(xiāo)越來(lái)越大。在群聚中每個(gè)智能體必須檢查其他所有智能體以確定是否因距離太近而產(chǎn)生影響，在這種情況下，如果存在,n,個(gè)智能體的場(chǎng)景，需要計(jì)算,1/2(n),次獨(dú)立的距離計(jì)算（給出中間的結(jié)果儲(chǔ)存在交互的數(shù)組里）。那么分離規(guī)則，隊(duì)列規(guī)則和聚合規(guī)則必須對(duì)每個(gè)智能體計(jì)算它附近的每個(gè)智能體。另一方面，因?yàn)橛绊懯窍嗷サ?，所以保存中間結(jié)果可以使計(jì)算量減半。,那么如何對(duì)集群技術(shù)進(jìn)行簡(jiǎn)化呢？,以下將對(duì)如何對(duì)集群技術(shù)進(jìn)行簡(jiǎn)化給出兩點(diǎn)方法：,1.,從群體初始化方面入手。,2.,從群體運(yùn)動(dòng)方面入手。,參考資料：,人工智能游戲編程真言,-,清華大學(xué)出版社,游戲開(kāi)發(fā)中的人工智能,-,東南大學(xué)出版社,游戲設(shè)計(jì)概論,清華大學(xué)出版社,參考網(wǎng)站：,http:/ operator,（重載運(yùn)算符）會(huì)替我們做向量加法。,DoUnitAI,（）找出鄰近單位并收集信息后，就可以使用群聚規(guī)則了。,此段程序第一件事是檢查鄰近單位數(shù)量是否大于,0.,如果是，我們就能繼續(xù)計(jì)算鄰近單位的平均位置。做法是以所有鄰近單位位置的向量總和,Pave,除以鄰近單位數(shù)量,N,。,最后一行就是實(shí)際計(jì)算滿(mǎn)足凝聚規(guī)則的轉(zhuǎn)向力。,凝聚,基本上，累加在,FS.X,的轉(zhuǎn)向力是當(dāng)前單位的方向，以及其鄰近單位平均位置向量間的角度的線(xiàn)性函數(shù)，也就是說(shuō)，如果角度大，則轉(zhuǎn)向力也會(huì)相對(duì)較大；如果角度小，則轉(zhuǎn)向力也會(huì)相對(duì)較小。這正是我們想要的。如果當(dāng)前單位的方向和鄰近單位的平均位置的方向相距很遠(yuǎn)，我們會(huì)想讓他做大幅度的轉(zhuǎn)彎。如果其方向和鄰近單位平均位置的方向不太遠(yuǎn)，我們只想對(duì)其方向做小范圍的修正。,返回,對(duì)齊,對(duì)齊意指我們想讓群聚中的所有單位都大致朝相同方向前進(jìn)。為了滿(mǎn)足這條規(guī)則，每個(gè)單位都應(yīng)該在行進(jìn)時(shí)，試著以等同其鄰近單位平均方向的方向來(lái)前進(jìn)。,中間以粗線(xiàn)表示單位是沿著和其相連的粗箭頭方向進(jìn)行的。另外和其相連的虛線(xiàn)箭頭則代表其鄰近單位的平均方向。因此，就此而言，以粗線(xiàn)表示的單位必須朝右側(cè)行進(jìn)。,我們可以利用每個(gè)單位的速度向量求出其方向。把每個(gè)單位的速度向量，換算成單位向量，就可以得出其方位向量。上面收集鄰近單位方向數(shù)據(jù)的過(guò)程，那一行,Vave+=Unitsj.vVelocity;,會(huì)把每個(gè)鄰近單位的速度向量累加在,Vave,中，其做法類(lèi)似于,Pave,累加位置過(guò)程。,這段代碼計(jì)算了每個(gè)單位的對(duì)齊轉(zhuǎn)向力。代碼幾乎和上面聚集差聚集規(guī)則一樣。此處不再處理鄰近單位的平均位置，而是把,Vave,除以鄰近單位數(shù)量,N,，先求出當(dāng)前單位鄰近單位的平均方向。所得結(jié)果儲(chǔ)存在,u,中，并換算成單位向量，則為平均向量。,返,回,就此例而言，轉(zhuǎn)向力是當(dāng)前單位方向，及其鄰近單位平均方向間角度的線(xiàn)性函數(shù)。同意的，只要當(dāng)前單位的方向，和其鄰近單位的平均方向很接近，則只需稍微作調(diào)整。,分隔,分隔意指我們想讓每個(gè)單位彼此間保持最小距離，即使根據(jù)凝聚和對(duì)齊規(guī)則，他們會(huì)試著靠近一點(diǎn)。我們不想讓那些單位撞在一起，或者更糟的是，在某個(gè)巧合地點(diǎn)重合在一起。因此，我們要采用分隔手段，讓每個(gè)單位和其視野內(nèi)的鄰近單位保持某一預(yù)定的最小分隔距離,處理分隔的程序和處理凝聚及對(duì)齊的只有一點(diǎn)不同，因?yàn)榫头指舳裕笏氵m當(dāng)?shù)霓D(zhuǎn)向力校正值時(shí)，我們必須逐一檢視每個(gè)鄰近單位，而不是使用所有鄰近單位的某個(gè)平均值。,返,回,演講完畢，謝謝觀看！,內(nèi)容總結(jié),人工智能。比如說(shuō)：你看到的是一群大雁，它們的飛行是有一定的規(guī)律，而且你完全可以看出來(lái)它們會(huì)排成一字或者人字，不會(huì)是亂糟糟的飛行。1，單位的視野，我們以r為單位的視野半徑，以為視野角度，落在這個(gè)圓弧內(nèi)的所有物體都是可見(jiàn)的。2，避開(kāi)規(guī)則（Avoidance rule），單位不會(huì)被彼此撞上。計(jì)算智能體的位置和目標(biāo)對(duì)象的位置之間的差異，給出x，y和z坐標(biāo)的增量。鄰近單位的平均位置很容易計(jì)算，只要找出鄰近單位后，其平均位置就是其各個(gè)位置的向量總和，再除以總鄰近單位數(shù)?；旧希奂釉贔S.X的轉(zhuǎn)向力是當(dāng)前單位的方向，以及其鄰近單位平均位置向量間的角度的線(xiàn)性函數(shù)，也就是說(shuō)，如果角度大，則轉(zhuǎn)向力也會(huì)相對(duì)較大。如果當(dāng)前單位的方向和鄰近單位的平均位置的方向相距很遠(yuǎn)，我們會(huì)想讓他做大幅度的轉(zhuǎn)彎。如果其方向和鄰近單位平均位置的方向不太遠(yuǎn)，我們只想對(duì)其方向做小范圍的修正。另外和其相連的虛線(xiàn)箭頭則代表其鄰近單位的平均方向,