>>>  技術話題—商業文明的嶄新時代  >>>

簡體     傳統

GameRes發布，文/paladin_t，轉載請注明GameRes和作者


追擊、群聚是極常用到的敵人行為模式。靠拢玩家位置的移動叫追擊；群聚指一批敵人集體采用統一的行動，就像一群群沙丁魚一樣。群聚敵人往往配合追擊來對玩家施加壓力，因此本文隱含用追擊配合做群聚示例。

如果群聚行為的敵人沒有對群體內其他敵人的感知能力，將造成一種很奇葩的現象：扎堆。我見過很多游戲可以控制主角兜來兜去讓群聚敵人集中到一堆，或者你不動他們自己就會走成一條直線。


 

這很煩人，玩家會認為敵人非常傻，如果玩家要采取躲避敵人的策略，挑戰性的要素只剩下對走位的決策和移動速度的比拼。更惡心的是往往敵人比你挨著我我挨著你還要親密，甚至全部疊加集中到一個點上。


 

喂，這太蠢了點吧。這是最raw最simple的實現方式，誰都能想出來。


 

敵人始終單純的趨向主角（也許還會做出對主角移動預判的計算，但不在本文討論范疇內），在主角從a點移動到b點的過程中敵人始終保持這樣的趨向性。


 

用彩色曲線對例圖中敵人的移動軌跡做描繪，也許是這個樣子：



 

看到了吧，敵人群體的范圍越來越小了。做為開發者兼玩家，這種prototype級別的做法會給我留下此游戲完成度很低的印象。

物理引擎在現代游戲中已經不是什么稀奇物件了，不管3D游戲還是2D游戲，都能找到物理機制和游戲表達結合的非常好的例子，某些游戲走的更遠，對物理機制利用的更深入，物理就是這種游戲的全部樂趣。如果你的游戲中恰巧有一個可以隨手拿來利用一下的物理引擎，也許你可以用它來防止敵人們過于親密，比如給每個敵人一個比渲染包圍體略大一些的防撞車碰撞體。


 

這看起來就像敵人間互相有了斥力場，酷！大功告成，萬事大吉！

你得承認凡是做游戲鬼點子多的人才不會滿足于把方案思考到能用就好的程度。我不是排斥使用物理引擎，相反我非常喜歡物理機制，我曾給我的首款App定制實現了一個物理引擎，效率良好，運轉穩定，最關鍵的是這個精簡版的物理引擎功能不多不少剛剛好滿足我的需求，完全沒必要用更加高大上的庫。對于防止群聚行為敵人扎堆這件事我不想用物理引擎也是因為：完全沒必要用啊。某些RTS不同兵種間有搭配性玩法，需要不同兵種的密度均衡，如果用物理引擎反而很難做。詢問了幾個同行，似乎不用物理引擎對這事都沒什么轍，沒辦法，又得自己動手了。讓我們來看看如果不使用物理引擎自己處理敵人間的“推搡”是怎樣的情況。


 

如果有兩只敵人，只需要做1次計算讓一只跟另一只保持適當距離就行了；如果有3只敵人，需要做3次這樣的計算；如果有4只，需要算6次；如果有5只呢，要算10次……這種算法的復雜度是O(n(n-1)/2)，可想而知敵人數量多了這將成為CPU的災難。經驗告訴我，復雜度中有高達形如“n乘以n”這樣的因子的算法都是要不得的，需要想辦法優化或做折衷。

思考優化方案從現實切入吧，我們每個人都有在方陣隊伍里齊步走的經歷，左右腳步調的統一依靠“一二一”口號和踏步聲音做同步數據源；在方陣中相對位置的固定不變我們不需要也不可能通過獲取方陣中其他所有人的位置信息做反饋調整，事實上我們只是瞄著視線范圍內與我們臨近的同學來做模糊判定的。先考慮某一只敵人不管別的敵人同學自己單獨行動的行為：


 

這很容易，只需要朝著主角的位置奔去就行了，我們不妨把例圖中優先計算行動的敵人1當成走方陣時的排頭同學，他們只需要走好自己的就行了。

取敵人1和主角位置連線（長度為R的）線段上某一點，（比如不妨定R為線段長度的一半），從主角位置到這一點（以R為半徑）做一個圓，好歹我們可以知道敵人群體的總數量有幾只，把這個圓平均劃分為n份，每一只都朝著相對應的劃分的端點襲去，嗯，也許還得給每只敵人做些移動方向的微調；由于敵人1距主角越來越近，R是越來越小的，這個圓也會越來越向主角收縮，于是我們神奇的達成了敵人的這一套行為：

1. 群體移動趨勢一致統一
2. 群內個體間不會越來越靠近


 

圓只需要劃分一次，某一只敵人只需要知道自己是第幾號就可以計算出速度向量，看，復雜度一下降低到了O(n)，單次計算中的向量計算也銳減。

再引申談一點點，群聚敵人分成若干堆怎樣實現呢，不妨這樣來看，每一堆算做一個聚集群體應用上文算法，再把某一群體看做一個整體，若干個這樣的群體同理應用群聚算法（或其他行為模式）。


 

本文算法代碼可在github獲取，閱讀原文前往github。

網載 2014-07-14 16:12:07