人工智能小組成員：xx人工智能人工智能人工智能1游戲中的人工智能——群聚游戲中的人工智能——群聚2什么是群聚呢？群聚，就是多個非玩家角色一起行動，而不是個別行動。比如說：你看到的是一群大雁，它們的飛行是有一定的規律，而且你完全可以看出來它們會排成一字或者人字，不會是亂糟糟的飛行。那么，我們在游戲中，諸如巡邏小隊之類的移動又是什么樣的呢？1987年，CraigReynolds發表了一篇名為《Flocks，HerdsandSchools：ADistributedBehavialModel》的論文，在這篇論文中，他提出了基本的群聚算法模型，甚至可以這樣說，后續的一系列群聚算法都有這篇論文的身影。那么我們來看看CraigReynolds提到的boids——類鳥群的模擬群體。在這種類鳥群里面，是沒有領導核心，它們都是跟著群體在走，而這個群體似乎是自己有自己的想法。什么是群聚呢？群聚，就是多個非玩家角色一起行動，而不是個別行3Reynolds基本群聚算法核心群體行為的核心是基本的群聚算法。“單位”（unit）指代組成群體的個別實體。凝聚：每個單位都往其臨近單位的平均位置行動。對齊：每個單位行動時，都要把自己對齊在其臨近單位的平均方向上。分隔：每個單位行動時，要避免撞上其臨近單位。Reynolds基本群聚算法核心群體行為的核心是基本的群4Reynolds基本群聚算法是沒有領導核心的；就某種意義而言，它們都跟著整個群體移動。每個單位都必須有行進的能力；每個單位都必須知道其局部周圍的情況，即鄰近單位位置、方向以及群體中與自身最靠近的單位之間的距離。在仿真物理環境中可以對仿真中的單位施加轉向力使其改變方向；在磚塊環境中可以采用視線方法讓單位改變方向或朝特定點移動。Reynolds基本群聚算法是沒有領導核心的；就5為了分析我們這個群聚系統，我們需要理解一些基本的概念：1，

單位的視野，我們以r為單位的視野半徑，以θ為視野角度，落在這個圓弧內的所有物體都是可見的。2，

避開規則（Avoidancerule），單位不會被彼此撞上。3，

凝聚規則，單位離得太遠就應該靠近一點，這個規則和避開規則合在一起，從而形成了群聚。為了分析我們這個群聚系統，我們需要理解一些基本的概念：6磚塊環境中的移動模式非確定性方法（加入隨機因素）：

1、初始化路徑數組，移動數組

2、用Bresenham線段算法計算不同的移動模式

3、將模式標準化

4、設定前進速率，按照設定好的移動模式移動，當到達線段的端點時檢查移動數組，以確定移動方向。磚塊環境中的移動模式非確定性方法（加入隨機因素）：7到目前為止，我們討論的群聚規給大家留下了深刻印象。然而，像這樣的群聚行為如果在游戲中，這些單位以群體形態移動式，還能避免撞上游戲世界里的物體，那就更實用了。到目前為止，我們討論的群聚規給大家留下了深刻印象。然而，像這8實際上加入避開障礙物的行為其實相當簡單，我們所要做的就是提供某種機制給那些單位使用，讓他們看到前方，再施加適當的轉向力，使其避開路徑中的障礙物。首先，我們運算向量a，這只是該單位和障礙物位置間的差值，接著，取a和v的內積，將a投射到v上，由此可得向量p，把向量p減去向量a，可得向量b，現在要測試v是否和圓的某處相交，得測試兩種情況。1.p的數值必須小于v的數值。2.b的數值必須小于該障礙物的半徑r。如果兩者都是如此，則需要校正轉向力，否則，該單位可繼續沿當前方向前進。實際上加入避開障礙物的行為其實相當簡單，我們所要做的就是提供9追隨領頭者對基本群聚算法的修改不必只限于避開障礙物。因為來自于各種規則的轉向力都在同一變量中累加，然后一次施加，以控制該單位的方向，所以，我們還可以在考慮過的規則之上在疊加其他許多有效的規則。其中一條有趣的外加規則，就是跟隨領頭者規則。如前所述，我們討論的群聚規則是沒有領頭者的，然而，如果我們把基本群聚算法和某些領頭者AI結合起來，就可以在游戲中使用群聚功能時，開啟許多新的可能效果。如果我們在其中加入領頭者，就能讓群體的移動更有目的性，或者看起來比較有智能。追隨領頭者對基本群聚算法的修改不必只限于避開障礙物。因為來自10我們來看看一個實際例子：我們來看看一個實際例子：11游戲中的人工智能群聚12游戲中的人工智能群聚13另一種群聚方法——簡化集群技術Reynolds的群聚算法已經被很好地證明了，而且在生成若干組智能體的逼真動作效果非常好。但是，該算法在計算上的開銷大，尤其是在有大量智能體或者有復雜場景需要探測的時候。因此，他們有時候不適合實時的應用程序，比如電視游戲。所以我們有必要對集群技術進一步的進行簡化。另一種群聚方法——簡化集群技術Reynolds的群聚算法已經14群聚算法在模擬少量或中等數量的生物的自然行為時是完美的，尤其當這些生物的運動（而不是生物和生物之間的影響、以及生物和場景之間的互動）是主要的關注焦點的游戲中（例如任天堂的Pikmin）。但是，隨著生物個數的增加，傳統的群聚算法開銷越來越大。在群聚中每個智能體必須檢查其他所有智能體以確定是否因距離太近而產生影響，在這種情況下，如果存在n個智能體的場景，需要計算1/2(n2)次獨立的距離計算（給出中間的結果儲存在交互的數組里）。那么分離規則，隊列規則和聚合規則必須對每個智能體計算它附近的每個智能體。另一方面，因為影響是相互的，所以保存中間結果可以使計算量減半。群聚算法在模擬少量或中等數量的生物的自然行為時是完美的，尤其15那么如何對集群技術進行簡化呢？以下將對如何對集群技術進行簡化給出兩點方法：1.從群體初始化方面入手。2.從群體運動方面入手。那么如何對集群技術進行簡化呢？以下將對如何對集群技術進行簡化16參考資料：《人工智能游戲編程真言--清華大學出版社》《游戲開發中的人工智能--東南大學出版社》《游戲設計概論—清華大學出版社》參考網站：/view/df809645be1e650e52ea998d.html/nightelve/article/details/8982647參考資料：17初始化初始化智能體最簡單的方法就是把它們從幕后搬出來。讓集群智能體從天花板上落到玩家頭上，讓它們從墻上漩渦式地鉆出來，或者大群智能體生物從深谷裂口中瀑布般地涌出來（最好是在玩家占領的地盤上）都是最大限度利用集群生物出場的方法。集群生物也可以用“爆炸”的方式進入場景的某個區域，當某個容器被破壞（如籠子）或者被打開（如棺材）。返回初始化初始化智能體最簡單的方法就是把它們從幕后搬出來。返回18運動對每一個活動的智能體保存其當前的位置，根據其速度和運動方向更新x，z坐標，并且根據重力增加下落速度時修改其y坐標。計算智能體的位置和目標對象的位置之間的差異，給出x，y和z坐標的增量。再算出從目標對象到智能體的相對夾角（angle）（atan(dz,dx)-agent->yrot）。如果智能體是逃離目標對象（因為它的定時器timer大于某個特定值）,angle取負值。如果玩家在距離智能體某個范圍之內（用適當的距離檢查，或者用簡單的盒式沖突檢測來節省時間），就認為玩家受到傷害。運動對每一個活動的智能體保存其當前的位置，根據其速度和運動方19

如果智能體不是下落的，那么它的操縱方式和運動方向根據它在內層區域或外層區域分別按如下進行修正：外層區域：如果未到速度的最大值就增加智能體速度。每個智能體的最大速度應該不同。如果智能體的運動方向大致是正確的，給這個智能體的y-rotation一個小小的擾動否則就馬上改變y-rotation，指向正確方向。內層區域：按照智能體的速度改變它的 y-rotation，并且按照它的angle改變它的速度。這些改變背后方程組的本質確定了集群生物在目標對象周圍運動的形式。返回 如果智能體不是下落的，那么它的操縱方式和運動方向根據它在內20Bresenham直線算法Bresenham直線算法是用來描繪由兩點所決定的直線的算法，它會算出一條線段在n維光柵上最接近的點。這個算法只會用到較為快速的整數加法、減法和位元移位，常用于繪制電腦畫面中的直線。是計算機圖形學中最先發展出來的算法。Bresenham直線算法Bresenham直線算法是用來描21返回返回22凝聚凝聚意指我們想讓所有單位都待在同一群體中，我們不要每個單位和群體分開，各走走的路。為了滿足這項規則，每個單位都應該朝其鄰近單位之平均位置前進。鄰近單位的平均位置很容易計算，只要找出鄰近單位后，其平均位置就是其各個位置的向量總和，再除以總鄰近單位數。Pave+=units[j].vPosition;這一行將所有鄰近單位的位置向量相加。Pave和vPosition是Vectort類的變量，此overloadedoperator（重載運算符）會替我們做向量加法。DoUnitAI（）找出鄰近單位并收集信息后，就可以使用群聚規則了。此段程序第一件事是檢查鄰近單位數量是否大于0.如果是，我們就能繼續計算鄰近單位的平均位置。做法是以所有鄰近單位位置的向量總和Pave除以鄰近單位數量N。最后一行就是實際計算滿足凝聚規則的轉向力。凝聚凝聚意指我們想讓所有單位都待在同一群體中，我們不要每個單23凝聚基本上，累加在FS.X的轉向力是當前單位的方向，以及其鄰近單位平均位置向量間的角度的線性函數，也就是說，如果角度大，則轉向力也會相對較大；如果角度小，則轉向力也會相對較小。這正是我們想要的。如果當前單位的方向和鄰近單位的平均位置的方向相距很遠，我們會想讓他做大幅度的轉彎。如果其方向和鄰近單位平均位置的方向不太遠，我們只想對其方向做小范圍的修正。返回凝聚基本上，累加在FS.X的轉向力是當前單位的方向，以及其鄰24對齊對齊意指我們想讓群聚中的所有單位都大致朝相同方向前進。為了滿足這條規則，每個單位都應該在行進時，試著以等同其鄰近單位平均方向的方向來前進。中間以粗線表示單位是沿著和其相連的粗箭頭方向進行的。另外和其相連的虛線箭頭則代表其鄰近單位的平均方向。因此，就此而言，以粗線表示的單位必須朝右側行進。對齊對齊意指我們想讓群聚中的所有單位都大致朝相同方向前進。為25我們可以利用每個單位的速度向量求出其方向。把每個單位的速度向量，換算成單位向量，就可以得出其方位向量。上面收集鄰近單位方向數據的過程，那一行Vave+=Units[j].vVelocity;會把每個鄰近單位的速度向量累加在Vave中，其做法類似于Pave累加位置過程。這段代碼計算了每個單位的對齊轉向力。代碼幾乎和上面聚集差聚集規則一樣。此處不再處理鄰近單位的平均位置，而是把Vave除以鄰近單位數量N，先求出當前單位鄰近單位的平均方向。所得結果儲存在u中，并換算成單位向量，則為平均向量。返回就此例而言，轉向力是當前單位方向，及其鄰近單位平均方向間角度的線性函數。同意的，只要當前單位的方向，和其鄰近單位的平均方向很接近，則只需稍微作調整。我們可以利用每個單位的速度向量求出其方向。把每個單位的速度向26分隔分隔意指我們想讓每個單位彼此間保持最小距離，即使根據凝聚和對齊規則，他們會試著靠近一點。我們不想讓那些單位撞在一起，或者更糟的是，在某個巧合地點重合在一起。因此，我們要采用分隔手段，讓每個單位和其視野內的鄰近單位保持某一預定的最小分隔距離處理分隔的程序和處理凝聚及對齊的只有一點不同，因為就分隔而言，求算適當的轉向力校正值時，我們必須逐一檢視每個鄰近單位，而不是使用所有鄰近單位的某個平均值。返回分隔分隔意指我們想讓每個單位彼此間保持最小距離，即使根據凝聚27人工智能小組成員：xx人工智能人工智能人工智能28游戲中的人工智能——群聚游戲中的人工智能——群聚29什么是群聚呢？群聚，就是多個非玩家角色一起行動，而不是個別行動。比如說：你看到的是一群大雁，它們的飛行是有一定的規律，而且你完全可以看出來它們會排成一字或者人字，不會是亂糟糟的飛行。那么，我們在游戲中，諸如巡邏小隊之類的移動又是什么樣的呢？1987年，CraigReynolds發表了一篇名為《Flocks，HerdsandSchools：ADistributedBehavialModel》的論文，在這篇論文中，他提出了基本的群聚算法模型，甚至可以這樣說，后續的一系列群聚算法都有這篇論文的身影。那么我們來看看CraigReynolds提到的boids——類鳥群的模擬群體。在這種類鳥群里面，是沒有領導核心，它們都是跟著群體在走，而這個群體似乎是自己有自己的想法。什么是群聚呢？群聚，就是多個非玩家角色一起行動，而不是個別行30Reynolds基本群聚算法核心群體行為的核心是基本的群聚算法。“單位”（unit）指代組成群體的個別實體。凝聚：每個單位都往其臨近單位的平均位置行動。對齊：每個單位行動時，都要把自己對齊在其臨近單位的平均方向上。分隔：每個單位行動時，要避免撞上其臨近單位。Reynolds基本群聚算法核心群體行為的核心是基本的群31Reynolds基本群聚算法是沒有領導核心的；就某種意義而言，它們都跟著整個群體移動。每個單位都必須有行進的能力；每個單位都必須知道其局部周圍的情況，即鄰近單位位置、方向以及群體中與自身最靠近的單位之間的距離。在仿真物理環境中可以對仿真中的單位施加轉向力使其改變方向；在磚塊環境中可以采用視線方法讓單位改變方向或朝特定點移動。Reynolds基本群聚算法是沒有領導核心的；就32為了分析我們這個群聚系統，我們需要理解一些基本的概念：1，

單位的視野，我們以r為單位的視野半徑，以θ為視野角度，落在這個圓弧內的所有物體都是可見的。2，

避開規則（Avoidancerule），單位不會被彼此撞上。3，

凝聚規則，單位離得太遠就應該靠近一點，這個規則和避開規則合在一起，從而形成了群聚。為了分析我們這個群聚系統，我們需要理解一些基本的概念：33磚塊環境中的移動模式非確定性方法（加入隨機因素）：

1、初始化路徑數組，移動數組

2、用Bresenham線段算法計算不同的移動模式

3、將模式標準化

4、設定前進速率，按照設定好的移動模式移動，當到達線段的端點時檢查移動數組，以確定移動方向。磚塊環境中的移動模式非確定性方法（加入隨機因素）：34到目前為止，我們討論的群聚規給大家留下了深刻印象。然而，像這樣的群聚行為如果在游戲中，這些單位以群體形態移動式，還能避免撞上游戲世界里的物體，那就更實用了。到目前為止，我們討論的群聚規給大家留下了深刻印象。然而，像這35實際上加入避開障礙物的行為其實相當簡單，我們所要做的就是提供某種機制給那些單位使用，讓他們看到前方，再施加適當的轉向力，使其避開路徑中的障礙物。首先，我們運算向量a，這只是該單位和障礙物位置間的差值，接著，取a和v的內積，將a投射到v上，由此可得向量p，把向量p減去向量a，可得向量b，現在要測試v是否和圓的某處相交，得測試兩種情況。1.p的數值必須小于v的數值。2.b的數值必須小于該障礙物的半徑r。如果兩者都是如此，則需要校正轉向力，否則，該單位可繼續沿當前方向前進。實際上加入避開障礙物的行為其實相當簡單，我們所要做的就是提供36追隨領頭者對基本群聚算法的修改不必只限于避開障礙物。因為來自于各種規則的轉向力都在同一變量中累加，然后一次施加，以控制該單位的方向，所以，我們還可以在考慮過的規則之上在疊加其他許多有效的規則。其中一條有趣的外加規則，就是跟隨領頭者規則。如前所述，我們討論的群聚規則是沒有領頭者的，然而，如果我們把基本群聚算法和某些領頭者AI結合起來，就可以在游戲中使用群聚功能時，開啟許多新的可能效果。如果我們在其中加入領頭者，就能讓群體的移動更有目的性，或者看起來比較有智能。追隨領頭者對基本群聚算法的修改不必只限于避開障礙物。因為來自37我們來看看一個實際例子：我們來看看一個實際例子：38游戲中的人工智能群聚39游戲中的人工智能群聚40另一種群聚方法——簡化集群技術Reynolds的群聚算法已經被很好地證明了，而且在生成若干組智能體的逼真動作效果非常好。但是，該算法在計算上的開銷大，尤其是在有大量智能體或者有復雜場景需要探測的時候。因此，他們有時候不適合實時的應用程序，比如電視游戲。所以我們有必要對集群技術進一步的進行簡化。另一種群聚方法——簡化集群技術Reynolds的群聚算法已經41群聚算法在模擬少量或中等數量的生物的自然行為時是完美的，尤其當這些生物的運動（而不是生物和生物之間的影響、以及生物和場景之間的互動）是主要的關注焦點的游戲中（例如任天堂的Pikmin）。但是，隨著生物個數的增加，傳統的群聚算法開銷越來越大。在群聚中每個智能體必須檢查其他所有智能體以確定是否因距離太近而產生影響，在這種情況下，如果存在n個智能體的場景，需要計算1/2(n2)次獨立的距離計算（給出中間的結果儲存在交互的數組里）。那么分離規則，隊列規則和聚合規則必須對每個智能體計算它附近的每個智能體。另一方面，因為影響是相互的，所以保存中間結果可以使計算量減半。群聚算法在模擬少量或中等數量的生物的自然行為時是完美的，尤其42那么如何對集群技術進行簡化呢？以下將對如何對集群技術進行簡化給出兩點方法：1.從群體初始化方面入手。2.從群體運動方面入手。那么如何對集群技術進行簡化呢？以下將對如何對集群技術進行簡化43參考資料：《人工智能游戲編程真言--清華大學出版社》《游戲開發中的人工智能--東南大學出版社》《游戲設計概論—清華大學出版社》參考網站：/view/df809645be1e650e52ea998d.html/nightelve/article/details/8982647參考資料：44初始化初始化智能體最簡單的方法就是把它們從幕后搬出來。讓集群智能體從天花板上落到玩家頭上，讓它們從墻上漩渦式地鉆出來，或者大群智能體生物從深谷裂口中瀑布般地涌出來（最好是在玩家占領的地盤上）都是最大限度利用集群生物出場的方法。集群生物也可以用“爆炸”的方式進入場景的某個區域，當某個容器被破壞（如籠子）或者被打開（如棺材）。返回初始化初始化智能體最簡單的方法就是把它們從幕后搬出來。返回45運動對每一個活動的智能體保存其當前的位置，根據其速度和運動方向更新x，z坐標，并且根據重力增加下落速度時修改其y坐標。計算智能體的位置和目標對象的位置之間的差異，給出x，y和z坐標的增量。再算出從目標對象到智能體的相對夾角（angle）（atan(dz,dx)-agent->yrot）。如果智能體是逃離目標對象（因為它的定時器timer大于某個特定值）,angle取負值。如果玩家在距離智能體某個范圍之內（用適當的距離檢查，或者用簡單的盒式沖突檢測來節省時間），就認為玩家受到傷害。運動對每一個活動的智能體保存其當前的位置，根據其速度和運動方46

如果智能體不是下落的，那么它的操縱方式和運動方向根據它在內層區域或外層區域分別按如下進行修正：外層區域：如果未到速度的最大值就增加智能體速度。每個智能體的最大速度應該不同。如果智能體的運動方向大致是正確的，給這個智能體的y-rotation一個小小的擾動否則就馬上改變y-rotation，指向正確方向。內層區域：按照智能體的速度改變它的 y-rotation，并且按照它的angle改變它的速度。這些改變背后方程組的本質確定了集群生物在目標對象周圍運動的形式。返回 如果智能體不是下落的，那么它的操縱方式和運動方向根據它在內47Bresenham直線算法Bresenham直線算法是用來描繪由兩點所決定的直線的算法，它會算出一條線段在n維光柵上最接近的點。這個算法只會用到較為快速的整數加法、減法和位元移位，常用于繪制電腦畫面中的直線。是計算機圖形學中最先發展出來的算法。Bresenham直線算法Bresenham直線算法是用來描48返回返回49凝聚凝聚意指我們想讓所有單位都待在同一群體中，我們不要每個單位和群體分開，各走走的路。為了滿足這項規則，每個單位都應該朝其鄰近單位之平均位置前進。鄰近單位的平均位置很容易計算，只要找出鄰近單位后，其平均位置就是其各個位置的向量總和，再除以總鄰近單位數。Pave+=units[j].vPosition;這一行將所有鄰近單位的位置向量相加。Pave和vPosition是Vectort類的變量，此overloadedoperator（重載運算符）會替我們做向量加法。DoUnitAI（）找出鄰近單位并收集信息后，就可以使用群聚規則了。此段程序第一件事是檢查鄰近單位數量是否大于0.如果是，我們就能繼續計算鄰近單位的平均位置。做法是以所有鄰近單位位置的向量總和Pave除以鄰近單位數量N。最后一行就是實際計算滿足凝聚規則的轉向力。凝聚凝聚意指我們想讓所有單位都待在同一群