人工智能、数理算法

oraclelang

怎样在战棋类RPG中实现精灵的移动范围
                                       by Kylinx　Homepage: http://kylinx.yeah.net/

相信玩过这类RPG游戏的玩家都知道，精灵的移动范围是有点象一个“十”的。那么这是怎么样实现的呢？

下面我就来说说我在我的游戏“宿命传说”中的做法

注:“宿命传说”下载地址：http://mail.ustc.edu.cn/~lufites/Downloads/rpg.rar

我在程序中有这么一段描述：

其中TilePos为

class TilePos

{

public:

oraclelang

int Line;//地图块在大地图中的行号

       int Row;//地图块在大地图中的列号

}

TilePos * CalculateArea(TilePos pos,int MoveAbility,int &Num)

{

//   pos 为中心坐标，也就是以这里作为计算范围的中心

//   MoveAbility行动范围

//   Num返回可移动到的坐标的数量

       Num=MoveAbility*(4+(MoveAbility-1)*2)+1;

       int DeltaLine=-MoveAbility;//注意有个负号

       int DeltaRow=0;

       TilePos *tp=new TilePos[Num];

    If(!tp)return NULL;

       for(int i=0;i<Num;i++)

       {

              tp.Line=pos.Line+DeltaLine;

              tp.Row=pos.Row+DeltaRow;

              if( (abs(DeltaLine)+abs(DeltaRow)==MoveAbility) && DeltaRow>=0 )

              {

                     DeltaLine++;

                     DeltaRow=abs(DeltaLine)-MoveAbility;

              }

              else

              {

                     DeltaRow++;

              }

       }

       return tp;

}

可能大家会问：怎么知道块总数呢？

我是这样计算的:

Num= MoveAbility*(4+(MoveAbility-1)*2)+1;

结果为:

MoveAbility->Num

1->5;

2->13;

3->25;

4->41;

至于为什么会想出这样嘛，我说我是归纳的（不知道哪位大虾有更清楚的算法没有，如果有，请Mail我一份，谢谢）

3

0

1

2

大家再看看右边这幅图：

以兰色块为中心，移动力为3的图象就是这样

设兰色块坐标为x0,y0;

则0号块为x0-3,y0;

1号为x0-2,y0-1;

我们不难发现，与兰色块坐标偏移最大的

就是移动力（此图为3）！

如0号块x偏移了-3，y偏移了0

1号块x偏移了-2，y偏移了-1

由此发现，在最外圈的图块偏移的绝对值之和都为3

(3=MoveAbility)

那么怎么得到所有的图块坐标呢？

我从最左端开始扫描（也就是0号块）

当然此时x偏移-3,y偏移0

然后我在for循环中使用了这一句：

if( (abs(DeltaLine)+abs(DeltaRow)==MoveAbility) && DeltaRow>=0 )

              {

                     DeltaLine++;

                     DeltaRow=abs(DeltaLine)-MoveAbility;

              }

              else

              {

                     DeltaRow++;

              }

是什么意思呢？

If里的东西是指当扫描到下边缘时就继续下一列的扫描

DeltaRow=abs(DeltaLine)-MoveAbility是什么呢？上边缘！

Else 里的东西就很好理解了吧？扫描列，直到扫到下边缘为止！

最后就返回一个指针，里面就是可以移动到的范围！！

好了！就这么简单！如果您看了还有什么地方不明白的话，请联

oraclelang

即时战略游戏中如何协调对象移动


作者：Dave C. Pottinger
翻译改写：lzc

　　在图论中人们研究了通过怎样的计算才能找到一条从A点到B点的通路，以图论本身来说这已经解决了从A到B的问题，剩下的只是从A沿着找到的路线移动到B就可以了。这样的认识基于一个默认的假设--道路中的一切障碍物都是固定的，但是在现在已经广泛流行的即时战略类游戏中问题却远远不止这些。举个例子说上下班高峰期的时候，路上的每一个人都清楚地知道自己的目的地和所要走的路径，但是由于某些个人不遵守规则或其他人为原因还是会造成堵车现象。而如果这样的事情发生在一个即时战略的游戏中，那么带给玩家的沮丧感和愤怒将远超过现实中的堵车现象。当游戏中的一个士兵接到玩家的命令要从基地的一侧移动到另一侧以帮助抵抗敌人的进攻时，它需要一个计划(更明确的说是一条寻找出来的路线)使它能够到达目的地，但很可能在它移动的过程中预定的路线上出现了变化(例如玩家让工人们在士兵的必经之路上修建一个建筑或另外一批士兵出现在路上，从而堵塞了道路)，这时如果没有一个优秀的移动系统，那么之前的寻道工作等于是白费工夫。

oraclelang

一些需要解决的问题


　　在进一步深入到我们的移动系统中之前，我将先简介一下人们在解决移动问题上遇到的一些问题，这些问题是消耗最少的CPU时间的同时达到最佳的智能效果和最高的移动精度的关键。

　　首先让我们对比一下同时移动单个对象与同时移动数十、数百个对象的不同。一次移动一个对象是非常简单的，但是一个可以相当完美的移动单个对象的算法并不一定能很好地解决数百个对象的同时移动，这其中最大的问题就是CPU时间的消耗。请一定要切记如果你要制作一个需要同时移动大量个体的游戏程序，那么在CPU的使用上一定要非常的保守。

oraclelang

首先让我们对比一下同时移动单个对象与同时移动数十、数百个对象的不同。一次移动一个对象是非常简单的，但是一个可以相当完美的移动单个对象的算法并不一定能很好地解决数百个对象的同时移动，这其中最大的问题就是CPU时间的消耗。请一定要切记如果你要制作一个需要同时移动大量个体的游戏程序，那么在CPU的使用上一定要非常的保守。

　　某些移动算法是很依赖CPU速度的，这就是那些要同时移动大量个体的游戏中只有很少的一部分支持高级的移动方式(例如个体的加速和减速)的原因。玩家们总是认为游戏中的大船和被重装备武装起来的战士们应该具有能够加速和减速的能力，这样才能体现出真实性，但是这小小的真实性将会增加超乎想象的额外的CPU计算工作。这种情况下事实上用来处理个体移动的时间增加了，因为你不得不花费更多的时间来计算加速度，从而获得新的速度值。在后面我们扩展例子程序到处理移动的预操作部分时，你将清楚地看到这样的工作所增加的计算复杂度有多大。另一个将会大大增加CPU计算量的问题是个体的转动半径。大多数寻道算法都不考虑个体的转动半径(转动半径是指一个个体原地旋转一周所需的最小圆的半径，因为我们不可能让一个士兵倒退着走上半张地图去袭击敌人的基地，所以经常需要个体进行旋转)对道路选择的影响。于是就会出现一种情况，虽然我们的一头大象已经找到了一条通往目的地的通路，但是它却不能沿着这条路线移动到目的地，因为路线中的一个拐角面积要比大象的转动半径小一些。大多数移动系统通过减缓个体的速度，再作出一个缓慢而更节省空间的转身动作(相信很多人都看到过即时战略游戏中士兵在拐角处被堵住时所作的动作吧)来解决这一问题，但这种方法会极大的增加CPU的计算量。

　　正如大家所想象的那样，即使是即时战略游戏也并不是即时的，而是不断的进行循环，在每次循环中处理游戏的全部数据和玩家的指令(我们可以称它为UL-Update Loop)。为了增加游戏的性能，一般采用的方法是记录上一次UL的所消耗的时间，以预测下一次UL大约将要花费的时间(为了能尽可能地逼近即时处理，这样做是很有必要的)，但是这就给个体的移动带来了大问题--每次UL中个体的移动距离很可能是完全不同的，下面的图1就是这种情况的一个例子。负责个体移动的算法显然在面对每次移动相同距离时比每次都要为所有移动个体计算不同的时间下移动出的不同距离并将其显示出来要轻松得多。当然，如果游戏的UL系统制作的非常优秀，那将略微改善一点这样的窘境。

oraclelang

不要忘记处理个体移动中的碰撞问题。一旦你的游戏中的士兵们碰撞到了一起，你要怎样将他们分开呢？一种方法是是个体之间根本不发生碰撞，但在实际的应用中这是不可能做到的。不仅仅是实现这要求的程序代码非常难写，而且无论你写再多的代码也是无用的，这些个体总是会找到一些途径来使彼此重叠在一起，而在更多的情况中，这些个体的重合是必须的。一些使用近距离兵器进行战斗的游戏，例如《帝国时代》，就是一个要求个体重合的实例。另外，如果你要限制你游戏中的个体不能碰撞在一起，那么他们很可能为了避开彼此而离开预设的移动路线，暴露在其它对手的攻击之下，受到意外的伤害，这会使玩家对你的游戏极端不满。因此你必须决定好你的那些个体相互靠的有多近，重合多少是可以容忍的，还要设法处理由这些决定所带来的问题

oraclelang

注意考虑地图的复杂性。在复杂的地图上实现良好的移动的算法比简单地图上做到同样效果的算法要复杂得多，由于现在地图越来越倾向于复杂和真实，对于移动算法的要求也进一步提高了。

　　随机生成的地图可能造成意想不到的问题。由于不能通过给固定道路编写预定路线来减小寻道的难度，因此随机生成的地图在复杂性上要更高于预设地图，尤其对于寻道而言。当寻道变得使CPU负担过重时，唯一的解决方法是降低寻道的精度和质量，这时就要求提高移动算法的质量以弥补寻道上的不足造成的程序反应迟钝。

oraclelang

一定要认真处理各类个体的体积和由此产生的空间问题，这个问题最能说明你所需要的移动算法的精度。如果你的程序中需要移动的物体很少，以至于几乎不会出现彼此互相碰撞的情况(例如大部分的第一人称射击游戏)，那你可以放心地使用一些简单的算法。如果你的程序所要处理的移动物体非常多，并且还要处理彼此的碰撞和诸如检测两个个体之间的缝隙是否足够更小的个体从中间穿过等等操作，这时对你的移动算法在精确度上和质量上的要求将会使计算量大幅度的增加。

oraclelang

一个简单的移动算法


　　让我们从一个简单的对个体状态进行处理的移动算法的伪码(点击这里看伪码)开始，这个算法所作的只是简单的使用一条给定路线前进，当遇到碰撞和冲突时重新寻道，因此它能在2D和3D游戏中都表现得很出色。使用该算法，我们将从一个给定的状态开始，持续循环直到找到一个可行的位置作为中继点作为个体移动的目标去接近之后才跳出循环。移动状态将会在整个UL中保存下来，这将使我们能够正确的设置未来的状态，例如"自动"添加中继点。这种保存机制可以保证减少一个个体在下一次UL中作出与当前UL移动相反的判断的可能性

oraclelang

我们假定被给定了一条通向目的地的路径，并且这条路径在提供给我们时是精确的，并且是可行的(也就是不会发生碰撞)。由于大多数即时战略游戏拥有巨大的地图，以至于一个个体可能要花费几分钟的时间来走完整个路程，而在这几分钟里地图上可能发生使当前路径不在可用的变化(例如在路径上新建了建筑)。为了解决这个问题，现在我们加入少许碰撞检测，一旦遇到碰撞，就进行重新寻道。在后面你将看到，我们可以采取几种方法来避免重新寻道，以减少CPU消耗。