下面的没有经过实践，因此很可能是错误的，觉得有用的初学朋友读一读吧：）
希望高人指点一二 :)

简介：
在标准的SLG游戏中，当在一个人物处按下鼠标时，会以人物为中心，向四周生成一个菱形的可移动区范围，如下：

  0
 000
00s00
 000
  0

这个图形在刚开始学习PASCAL时就应该写过一个画图的程序（是否有人怀念？）。那个图形和SLG的扩展路径一样。

一、如何生成路径：
从人物所在的位置开始，向四周的四个方向扩展，之后的点再进行扩展。即从人物所在的位置从近到远进行扩展（类似广宽优先）。

二、扩展时会遇到的问题：
1、当扩展到一个点时，人物的移动力没有了。
2、当扩展的时候遇到了一个障碍点。
3、当扩展的时候这个结点出了地图。
4、扩展的时候遇到了一个人物正好站在这个点（与2同？）。
5、扩展的点已经被扩展过了。当扩展节点的时候，每个节点都是向四周扩展，因此会产生重复的节点。

当遇到这些问题的时候，我们就不对这些节点处理了。在程序中使用ALLPATH[]数组记录下每一个等扩展的节点，不处理这些问题节点的意思就是不把它们加入到ALLPATH[]数组中。我们如何去扩展一个结点周围的四个结点，使用这个结点的坐标加上一个偏移量就可以了，方向如下：

  3
  0 2
  1

偏移量定义如下：
int offx[4] = { -1, 0, 1, 0 };
int offy[4] = { 0, 1, 0, -1 };

扩展一个节点的相邻的四个节点的坐标为：
for(int i=0; i<4; i )
{
    temp.x = temp1.x offx[i];
    temp.y = temp1.y offy[i];
}

三、关于地图的结构：
1、地图的二维坐标，用于确定每个图块在地图中的位置。
2、SLG中还要引入一个变量decrease表示人物经过这个图块后他的移动力的减少值。例如，一个人物现在的移动力为CurMP=5，与之相领的图块的decrease=2；这时，如果人物移动到这里，那它的移动力变成CurMP-decrease。
3、Flag域：宽度优先中好像都有这个变量，有了它，每一个点保证只被扩展一次。防止一个点被扩展多次。（一个点只被扩展一次真的能得到正确的结果吗？）
4、一个地图上的图块是否可以通过，我们使用了一个Block代表。1---不可以通过；0---可以通过。

这样，我们可以定义一个简单的地图结构数组了：

#define MAP_MAX_WIDTH 50
#define MAP_MAX_HEIGHT 50
typedef struct tagTILE{
    int x,y,decrease,flag,block;
}TILE,*LPTILE;
TILE pMap[MAP_MAX_WIDTH][MAP_MAX_HEIGHT];

以上是顺序数组，是否使用动态的分配更好些？毕竟不能事先知道一个地图的宽、高。

四、关于路径：
SLG游戏中的扩展路径是一片区域（以人物为中心向四周扩展，当然，当人物移动时路径只有一个）。这些扩展的路径必须要存储起来，所有要有一个好的结构。我定义了一个结构，不是很好：

typedef struct tagNODE{
    int x,y;   //扩展路径中的一个点在地图中的坐标。
    int curmp; //人物到了这个点以后的当前的移动力。
}NODE,*LPNODE;

上面的结构是定义扩展路径中的一个点的结构。扩展路径是点的集合，因此用如下的数组进行定义：

NODE AllPath[PATH_MAX_LENGTH];

其中的PATH_MAX_LENGTH代表扩展路径的点的个数，我们不知道这个扩展的路径中包含多少个点，因此定义一个大一点的数字使这个数组不会产生溢出：

#define PATH_MAX_LENGTH 200

上面的这个数组很有用处，以后的扩展就靠它来实现，它应该带有两个变量nodecount 代表当前的数组中有多少个点。当然，数组中的点分成两大部分，一部分是已经扩展的结点，存放在数组的前面；另一部分是等扩展的节点，放在数组的后面为什么会出现已扩展节点和待扩展节点？如下例子：

当前的人物坐标为x,y；移动力为mp。将它存放到AllPath数组中，这时的起始节点为等扩展的节点。这时我们扩展它的四个方向，对于合法的节点（如没有出地图，也没有障碍......），我们将它们存放入AllPath数组中，这时的新加入的节点（起始节点的子节点）就是等扩展结点，而起始节点就成了已扩展节点了。下一次再扩展节点的时候，我们不能再扩展起始节点，因为它是已经扩展的节点了。我们只扩展那几个新加入的节点（待扩展节点），之后的情况以此类推。那么我们如何知道哪些是已经扩展的结点，哪些是等扩展的节点？我们使用另一个变量cutflag，在这个变量所代表的下标以前的结点是已扩展节点，在它及它之后是待扩展结点。

五、下面是基本框架（只扩展一个人物的可达范围）：

　　一提起游戏中的寻路，很多人就会想起A*算法，的确，A*无疑是当前用的最多也是最先进的算法，在比较简单的地图上它的速度非常快，能很快找到最短路径(确切说是时间代价最小路径)，而且使用A*算法可以很方便地控制搜索规模以防止程序堵塞。

　　关于A*算法的文章已经很多了，上google随便一搜都能找到，但是国内网友原创的似乎不是很多，建议英文不太差的爱好者上国外的网站查找相关资料，比如http://www-cs-students.stanford.edu/~amitp/gameprog.html。

　　A*算法本身表述起来很简单，程序写起来也不难，两三百行轻松搞定，关键是要在代码优化上下功夫，这就很考验程序员的算法功底了。基本的思路一般都是以空间(也就是内存的占用)换取时间(搜索速度)，另外还有一些地图预处理(包括人工的预处理和用程序预处理)的技术比如多级地图精度或者地图分区域搜索等等，但我今天要讨论的不是A*算法本身，关于这方面有兴趣的网友可以另外和我交流。

　　不管怎么优化，寻路总是一项非常费时的工作，并且工作量和地图的大小基本成线性关系(不限制搜索规模的前提下)，现在的rts往往允许每方生产200个以上的移动单位，同时可能会有大量的移动物体需要寻路，如果同时选定100个单位点并向他们下达远程行军命令，假设每次寻路需要5ms(在复杂地图上，这个数值一点都不夸张，我是说在我的机器上)，那么就需要0.5秒的时间在寻路上，也就是说整个游戏将因此停顿0.5秒，你受的了么？

　　呵呵，俺们程序员是不会让这种情况出现地，通常有几种方法来避免寻路运算导致程序堵塞：

　　1、限制同时选定的移动单位个数
　　　帝国2里面，这个限制是40个，当然这样一来，同一个编队里的人数就不可能超过40了，这一方面是为了减少寻路耗时，同时可能也有别的考虑，我能想到的是同时控制过多的单位攻击同一个目标可能效率会很低，我不知道其它rts游戏是否也有类似的限制，但是如果采用了下文所述的第2，第3种方案的话，这个限制就显得不那么重要了。

　　2、把寻路工作在时间上分散进行
　　　可以估计一下每次寻路所花的时间，限制每个“回合”(就是游戏的一帧)最多让多少个单位寻路，其它的等下一个回合再说，这样游戏就不会停顿，但是缺点是可能会看到所有人不是同时动身，而是先后开始移动，网上有文章说为了避免选中的单位“发楞”而让玩家以为出了什么问题，可以让一时来不及寻路的单位花很少的时间凭“直觉”决定一个方向(通常就是目标所在的直线方向了)先走再说,等轮到自己寻路以后再改回来，这也是个办法，因为“直觉”的方向在大多数情况下就是正确的方向，但是据我观察在帝国2里面没有用到这个小伎俩,后面会说到。

　　3.这个是最实惠最有效的，就是距离相近的单位公用一条路径，所谓“相近”一般来说以互相都在视野之内为限
　　　玩过帝国2的人都会感叹其中各种漂亮的阵型，连行军的时候都要摆的整整齐齐的一个方阵(当然前提是在空地上跑)。即使你故意挨个把他们分散了(不能距离太远)，同时选中他们并点取一个目的地以后，他们也会在行进中慢慢的自动靠拢，不一会又排成方阵了，而且，不管你让他们去地图的什么地方，他们都会全体立即响应，而不会出现上一条所说的那种停顿或者先后启动，这是怎么回事呢？聪明的你一定能想到，只要让一个人带队寻路，其他人跟着就行了，对！就是这么回事。让一个单位寻路而其余的单位跟随，这比让每个单位单独寻路要快的多了，这个带队的移动单位称之为“寻路兵”。

　　说到这里要提到帝国2的一个不知能不能算的bug，比如有一条很长的小河，你有一帮人马，一部分在河左边，另一部分在河右边，他们挨的很近，虽然隔着河。现在你画个框把他们同时选定，比如让他们都到河左边，因为他们相互都看得见，于是程序就选了一个人带路(怎么选的我不太清楚)，这时候可能出现两种情况：一种是寻路兵在河左边，于是他带着河左边的众弟兄朝目的地去了，河右边的一干人很想跟着(根据程序的设定，他们不需要自己寻路)但是无奈隔着河过不去，在河边彷徨了一会(帝国2的算法据我观察在原定路线不能走的情况下会先尝试从两边绕行，当然绕行的范围是有限的，如果发现绕不过去才重新寻路)，当对岸的人马走出他们视野的时候他们才想起来可以自己寻路，于是顺着河边绕过去了；另一种情况更搞笑，就是系统选出的寻路兵在河右边，本来河左边的人是离目的地很近的，但是他们不管，非要隔着河紧跟着那边的寻路兵，直到在河流的尽头与寻路兵所在的部队汇合以后，才一起排着方阵走向目的地。

　　关于帝国2中寻路兵的确定，就是在一队人马中选哪个来带头寻路，我还没有什么头绪。
　　另外，当寻路兵死亡(按了del键，呵呵)，或者被指定了另外的目的地时，剩下的单位中会重新产生一个寻路兵，重新寻路。

　　奇怪的是，帝国2中的农民的移动却没有采用寻路兵策略，即使彼此很靠近的一堆农民，他们移动时也不会排成方阵，而且点选目标的一瞬间会出现上文第2条所述的那种停顿，即有的农民先启动，有些后启动。在我的CII533的机器上，40个农民，huge空白地图从一头到另一头，最快启动的农民和最慢的大概相差0.5秒，延迟已经很明显了。我不太明白为什么这么设计，可能是农民行为的特殊性上的考虑，呵呵，农民嘛，向来是自由散漫无组织无纪律的:)

　　另外关于帝国2要说明的是它没有类似红警里面的同一方的“让路”算法，如果你让几个人把一个咽喉要道堵住，然后控制另一队人试图通过这个关口，可以看出寻路的时候算法没有考虑堵住关口的单位,因为你控制的人马径直就朝这个关口过来了，就像以为它是通的一样(这本身是合理的，因为他们不知道挡路者什么时候会离开)，到了跟前一看堵住了，左边右边的绕了两下没绕过去就回头找另一条路去了，挡路的人根本无动于衷。

　　现在的rts正在向网络化发展，在地图越来越大，移动单位越来越多的情况下，一方面是路径搜索算法本身的效率，另外行军算法(例如阵型，让路等等)的效率和巧妙程度也是个很值得研究的课题。
 
　　呵呵，居然写了这么多，我有时间的话还会研究一下其它游戏的寻路特点，如果有同好者欢迎和我交流，本文如果要转载，请注明是转载，谢谢！
 
cooker
03_05_16