红色警戒地图移动问题探究
--------------------------------------------------
玩过RA的应该都知道，RA里面移动对象的路径计算是“瞬间”完成的，基本在0.01秒内就可以完成移动路径的计算并且进行移动。但是，如果有一些OI基础的都知道，单源最短路径的计算是一个Θ(n^2)的算法，假定有10个步兵要移动，而地图的大小是100x100的话，计算的时间将是：
10*100*100*100*100=10^10
计算方法是：将地图视作一个100*100=10000顶点的图，定点之间的边定义为“是否相邻”（悬崖不算）。这样就得到了上面的公式。
以2GHZ的CPU计算，上面的计算过程将耗费0.5秒，而这还不包括依照兵种差异而修改算法的时间！这样，对于“50天启vs50光棱”的效果将耗费2.5秒来计算路径，这显然是不可能的。
这一讲就来让大家了解一下RTS计算移动路径的方法。
-------方法1-------
前面已经讲过，RTS将地图抽象为图结构，这个图的规模达到10000个顶点。显然用邻接矩阵是计算不了的了。在RA中存储地图使用的是邻接表——一种节省内存的数据结构（注意到RA地图抽象成的图非常稀疏）。这就使得RA不得不采用一些适合于稀疏图的算法。而且，因为地图规模的缘故，使得算法的复杂度必须控制在O(nlog(n))的水平以内。
RTS中寻路的并非一些多项式算法，而是启发式深搜。通过改变搜索顺序，启发式深搜可以在很快的时间内找到路径。而且，没有多少多余的搜索。这样，在O(nlog(n))时间内找到路径是完全可能的（虽然A*最坏时间效率是指数时间）
-------方法2-------
我们注意到地图中的障碍物的面积是比较少的。这样可以联想到将“不可通过部分”设置成一些多边形障碍物，这就使得寻路问题称为计算几何问题了。这类问题叫ESPO。
假设地图规模是m个多边形片，k个多边形障碍物，一共n个顶点在障碍物上。Rohnert给出的算法时间复杂度是O(knlog(n))，对于一般的地图已经足够了。这个算法使用的还是dijkstra，假如用配对堆的话效率会更高（不计算了）。与处理过程将在建筑物被摧毁（地图改变）时进行。（或许就可以解释为什么摧毁建筑物以后游戏会卡一下）。
个人观点，欢迎拍砖。
红警2地图制作心得：
●关于悬崖
*悬崖的意义：是地图初学者向老鸟过渡的重要途径，一旦掌握悬崖制作，其他方面能更快的融会贯通（本
人的亲身体会，但无科学依据）
*避免一个误区：没有悬崖的地图就是低水平的作品。
象官方地图中的B2，沙丘就是经典的反例。
*制作悬崖时，一定要开框架模式，才能保证地形的准确和专业
*制作悬崖莫要贪高，一般一两层就够了，到了最高处，悬崖会因为游戏地形限制而失去美观。
●关于灯光
*一般的新手容易忽略灯光的设置，其实合适的灯光设置能让地图增色不少。
*正常灯光设置：根据自己的需要任意设置，但要注意，如果想做夜晚的话，不能太黑，不然会影响游戏者
的操作（亮度一般比正常偏暗就可以，个人觉得红警里红黄不如蓝绿来的赏心悦目）。
*闪电风暴场景的灯光：这个更容易被忽略。根据传统，灯光参数应该是类似夜晚的暗效果（当然，如果是
YY或者恶搞地图就无所谓了……）
●关于资源
*无论是正规还是娱乐地图，资源的分布都应该是较为平衡的（少数高强度YY地图除外）。
这个平衡不仅仅是数量上的平衡，还有[矿位]的平衡。
由于游戏中的矿场都一同一个面向（东南），因此东南角度玩家倒矿就要多绕半个矿场的路程。
所以西北角的矿应该离出生地较远，才能尽量保证平衡（即使是官方地图也达不到绝对平衡）
东北 西北等其他位置同理……
典型例子：B2
*如果你做的地图偏重战术性竞技性，那么，油井不能摆多（如果多的话，应该尽量分散开）
红警的竞技性在于经济和兵力的协调高效发展，而不是给足经济比刷兵。
●关于AI
*由于目前对战很少使用自制地图，因此竞技地图的市场前景不好，所以一般做的地图都是偏向娱乐
而娱乐地图就要考虑怎么样让完家跟电脑玩的高兴
*虽然玩家都有虐电脑的情结，但绝对不希望面对的是几个智障。因此，AI需要能起完全科技。而地图中最
容易限制AI发展的，就是地形空间
电脑终究是电脑，在遇到狭窄的地形时不会像我们一样一字排开布局，它能做的，就只有发呆……
所以，千万记住，给AI多一点空间，也许他就能多打你几拳，和这样的电脑玩，才有意思嘛。
●关于地图美化
*没什么多说的，因为我也不是美工高手，但有一点：不要一味贪图华丽，使得整个地图刷满建筑树木，一
旦修饰物太多，容易消耗更多的系统资源，机器不好的玩家甚至还会受罪……
*根据地图场景添加些音效触发还是不错的，至少让人觉得你挺专业的，想的挺周到……
●关于触发
*还是避免一个误区：有触发的地图是高水平的地图或者会做触发的人都是高水平者
诚然，触发是编辑器里高级模式下的工具，但以此衡量水平欠妥。
地图制作的水平，主要是作者对地图的理解，制作的意识，技术上的差异却是次要的
*不过，话说回来，触发确实也是一个能让地图增色不少的强有力工具。
比如上文说到的音效触发，还有文本触发，画面的触发（有张地图用此制造了昼夜更替的效果）
*触发能丰富地图的内涵：例如宝箱（里面的东西可以自定义，有些地图所谓的“藏了枚核弹”就是运用这
个触发），例如莫名其妙的闪电风暴打击或者核弹打击，又如开局赠送一些单位建筑什么的……很多个性化
的地图特效，往往都是借助触发完成的。可以说，触发，是地图制作中一个蕴涵了巨大价值的金矿！
●关于INI
*说到个性化特效，当然不能不说INI的修改
修改地图INI同样也是地图制作中的高级课题，需要作者对游戏程序规则的熟悉
*会做MOD的人，一定会修改地图内置INI，但反之却不是。修改INI只是制作做MOD的一个子集
修改地图INI只需要改每个小节下一个或某几个键或键值，而不需要再去考虑其他键，因此是方便高效的
*修改INI可以打破传统：游戏全局设置上可以修改（建造速度，维修费用，买卖规则等等）；单位属性可以
修改（血，装甲，武器，甚至图象）；建筑可以修改（血，装甲，武器，特性等等）……
*不仅如此，还能修改AI，使得电脑疯狂出兵或者严重智障……
●总之，
地图制作虽然只是红警MOD的一个分支，但可以研究的还有很多
红色警戒虽然已经是一款夕阳游戏，但值得我们去挖掘的还有更多
做MOD吃不消？？那就从做地图开始吧……
最后，我也希望吧里有良好的制图氛围，有新人出作品，应该以鼓励赞扬为主，绝对不该出现嘲讽讥笑，维
持红警的生命力，往往就在我们的一言一行中！
喜欢 
顶
难过
囧
围观
无聊
