紅色警戒地圖移動問題探究
--------------------------------------------------
玩過RA的應(yīng)該都知道，RA里面移動對象的路徑計算是“瞬間”完成的，基本在0.01秒內(nèi)就可以完成移動路徑的計算并且進(jìn)行移動。但是，如果有一些OI基礎(chǔ)的都知道，單源最短路徑的計算是一個Θ(n^2)的算法，假定有10個步兵要移動，而地圖的大小是100x100的話，計算的時間將是：
10*100*100*100*100=10^10
計算方法是：將地圖視作一個100*100=10000頂點的圖，定點之間的邊定義為“是否相鄰”（懸崖不算）。這樣就得到了上面的公式。
以2GHZ的CPU計算，上面的計算過程將耗費0.5秒，而這還不包括依照兵種差異而修改算法的時間！這樣，對于“50天啟vs50光棱”的效果將耗費2.5秒來計算路徑，這顯然是不可能的。
這一講就來讓大家了解一下RTS計算移動路徑的方法。
-------方法1-------
前面已經(jīng)講過，RTS將地圖抽象為圖結(jié)構(gòu)，這個圖的規(guī)模達(dá)到10000個頂點。顯然用鄰接矩陣是計算不了的了。在RA中存儲地圖使用的是鄰接表——一種節(jié)省內(nèi)存的數(shù)據(jù)結(jié)構(gòu)（注意到RA地圖抽象成的圖非常稀疏）。這就使得RA不得不采用一些適合于稀疏圖的算法。而且，因為地圖規(guī)模的緣故，使得算法的復(fù)雜度必須控制在O(nlog(n))的水平以內(nèi)。
RTS中尋路的并非一些多項式算法，而是啟發(fā)式深搜。通過改變搜索順序，啟發(fā)式深搜可以在很快的時間內(nèi)找到路徑。而且，沒有多少多余的搜索。這樣，在O(nlog(n))時間內(nèi)找到路徑是完全可能的（雖然A*最壞時間效率是指數(shù)時間）
-------方法2-------
我們注意到地圖中的障礙物的面積是比較少的。這樣可以聯(lián)想到將“不可通過部分”設(shè)置成一些多邊形障礙物，這就使得尋路問題稱為計算幾何問題了。這類問題叫ESPO。
假設(shè)地圖規(guī)模是m個多邊形片，k個多邊形障礙物，一共n個頂點在障礙物上。Rohnert給出的算法時間復(fù)雜度是O(knlog(n))，對于一般的地圖已經(jīng)足夠了。這個算法使用的還是dijkstra，假如用配對堆的話效率會更高（不計算了）。與處理過程將在建筑物被摧毀（地圖改變）時進(jìn)行。（或許就可以解釋為什么摧毀建筑物以后游戲會卡一下）。
個人觀點，歡迎拍磚。
紅警2地圖制作心得：
●關(guān)于懸崖
*懸崖的意義：是地圖初學(xué)者向老鳥過渡的重要途徑，一旦掌握懸崖制作，其他方面能更快的融會貫通（本
人的親身體會，但無科學(xué)依據(jù)）
*避免一個誤區(qū)：沒有懸崖的地圖就是低水平的作品。
象官方地圖中的B2，沙丘就是經(jīng)典的反例。
*制作懸崖時，一定要開框架模式，才能保證地形的準(zhǔn)確和專業(yè)
*制作懸崖莫要貪高，一般一兩層就夠了，到了最高處，懸崖會因為游戲地形限制而失去美觀。
●關(guān)于燈光
*一般的新手容易忽略燈光的設(shè)置，其實合適的燈光設(shè)置能讓地圖增色不少。
*正常燈光設(shè)置：根據(jù)自己的需要任意設(shè)置，但要注意，如果想做夜晚的話，不能太黑，不然會影響游戲者
的操作（亮度一般比正常偏暗就可以，個人覺得紅警里紅黃不如藍(lán)綠來的賞心悅目）。
*閃電風(fēng)暴場景的燈光：這個更容易被忽略。根據(jù)傳統(tǒng)，燈光參數(shù)應(yīng)該是類似夜晚的暗效果（當(dāng)然，如果是
YY或者惡搞地圖就無所謂了……）
●關(guān)于資源
*無論是正規(guī)還是娛樂地圖，資源的分布都應(yīng)該是較為平衡的（少數(shù)高強度YY地圖除外）。
這個平衡不僅僅是數(shù)量上的平衡，還有[礦位]的平衡。
由于游戲中的礦場都一同一個面向（東南），因此東南角度玩家倒礦就要多繞半個礦場的路程。
所以西北角的礦應(yīng)該離出生地較遠(yuǎn)，才能盡量保證平衡（即使是官方地圖也達(dá)不到絕對平衡）
東北 西北等其他位置同理……
典型例子：B2
*如果你做的地圖偏重戰(zhàn)術(shù)性競技性，那么，油井不能擺多（如果多的話，應(yīng)該盡量分散開）
紅警的競技性在于經(jīng)濟和兵力的協(xié)調(diào)高效發(fā)展，而不是給足經(jīng)濟比刷兵。
●關(guān)于AI
*由于目前對戰(zhàn)很少使用自制地圖，因此競技地圖的市場前景不好，所以一般做的地圖都是偏向娛樂
而娛樂地圖就要考慮怎么樣讓完家跟電腦玩的高興
*雖然玩家都有虐電腦的情結(jié)，但絕對不希望面對的是幾個智障。因此，AI需要能起完全科技。而地圖中最
容易限制AI發(fā)展的，就是地形空間
電腦終究是電腦，在遇到狹窄的地形時不會像我們一樣一字排開布局，它能做的，就只有發(fā)呆……
所以，千萬記住，給AI多一點空間，也許他就能多打你幾拳，和這樣的電腦玩，才有意思嘛。
●關(guān)于地圖美化
*沒什么多說的，因為我也不是美工高手，但有一點：不要一味貪圖華麗，使得整個地圖刷滿建筑樹木，一
旦修飾物太多，容易消耗更多的系統(tǒng)資源，機器不好的玩家甚至還會受罪……
*根據(jù)地圖場景添加些音效觸發(fā)還是不錯的，至少讓人覺得你挺專業(yè)的，想的挺周到……
●關(guān)于觸發(fā)
*還是避免一個誤區(qū)：有觸發(fā)的地圖是高水平的地圖或者會做觸發(fā)的人都是高水平者
誠然，觸發(fā)是編輯器里高級模式下的工具，但以此衡量水平欠妥。
地圖制作的水平，主要是作者對地圖的理解，制作的意識，技術(shù)上的差異卻是次要的
*不過，話說回來，觸發(fā)確實也是一個能讓地圖增色不少的強有力工具。
比如上文說到的音效觸發(fā)，還有文本觸發(fā)，畫面的觸發(fā)（有張地圖用此制造了晝夜更替的效果）
*觸發(fā)能豐富地圖的內(nèi)涵：例如寶箱（里面的東西可以自定義，有些地圖所謂的“藏了枚核彈”就是運用這
個觸發(fā)），例如莫名其妙的閃電風(fēng)暴打擊或者核彈打擊，又如開局贈送一些單位建筑什么的……很多個性化
的地圖特效，往往都是借助觸發(fā)完成的�？梢哉f，觸發(fā)，是地圖制作中一個蘊涵了巨大價值的金礦！
●關(guān)于INI
*說到個性化特效，當(dāng)然不能不說INI的修改
修改地圖INI同樣也是地圖制作中的高級課題，需要作者對游戲程序規(guī)則的熟悉
*會做MOD的人，一定會修改地圖內(nèi)置INI，但反之卻不是。修改INI只是制作做MOD的一個子集
修改地圖INI只需要改每個小節(jié)下一個或某幾個鍵或鍵值，而不需要再去考慮其他鍵，因此是方便高效的
*修改INI可以打破傳統(tǒng)：游戲全局設(shè)置上可以修改（建造速度，維修費用，買賣規(guī)則等等）；單位屬性可以
修改（血，裝甲，武器，甚至圖象）；建筑可以修改（血，裝甲，武器，特性等等）……
*不僅如此，還能修改AI，使得電腦瘋狂出兵或者嚴(yán)重智障……
●總之，
地圖制作雖然只是紅警MOD的一個分支，但可以研究的還有很多
紅色警戒雖然已經(jīng)是一款夕陽游戲，但值得我們?nèi)ネ诰虻倪�有更多
做MOD吃不消？？那就從做地圖開始吧……
最后，我也希望吧里有良好的制圖氛圍，有新人出作品，應(yīng)該以鼓勵贊揚為主，絕對不該出現(xiàn)嘲諷譏笑，維
持紅警的生命力，往往就在我們的一言一行中！
喜歡 
頂
難過
囧
圍觀
無聊
