民初思韻網

加入收藏   設為首頁
選擇語言   簡體中文
你好,請 登陸 或 注冊
首頁 人文思韻 傳奇人物 歷史思潮 時代作品 話題討論 國民思韻 民初捐助 賬戶管理
  搜索  
    人文精神 >>> 創業先鋒 眾人拾柴火焰高
字體    

COC Like 游戲中的尋路算法
COC Like 游戲中的尋路算法
GameRes游資網     阅读简体中文版

這是一篇老文章, 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 的原版算法是怎樣的。

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


2015-08-23 08:41

歡迎訂閱我們的微信公眾賬號!
春秋茶館訂閱號
微信號 season-tea(春秋茶館)
每天分享一篇科技/遊戲/人文類的資訊,點綴生活,啟迪思想,探討古典韻味。
  清末民初歷史人物  民初人物
傳統官僚翰林總統
徐世昌(1855年10月24日-1939年6月5日),字卜五,號菊人,又號水竹邨人、弢齋。祖籍浙江寧波鄞縣。清末民初,曾為北洋政府官僚。1918年,徐世昌獲段祺瑞控制的安....
學貫中西品讀東西文化
林語堂(1895年10月10日-1976年3月26日),中國文學家、發明家。福建省龍溪(現為漳州市平和縣)坂仔鎮人,乳名和樂,名玉堂,後改為語堂。美國哈佛大學比較文學碩士....
資助民初精神網
        回頂部     寫評論

 
評論集
暫無評論!
發表評論歡迎你的評論
昵稱:     登陸  註冊
主頁:  
郵箱:  (僅管理員可見)

驗證:   验证码(不區分大小寫)  
© 2011   民初思韻網-清末民初傳奇時代的發現與復興   版權所有   加入收藏    設為首頁    聯繫我們    1616導航