即时战略游戏中寻径(Path-finding)算法的原理及实现技术
作者：沈璐
前几年，我在学校上学时，经常与同学在宿舍里网络对战“红色警报”，玩多了也一直在探索象“红色警报”这类即时战略游戏背后隐藏的编程奥秘。最近，找到一段空闲时间，终于把以前的想法付诸实施，用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处无障碍物为止。若障碍物位于正上方(7)，可移动物体首先看左上方向(0 = (7+1) mod 8)能否通过，如果不通就接着试左边方向(1 = (7+2) mod 8)，还不行再依次按图上所示箭头试探其余几个方向，直至找到出口，并往该方向行走一步。若障碍物位于左下方(2)，则依次按下方(3)、右下方(4)、右方(5)、右上方(6)、上方(7)、左上方(0)、左方(1)等七个方向查看是否有通路。至于障碍物相对于可移动物体的其他位置的处理，照此类推。 重复步骤1、2，便能完成顺时针环绕障碍物行走。该算法详细的伪语言描述见下,反复调用函数ClockwiseWalkOneStep即可顺时针绕障碍一周。boolean ClockwiseWalkOneStep(int& nCol,int& nRow,int& i); { int n; for ( n = 1; n <=7 ; n++ ) { i =(i + n) mod 8; if ( Map[nCol,nRow].IsPassable(i) = true ) break; } if ( n==7 && Map[nCol,nRow].IsPassable(i) = false ) return false; switch ( i ) case 1: { nCol = nCol-1; i = 7; break; } case 2: { if ( Map[nCol,nRow].IsPassable(3) == false ) // 尽量走垂直或水平方向 { nCol = nCol-1; nRow = nRow+1; i = 7; } else { nRow = nRow+1; i = 0; } break; } case 3: { nRow = nRow+1; i = 1; break; } case 4: { if ( Map[nCol,nRow].IsPassable(5) == false ) { nCol = nCol+1; nRow = nRow+1; i = 1; } else { nCol = nCol+1; i = 2; end } break; } case 5: { nCol = nCol+1; i = 3; break; } case 6: { if ( Map[nCol,nRow].IsPassable(7) == false ) { nCol = nCol+1; nRow = nRow-1; i = 3; } else { nRow = nRow-1; i = 4; } break; } case 7: { nRow = nRow-1; i = 5; break; } case 0: { if ( Map[nCol,nRow].IsPassable(1) = false ) { nCol = nCol-1; nRow = nRow-1; i = 5 } else { nCol = nCol-1; i = 6; } break; } } return true; }
二、动态障碍物环境中的行走路径生成技术
刚才描述的算法只适用于单个可移动物体在静止的障碍物环境中生成行走路径。然而在实际的即时战略游戏中，经常是一群坦克在一个动态的地图上纵横驰骋，不同的坦克在行走过程中相遇时互为障碍物，而且是可移动的障碍物．因此，必须对上面的算法作出修改使得物体在运动中避开可移动的障碍物．
最直观的解决办法是，一碰到可移动的障碍物，马上重新计算行走路径，该方法的缺点是重复计算路径、耗时太多．其实，当某个物体碰撞到一个处于运动状态的可移动障碍物时，可以先等待一段时间，接着若发现可移动障碍物已挪开，就可以按原来的行走路径继续前进，从而节省了重复计算路径的时间；反之，若发现可移动障碍物仍在原地，就比较两者的优先级（预先为每一个行走物体分配一个优先级），优先级较低则继续等待，优先级高者立刻重新计算行走路径避开可移动的障碍物．显然，运用该方法可以减少很多重复计算，加快了执行速度．该算法伪语言描述见下：
// 遍历所有可移动物体 for (i = 1; i <= n; i++) { Switch ( Tank[i].State ) { case Run: { if （Tank[i]接到指挥命令） { Tank[i].GoalPos = 目的地址; Tank[i].State = FindNewPath; } if (Tank[i].Pos == RouteList[Tank[i]].GetEndPos()) //到达终点 { Tank[i].State = Stillness; break; } Tank[i].PosNext = RouteList[Tank[i]].GetNextPos(); //取出下一步 if ( Map[Tank[i].PosNext].Passable == true) { Tank[i].State = Moving; Tank[i].CurrentMovingPos = Tank[i].Pos; Map[Tank[i].PosNext].Passable = false; Map[Tank[i].Pos].Passable = false; } else { if (Map[Tank[i].PosNext].State == Stillness || (Tank[i].WaitTime > 规定时间 && Tank[i].PriorNum > Map[Tank[i].PosNext].PriorNum)) Tank[i].State = FindNewPath; else Tank[i].WaitTime ++; } break; } case FindNewPath: { 根据Tank[i].GoalPos,计算Tank[i]的行走路径，并添入RouteList[Tank[i]]； if ( RouteList[Tank[i]] 为空 ） Tank[i].State = FindNewPath; else { Tank[i].State = Run; Tank[i].WaitTime = 0; } break; } case Moving: { // 在Ｐos与PosNext间作线性插值 if ( (Tank[i].CurrentMovingPos + nStep) < Tank[i].PosNext ) { Tank[i].CurrentMovingPos += nStep; Tank[i].State = Moving; } else { Tank[i].CurrentMovingPos = Tank[i].PosNext; Tank[i].State = Run; Tank[i].WaitTime = 0; Map[Tank[i].PosNext].Passable = false; Map[Tank[i].Pos].Passable = true; Tank[i].Pos = Tank[i].PosNext; } } case Stillness: { if （Tank[i]接到指挥命令） { Tank[i].GoalPos = 目的地址; Tank[i].State = FindNewPath; } break; } } } 先绘制背景； for (i = 1; i <= n; i++) Draw(Tank[i].CurrentMovingPos);
图3 可移动物体状态转换图
上述算法中，可移动物体具有四种状态(见图3)：Stillness、Run、FindNewPath、Moving。在初始情况下，可移动物体处于Stillness状态。当接受指挥命令后，便进入FindNewPath状态。一旦计算出行走路径，可移动物体就置为Run状态。在Run状态下，从行走路径列表中取出下一步的坐标，若该坐标所示位置无障碍物，状态变迁为Moving，进行前后两步间的坐标插值，结束后又回到Run状态；若发现原先计算出来的行走路径已经不适用了，便从Run状态转为FindNewPath状态，等找到新路径后，再恢复至Run状态。最后，当到达终点时，可移动物体的状态为Stillness。
察看本算法的实际效果，请下载DEMO程序。
作者： 沈 璐 Email: uulushen@public1.sz.js.cn 通讯地址：江苏省苏州市干将东路704号 邮政编码：215000
