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