>>>  創業先鋒 眾人拾柴火焰高  >>>

簡體     傳統

這是一篇老文章, 2013 年初我剛玩 COC 的時候寫給公司內部分享的。由于當時公司還沒有決定開手游項目，但有意向做一款 COC Like 的產品，并希望開發期間保密，所以相關技術文章都沒有公開。

目前，我們的游戲上線，就可以把當初寫的東西陸續貼到 blog 上了。

COC 的地圖有 40x40 格，邊界還有兩格不可以放建筑的格子。所以整個地圖是 44x44 格的。但在做坐標判定時，基于格子是遠遠不夠的。COC 官方版本很可能是基于像素級的精度的，和本文所述方法不一致，所以本文僅提出一種可行的數據結構，

地圖至少要基于網格頂點來建立坐標系統。每個格子由中心點以及四角為頂點，一共有 9 個坐標點。也就是說，最小單位是半個格子。坐標系是 [0,88]

下面的示意圖是一個格子，以及 9 個坐標點：

關于建筑，除了表面上看到的占據格子的面積外，還有實際的尺寸。

比如礦，空間上占 3x3 個格子，但實體則可能是這樣的：

也就是說，對于一個 3x3 的建筑來說，它占據了 9 個坐標點 # 。當步兵攻擊它的時候，需要站在周圍的一圈坐標 + 上。實體不是方的，可以讓兵圍起來的時候大致成一個八邊形，而不是方形。

對于 2x2 的建筑，則是這樣的：

像營地這樣的 5x5 建筑，建筑實際占地和 3x3 一樣，步兵看起來是靠近攻擊的。步兵在攻擊的時候，必須坐標軸對齊毗鄰建筑，但是播放攻擊動畫是朝向建筑中心的。

關于尋路：

COC 不同于 RTS ，它基本上是運動的單位尋路去攻擊靜止建筑。（部隊交火例外，這個先撇開不談）地形在破壞之前，大體上路線其實大體上是固定的。而建筑也有限。加上地圖規模不大，這讓尋路模塊也有了極大的優化空間。

我認為預處理可以極大的簡化計算。

我們可以針對每類建筑設置一張尋路圖。以 3x3 的普通建筑為例：

這里的 0,1,2 只是到建筑的實際距離。我們只需要做一次全地圖填充，就可以寫入地圖上所有坐標點到建筑的最短距離。陸軍在移動時，只需要找到周圍 8 個坐標中距離建筑更近的一個，移動過去即可。如果距離為 0 就可以展開進攻。注意，斜向移動并不會更快。

對于不同攻擊距離的單位，可以分別生成不同的圖表。這樣，弓箭手就會在剛好在射程最遠處就展開進攻了。

關于墻：

墻不是建筑，除了炸彈骷髏，所有兵種都不以墻為尋路目的地。所以墻不需要生成上面的圖（炸彈骷髏的移動邏輯另做）。

墻對于尋路系統來說，只是一個權值很高的障礙（可以跳躍后則忽略）。比如，一個 3x3 建筑圍了墻后該怎么計算呢？（如下圖，我故意留了兩個口）。

展現為坐標點是這樣的。# 表示建筑，X 表示墻，. 表示路。

如果我們認為通過墻的難度是 6 (就是說，拆墻好過走 6 個格子。實際設置的值肯定比 6 大) ，那么按同樣的方法標注前面的圖就好了。

如果在行軍路線上，下一個目標點是墻，那么就先攻擊墻就可以了。

總結一下，其實我們只需要為每類兵種，針對它所偏好攻擊的建筑群生成一張路圖，標記了一個士兵在地圖任何位置所需要做的動作：是向某個方向移動？還是站在原地開始攻擊。那么士兵每到任何一個新坐標，他都可以通過查表 O(1) 時間得到要做的事情。

只有地形破壞后，路圖才需要重新計算。計算的時間復雜度是 O(n) 的，只跟地圖尺寸有關。我的試驗代碼可以在毫秒級完成重算。

ps. COC 應該不是采用這樣的算法這可能和他們采用的地圖數據結構有關，因為它的士兵 AI 有明顯的遲鈍，大約 6 秒才會重算一次。但我認為上面的算法更優不必追究 COC 的原版算法是怎樣的。

對于炸彈人的邏輯，大致應該是尋找附近封閉空間中最近目標，炸毀路徑上的障礙。詳細算法另開一篇。

GameRes游資網 2015-08-23 08:41:50