前几年，我在学校上学时，经常和同学在宿舍里网络对战“红色警报”，玩多了也一直在探索象“红色警报”这类实时战略游戏背后隐藏的编程奥秘。最近，找到一段空闲时间，终于把以前的想法付诸实施，用VC写了一个实时战略游戏的雏形(执行程式在附件中，采用了本文介绍的算法)。在此把实时战略游戏中寻径(Path-finding)算法的原理及实现技术写给大家。
想象一下，当您兴致勃勃地坐在电脑前，正指挥着屏幕上的千军万马时，突然发现那些坦克车一碰到障碍物便停止行动，您肯定会对他们的愚蠢行为大为不满。因此，在实时战略的电脑游戏中，都采用了实时的寻径算法为可移动物体(如：“红警”中的坦克、士兵)计算一条较为“聪明”的行走路线。
一、单个物体的寻径算法
寻径算法中需要解决的最基本问题是避开障碍物。最容易实现的方法是（参见图１）：
- 从起点到终点拉一条直线A。
- 沿着直线
A朝终点行进，一碰到障碍物便按顺时针方向绕着障碍物行走，直至碰到直线A。- 重复步骤
2，便一定能最终达到目的地。
图
1 (注：红色圆点表示起点，蓝色圆点表示终点；黄色直线标记为A, 黑色直线标记为B, 红色直线标记为B) 该算法计算出来的路径并不是最短的，有时候还会走出傻乎乎的路线，但速度很快，能在较低档次的PC机上满足游戏中实时的需要，“红警”中的寻径算法便是以此为基础的（在帝国时代中采用比较先进的Ａ＊算法，限于篇幅这儿就不作介绍了）。能够对上述算法作几点改进，使可移动物体的行走路线更趋合理。(
一) 看图１，显然可移动物体应按沿逆时针方向绕障碍物走，而不该按顺时针方向去绕弯子。于是，当碰到障碍物时，首先要判断环绕方向。假如比起顺时针方向，逆时针方向行走能以更短的路径碰到直线A，那么选取逆时针方向绕着障碍物行走，反之亦然。(
二) 尽量走直线路径，减少绕行路程。如图1所示，先按上述算法计算出行走路线B，然后当可移动物体在路线B上绕着障碍物行进时，每走一步便从当前位置向终点拉一条直线C，假如沿着直线C前进能和现在还未经过的行走路线B的某段相遇(中间没有障碍物)，就终止绕行，直接按直线C行走至路线B，从而缩短了路途。(
三) 当终点处于障碍物包围之中，可移动物体永远不可能到达终点，无论是按顺时针方向还是逆时针方向绕行都只能回到原地，无法行进了。对于这种情况的处理方式就是绕障碍物一周，选择离终点距离最近的地方停下来。 本文的寻径算法在具体实现中主要涉及到直线和环绕障碍物路线的生成技术。直线的光栅化生成能够参考任何一本电脑图像学教材，这儿不再赘述。下面给出环绕障碍物路线的生成算法(以顺时针方向为例)。
图
2
- 当环绕障碍物行走时，先要判断当前障碍物相对于可移动物体的方向，标记为整数 i（见图2）。例如：障碍物在可移动物体的正右方，就记作方向5。
- 接着可移动物体依次查看方向 j = (i n) mod 8 (n=1..7)，直至发现方向j处无障碍物为止。若障碍物位于正上方
文章整理：西部数码--专业提供域名注册、虚拟主机服务
http://www.west263.com
以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢!
