红警2地图移动问题和制作心得
2012-12-13 15:47:05 作者：霸气侧漏
《红色警戒2共和国之辉》是即时战略游戏《红色警戒2》的一款较早期的mod。然而，必须强调指出《共和国之辉》只是国内某个人玩家或者说mod爱好者的一款修改之作，并非westwood公司出的官方资料片。
>>红色警戒2攻略大全<<
红色警戒地图移动问题探究
玩过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攻略大全<<
红警2地图制作心得：
●关于悬崖
*悬崖的意义：是地图初学者向老鸟过渡的重要途径，一旦掌握悬崖制作，其他方面能更快的融会贯通（本
人的亲身体会，但无科学依据）
*避免一个误区：没有悬崖的地图就是低水平的作品。象官方地图中的B2，沙丘就是经典的反例。
*制作悬崖时，一定要开框架模式，才能保证地形的准确和专业
*制作悬崖莫要贪高，一般一两层就够了，到了最高处，悬崖会因为游戏地形限制而失去美观。
●关于灯光
*一般的新手容易忽略灯光的设置，其实合适的灯光设置能让地图增色不少。
*正常灯光设置：根据自己的需要任意设置，但要注意，如果想做夜晚的话，不能太黑，不然会影响游戏者的操作（亮度一般比正常偏暗就可以，个人觉得红警里红黄不如蓝绿来的赏心悦目）。
*闪电风暴场景的灯光：这个更容易被忽略。根据传统，灯光参数应该是类似夜晚的暗效果
●关于资源
*无论是正规还是娱乐地图，资源的分布都应该是较为平衡的（少数高强度YY地图除外）。这个平衡不仅仅是数量上的平衡，还有[矿位]的平衡。由于游戏中的矿场都一同一个面向（东南），因此东南角度玩家倒矿就要多绕半个矿场的路程。所以西北角的矿应该离出生地较远，才能尽量保证平衡（即使是官方地图也达不到绝对平衡）东北 西北等其他位置同理……
典型例子：B2
*如果你做的地图偏重战术性竞技性，那么，油井不能摆多（如果多的话，应该尽量分散开）
红警的竞技性在于经济和兵力的协调高效发展，而不是给足经济比刷兵。
●关于AI
*由于目前对战很少使用自制地图，因此竞技地图的市场前景不好，所以一般做的地图都是偏向娱乐而娱乐地图就要考虑怎么样让完家跟电脑玩的高兴
*虽然玩家都有虐电脑的情结，但绝对不希望面对的是几个智障。因此，AI需要能起完全科技。而地图中最容易限制AI发展的，就是地形空间电脑终究是电脑，在遇到狭窄的地形时不会像我们一样一字排开布局，它能做的，就只有发呆……所以，千万记住，给AI多一点空间，也许他就能多打你几拳，和这样的电脑玩，才有意思嘛。
●关于地图美化
*没什么多说的，因为我也不是美工高手，但有一点：不要一味贪图华丽，使得整个地图刷满建筑树木，一旦修饰物太多，容易消耗更多的系统资源，机器不好的玩家甚至还会受罪……
*根据地图场景添加些音效触发还是不错的，至少让人觉得你挺专业的，想的挺周到……
●关于触发
*还是避免一个误区：有触发的地图是高水平的地图或者会做触发的人都是高水平者诚然，触发是编辑器里高级模式下的工具，但以此衡量水平欠妥。地图制作的水平，主要是作者对地图的理解，制作的意识，技术上的差异却是次要的
*不过，话说回来，触发确实也是一个能让地图增色不少的强有力工具。比如上文说到的音效触发，还有文本触发，画面的触发（有张地图用此制造了昼夜更替的效果）
*触发能丰富地图的内涵：例如宝箱（里面的东西可以自定义，有些地图所谓的“藏了枚核弹”就是运用这个触发），例如莫名其妙的闪电风暴打击或者核弹打击，又如开局赠送一些单位建筑什么的……很多个性化的地图特效，往往都是借助触发完成的。可以说，触发，是地图制作中一个蕴涵了巨大价值的金矿！
●关于INI
*说到个性化特效，当然不能不说INI的修改修改地图INI同样也是地图制作中的高级课题，需要作者对游戏程序规则的熟悉
*会做MOD的人，一定会修改地图内置INI，但反之却不是。修改INI只是制作做MOD的一个子集修改地图INI只需要改每个小节下一个或某几个键或键值，而不需要再去考虑其他键，因此是方便高效的
*修改INI可以打破传统：游戏全局设置上可以修改（建造速度，维修费用，买卖规则等等）；单位属性可以修改（血，装甲，武器，甚至图象）；建筑可以修改（血，装甲，武器，特性等等）……
*不仅如此，还能修改AI，使得电脑疯狂出兵或者严重智障……
●总之
地图制作虽然只是红警MOD的一个分支，但可以研究的还有很多红色警戒虽然已经是一款夕阳游戏，但值得我们去挖掘的还有更多做MOD吃不消？？那就从做地图开始吧……
最后，我也希望吧里有良好的制图氛围，有新人出作品，应该以鼓励赞扬为主，绝对不该出现嘲讽讥笑，维
持红警的生命力，往往就在我们的一言一行中！