1、人工智能,小组成员：xx,人工智能,游戏中的人工智能群聚,什么是群聚呢？,群聚，就是多个非玩家角色一起行动，而不是个别行动。比如说：你看到的是一群大雁，它们的飞行是有一定的规律，而且你完全可以看出来它们会排成一字或者人字，不会是乱糟糟的飞行。那么，我们在游戏中，诸如巡逻小队之类的移动又是什么样的呢？1987年，Craig Reynolds发表了一篇名为Flocks，Herds and Schools：A Distributed Behavial Model的论文，在这篇论文中，他提出了基本的群聚算法模型，甚至可以这样说，后续的一系列群聚算法都有这篇论文的身影。那么我们来看看Craig Reyn
2、olds提到的boids类鸟群的模拟群体。在这种类鸟群里面，是没有领导核心，它们都是跟着群体在走，而这个群体似乎是自己有自己的想法。,Reynolds基本群聚算法核心,群体行为的核心是基本的群聚算法。“单位”（unit）指代组成群体的个别实体。凝聚：每个单位都往其临近单位的平均位置行动。对齐：每个单位行动时，都要把自己对齐在其临近单位的平均方向上。分隔：每个单位行动时，要避免撞上其临近单位。,Reynolds基本群聚算法是没有领导核心的；就某种意义而言，它们都跟着整个群体移动。每个单位都必须有行进的能力；每个单位都必须知道其局部周围的情况，即邻近单位位置、方向以及群体中与自身最靠近的单位之间的
3、距离。在仿真物理环境中可以对仿真中的单位施加转向力使其改变方向；在砖块环境中可以采用视线方法让单位改变方向或朝特定点移动。,为了分析我们这个群聚系统，我们需要理解一些基本的概念：1，单位的视野，我们以r为单位的视野半径，以为视野角度，落在这个圆弧内的所有物体都是可见的。2，避开规则（Avoidance rule），单位不会被彼此撞上。3，凝聚规则，单位离得太远就应该靠近一点，这个规则和避开规则合在一起，从而形成了群聚。,砖块环境中的移动模式,非确定性方法（加入随机因素）：1、初始化路径数组，移动数组 2、用Bresenham线段算法计算不同的移动模式 3、将模式标准化 4、设定前进速率，按照设
4、定好的移动模式移动，当到达线段的端点时检查移动数组，以确定移动方向。,到目前为止，我们讨论的群聚规给大家留下了深刻印象。然而，像这样的群聚行为如果在游戏中，这些单位以群体形态移动式，还能避免撞上游戏世界里的物体，那就更实用了。,实际上加入避开障碍物的行为其实相当简单，我们所要做的就是提供某种机制给那些单位使用，让他们看到前方，再施加适当的转向力，使其避开路径中的障碍物。首先，我们运算向量a，这只是该单位和障碍物位置间的差值，接着，取a和v的内积，将a投射到v上，由此可得向量p，把向量p减去向量a，可得向量b，现在要测试v是否和圆的某处相交，得测试两种情况。1.p的数值必须小于v的数值。2.b的
5、数值必须小于该障碍物的半径r。如果两者都是如此，则需要校正转向力，否则，该单位可继续沿当前方向前进。,追随领头者,对基本群聚算法的修改不必只限于避开障碍物。因为来自于各种规则的转向力都在同一变量中累加，然后一次施加，以控制该单位的方向，所以，我们还可以在考虑过的规则之上在叠加其他许多有效的规则。其中一条有趣的外加规则，就是跟随领头者规则。如前所述，我们讨论的群聚规则是没有领头者的，然而，如果我们把基本群聚算法和某些领头者AI结合起来，就可以在游戏中使用群聚功能时，开启许多新的可能效果。如果我们在其中加入领头者，就能让群体的移动更有目的性，或者看起来比较有智能。,我们来看看一个实际例子：,另一种
6、群聚方法简化集群技术,Reynolds的群聚算法已经被很好地证明了，而且在生成若干组智能体的逼真动作效果非常好。但是，该算法在计算上的开销大，尤其是在有大量智能体或者有复杂场景需要探测的时候。因此，他们有时候不适合实时的应用程序，比如电视游戏。所以我们有必要对集群技术进一步的进行简化。,群聚算法在模拟少量或中等数量的生物的自然行为时是完美的，尤其当这些生物的运动（而不是生物和生物之间的影响、以及生物和场景之间的互动）是主要的关注焦点的游戏中（例如任天堂的Pikmin）。但是，随着生物个数的增加，传统的群聚算法开销越来越大。在群聚中每个智能体必须检查其他所有智能体以确定是否因距离太近而产生影响，
7、在这种情况下，如果存在n个智能体的场景，需要计算1/2(n)次独立的距离计算（给出中间的结果储存在交互的数组里）。那么分离规则，队列规则和聚合规则必须对每个智能体计算它附近的每个智能体。另一方面，因为影响是相互的，所以保存中间结果可以使计算量减半。,那么如何对集群技术进行简化呢？,以下将对如何对集群技术进行简化给出两点方法：1.从群体初始化方面入手。2.从群体运动方面入手。,参考资料：人工智能游戏编程真言-清华大学出版社游戏开发中的人工智能-东南大学出版社游戏设计概论清华大学出版社参考网站：http:/,初始化,初始化智能体最简单的方法就是把它们从幕后搬出来。让集群智能体从天花板上落到玩家头上
8、，让它们从墙上漩涡式地钻出来，或者大群智能体生物从深谷裂口中瀑布般地涌出来（最好是在玩家占领的地盘上）都是最大限度利用集群生物出场的方法。集群生物也可以用“爆炸”的方式进入场景的某个区域，当某个容器被破坏（如笼子）或者被打开（如棺材）。,返回,运动,对每一个活动的智能体保存其当前的位置，根据其速度和运动方向更新x，z坐标，并且根据重力增加下落速度时修改其y坐标。计算智能体的位置和目标对象的位置之间的差异，给出x，y和z坐标的增量。再算出从目标对象到智能体的相对夹角（angle）（atan(dz,dx)-agent-yrot）。如果智能体是逃离目标对象（因为它的定时器timer大于某个特定值）,
9、angle取负值。如果玩家在距离智能体某个范围之内（用适当的距离检查，或者用简单的盒式冲突检测来节省时间），就认为玩家受到伤害。,如果智能体不是下落的，那么它的操纵方式和运动方向根据它在内层区域或外层区域分别按如下进行修正：外层区域：如果未到速度的最大值就增加智能体速度。每个智能体的最大速度应该不同。如果智能体的运动方向大致是正确的，给这个智能体的y-rotation一个小小的扰动否则就马上改变y-rotation，指向正确方向。内层区域：按照智能体的速度改变它的y-rotation，并且按照它的angle改变它的速度。这些改变背后方程组的本质确定了集群生物在目标对象周围运动的形式。,返回,B
10、resenham直线算法,Bresenham直线算法是用来描绘由两点所决定的直线的算法，它会算出一条线段在 n 维光栅上最接近的点。这个算法只会用到较为快速的整数加法、减法和位元移位，常用于绘制电脑画面中的直线。是计算机图形学中最先发展出来的算法。,返回,凝聚,凝聚意指我们想让所有单位都待在同一群体中，我们不要每个单位和群体分开，各走走的路。为了满足这项规则，每个单位都应该朝其邻近单位之平均位置前进。邻近单位的平均位置很容易计算，只要找出邻近单位后，其平均位置就是其各个位置的向量总和，再除以总邻近单位数。,Pave+=unitsj.vPosition;这一行将所有邻近单位的位置向量相加。Pav
11、e和vPosition是Vectort类的变量，此overloaded operator（重载运算符）会替我们做向量加法。DoUnitAI（）找出邻近单位并收集信息后，就可以使用群聚规则了。此段程序第一件事是检查邻近单位数量是否大于0.如果是，我们就能继续计算邻近单位的平均位置。做法是以所有邻近单位位置的向量总和Pave除以邻近单位数量N。最后一行就是实际计算满足凝聚规则的转向力。,凝聚,基本上，累加在FS.X的转向力是当前单位的方向，以及其邻近单位平均位置向量间的角度的线性函数，也就是说，如果角度大，则转向力也会相对较大；如果角度小，则转向力也会相对较小。这正是我们想要的。如果当前单位的方向
12、和邻近单位的平均位置的方向相距很远，我们会想让他做大幅度的转弯。如果其方向和邻近单位平均位置的方向不太远，我们只想对其方向做小范围的修正。,返回,对齐,对齐意指我们想让群聚中的所有单位都大致朝相同方向前进。为了满足这条规则，每个单位都应该在行进时，试着以等同其邻近单位平均方向的方向来前进。,中间以粗线表示单位是沿着和其相连的粗箭头方向进行的。另外和其相连的虚线箭头则代表其邻近单位的平均方向。因此，就此而言，以粗线表示的单位必须朝右侧行进。,我们可以利用每个单位的速度向量求出其方向。把每个单位的速度向量，换算成单位向量，就可以得出其方位向量。上面收集邻近单位方向数据的过程，那一行Vave+=Un
13、itsj.vVelocity;会把每个邻近单位的速度向量累加在Vave中，其做法类似于Pave累加位置过程。,这段代码计算了每个单位的对齐转向力。代码几乎和上面聚集差聚集规则一样。此处不再处理邻近单位的平均位置，而是把Vave 除以邻近单位数量N，先求出当前单位邻近单位的平均方向。所得结果储存在u中，并换算成单位向量，则为平均向量。,返回,就此例而言，转向力是当前单位方向，及其邻近单位平均方向间角度的线性函数。同意的，只要当前单位的方向，和其邻近单位的平均方向很接近，则只需稍微作调整。,分隔,分隔意指我们想让每个单位彼此间保持最小距离，即使根据凝聚和对齐规则，他们会试着靠近一点。我们不想让那些单位撞在一起，或者更糟的是，在某个巧合地点重合在一起。因此，我们要采用分隔手段，让每个单位和其视野内的邻近单位保持某一预定的最小分隔距离处理分隔的程序和处理凝聚及对齐的只有一点不同，因为就分隔而言，求算适当的转向力校正值时，我们必须逐一检视每个邻近单位，而不是使用所有邻近单位的某个平均值。,返回,
