findingnemo:即时战略游戏中寻径(Path-finding)算法的原理及实现技术

　　前几年我在学校上学时经常和同学在宿舍里网络对战“红色警报”玩多了也直在探索象“红色警报”这类即时战略游戏背后隐藏编程奥秘最近找到段空闲时间终于把以前想法付诸实施用VC写了个即时战略游戏雏形(执行在附件中采用了本文介绍算法)在此把即时战略游戏中寻径(Path-finding)算法原理及实现技术写给大家

　　想象下当你兴致勃勃地坐在电脑前正指挥着屏幕上千军万马时突然发现那些坦克车碰到障碍物便停止行动你肯定会对它们愚蠢行为大为不满因此在即时战略计算机游戏中都采用了实时寻径算法为可移动物体(如:“红警”中坦克、士兵)计算条较为“聪明”行走路线

、单个物体寻径算法

　　寻径算法中需要解决最基本问题是避开障碍物最容易实现思路方法是(参见图１):

1. 从起点到终点拉条直线A
2. 沿着直线A朝终点行进遇到障碍物便按顺时针方向绕着障碍物行走直至碰到直线A
3. 重复步骤2便定能最终达到目地

\" width=300 border=0> 图1
(注:红色圆点表示起点蓝色圆点表示终点；黄色直线标记为A, 黑色直线标记为B, 红色直线标记为B)



　　该算法计算出来路径并不是最短有时候还会走出傻乎乎路线但速度很快能在较低档次PC机上满足游戏中实时要求“红警”中寻径算法便是以此为基础(在帝国时代中采用比较先进Ａ＊算法限于篇幅这儿就不作介绍了)可以对上述算法作几点改进使可移动物体行走路线更趋合理

　　() 看图１显然可移动物体应按沿逆时针方向绕障碍物走而不该按顺时针方向去绕弯子于是当遇到障碍物时首先要判断环绕方向如果比起顺时针方向逆时针方向行走能以更短路径碰到直线A那么选取逆时针方向绕着障碍物行走反的亦然

　　( 2) 尽量走直线路径减少绕行路程如图1所示先按上述算法计算出行走路线B然后当可移动物体在路线B上绕着障碍物行进时每走步便从当前位置向终点拉条直线C如果沿着直线C前进能和目前还未经过行走路线B某段相遇(中间没有障碍物)就终止绕行直接按直线C行走至路线B从而缩短了路途

　　( 3) 当终点处于障碍物包围的中可移动物体永远不可能到达终点无论是按顺时针方向还是逆时针方向绕行都只能回到原地无法行进了对于这种情况处理方式就是绕障碍物周选择离终点距离最近地方停下来

　　本文寻径算法在具体实现中主要涉及到直线和环绕障碍物路线生成技术直线光栅化生成可以参考任何本计算机图形学教材这儿不再赘述下面给出环绕障碍物路线生成算法(以顺时针方向为例)

\" width=202 border=0> 图2

1.当环绕障碍物行走时先要判断当前障碍物相对于可移动物体方向标记为整数i(见图2)例如:障碍物在可移动物体正右方就记作方向5
2.接着可移动物体依次查看方向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)等 7个方向查看是否有通路至于障碍物相对于可移动物体其他位置处理照此类推
3.重复步骤1、2便能完成顺时针环绕障碍物行走该算法详细伪语言描述见下,反复ClockwiseWalkOneStep即可顺时针绕障碍周

boolean ClockwiseWalkOneStep(& nCol,& nRow,& i);
{
??? n;

??? for ( n = 1; n <=7 ; n )
??? {
??????? i =(i + n) mod 8;
??????? ( Map[nCol,nRow].IsPassable(i) = true )
??????????? ;
??? }

??? ( n7 && Map[nCol,nRow].IsPassable(i) = false )
??????? false;

??? switch ( i ) {
??? 1:?
??? {
??????? nCol = nCol-1;
??????? i = 7;
??????? ;
??? }
??? 2:?
??? {
??????? ( Map[nCol,nRow].IsPassable(3) false ) // 尽量走垂直或水平方向
??????? {
??????????? nCol = nCol-1;
??????????? nRow = nRow+1;
??????????? i = 7;
??????? }
???????
??????? {
??????????? nRow = nRow+1;
??????????? i = 0;
??????? }
??????? ;
??? }
??? 3:?
??? {
??????? nRow = nRow+1;
??????? i = 1;
??????? ;
??? }
??? 4:?
??? {
??????? ( Map[nCol,nRow].IsPassable(5) false )
??????? {
??????????? nCol = nCol+1;
??????????? nRow = nRow+1;
??????????? i = 1;
??????? }
???????
??????? {
??????????? nCol = nCol+1;
??????????? i = 2;
??????????? end
??????? }
??????? ;
??? }
??? 5:
??? {?
??????? nCol = nCol+1;
??????? i = 3;
??????? ;
??? }
??? 6:
??? {
??????? ( Map[nCol,nRow].IsPassable(7) false )
??????? {
??????????? nCol = nCol+1;
??????????? nRow = nRow-1;
??????????? i = 3;
??????? }
???????
??????? {
??????????? nRow = nRow-1;
??????????? i = 4;
??????? }
??????? ;
??? }
??? 7:
??? {
??????? nRow = nRow-1;
??????? i = 5;
??????? ;
??? }
??? 0:
??? {
??????? ( Map[nCol,nRow].IsPassable(1) = false )
??????? {
??????????? nCol = nCol-1;
??????????? nRow = nRow-1;
??????????? i = 5
??????? }
???????
??????? {
??????????? nCol = nCol-1;
??????????? i = 6;
??????? }
??????? ;
??? }



??? }
??? true;
}



2、动态障碍物环境中行走路径生成技术

　　刚才描述算法只适用于单个可移动物体在静止障碍物环境中生成行走路径然而在实际即时战略游戏中经常是群坦克在个动态地图上纵横驰骋区别坦克在行走过程中相遇时互为障碍物而且是可移动障碍物．因此必须对上面算法作出修改使得物体在运动中避开可移动障碍物．

　　最直观解决办法是碰到可移动障碍物马上重新计算行走路径该思路方法缺点是重复计算路径、耗时太多．其实当某个物体碰撞到个处于运动状态可移动障碍物时可以先等待段时间接着若发现可移动障碍物已挪开就可以按原来行走路径继续前进从而节省了重复计算路径时间；反的若发现可移动障碍物仍在原地就比较两者优先级(预先为每个行走物体分配个优先级)优先级较低则继续等待优先级高者立刻重新计算行走路径避开可移动障碍物．显然运用该思路方法可以减少很多重复计算加快了执行速度．该算法伪语言描述见下:

// 遍历所有可移动物体
for (i = 1; i <= n; i)
{
??? Switch ( Tank[i].State ) {
??????? Run:?
??????? {
??????????? (Tank[i]接到指挥命令)
??????????? {
??????????????? Tank[i].GoalPos = 目地址;
??????????????? Tank[i].State = FindNewPath;
??????????? }

??????????? (Tank[i].Pos RouteList[Tank[i]].GetEndPos) //到达终点
??????????? {
??????????????? Tank[i].State = Stillness;
??????????????? ;
??????????? }

??????????? Tank[i].PosNext = RouteList[Tank[i]].GetNextPos; //取出下步
??????????? ( 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;
??????????? }
???????????
??????????? {
??????????????? (Map[Tank[i].PosNext].State Stillness || (Tank[i].WaitTime > 规定时间 && Tank[i].PriorNum > Map[Tank[i].PosNext].PriorNum))
??????????????????? Tank[i].State = FindNewPath;
???????????????
??????????????????? Tank[i].WaitTime ;
??????????? }
??????????? ;
??????? }
??????? FindNewPath:
??????? {
根据Tank[i].GoalPos,计算Tank[i]行走路径并添入RouteList[Tank[i]]；
??????????? ( RouteList[Tank[i]] 为空 )
??????????????? Tank[i].State = FindNewPath;
???????????
??????????? {
??????????????? Tank[i].State = Run;
??????????????? Tank[i].WaitTime = 0;
??????????? }
??????????? ;
??????? }
??????? Moving:
??????? {
??????????? // 在Ｐos和PosNext间作线性插值
??????????? ( (Tank[i].CurrentMovingPos + nStep) < Tank[i].PosNext )
??????????? {
??????????????? Tank[i].CurrentMovingPos nStep;
??????????????? Tank[i].State = Moving;
??????????? }
???????????
??????????? {
??????????????? 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;
??????????? }
??????? }
??????? Stillness:
??????? {
??????????? (Tank[i]接到指挥命令)
??????????? {
??????????????? Tank[i].GoalPos = 目地址;
??????????????? Tank[i].State = FindNewPath;
??????????? }
??????????? ;
??????? }
??? }
}

先绘制背景；
for (i = 1; i <= n; i)
??? Draw(Tank[i].CurrentMovingPos);

\" width=513 border=0>
图3 可移动物体状态转换图

　　 上述算法中可移动物体具有 4种状态(见图3):Stillness、Run、FindNewPath、Moving在情况下可移动物体处于Stillness状态当接受指挥命令后便进入FindNewPath状态旦计算出行走路径可移动物体就置为Run状态在Run状态下从行走路径列表中取出下步坐标若该坐标所示位置无障碍物状态变迁为Moving进行前后两步间坐标插值结束后又回到Run状态；若发现原先计算出来行走路径已经不适用了便从Run状态转为FindNewPath状态等找到新路径后再恢复至Run状态最后当到达终点时可移动物体状态为Stillness
　

延伸阅读

• 2008-10-6-- processes:Finding and Listing Processes in C#