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