红警2地图移动问题和制作心得
《红色警戒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共和国之辉操作指南
►红色警戒2热键介绍_热键有哪些
►红色警戒2最新对战绝招_怎样对战
►红色警戒2秘籍大全