游戏开发中的人工智能（四）：群聚
接上文游戏开发中的人工智能（三）：移动模式
本文内容：群聚方法是A-life算法的实例。A-life算法除了可以做出效果很好的群聚行为外，也是高级群体运动的基础。
通常在游戏中，有些非玩家角色必须群聚移动，而不是个别行动。举个例子，假设你在写角色扮演游戏，在主城镇外有一片绵羊的草地，如果你的绵羊是一整群的在吃草，而不是毫无目的的在闲逛，看起来会更真实些。
这种群体行为的核心就是基本的群聚算法，本章要详谈基本群聚算法，教你如何修改算法，用来处理诸如避开障碍物之类的情况。本章接下来将以“单位”代指组成群体的个别实体，例如：绵羊、鸟、等等。
基本群聚
基本的群聚算法来自于CraigReynolds在1987年发表的论文《Flocks，HerdsandSchools:ADistributedBehavioralModel》。在论文中，他提出基本群聚算法，用以仿真整群的鸟、鱼或其他生物。
算法的三个规则：
•凝聚：每个单位都往其邻近单位的平均位置行动。•对齐：每个单位行动时，都要把自己对齐在其邻近单位的平均方向上。•分割：每个单位行动时，要避免撞上其邻近单位。
从这三条语句可以得知，每个单位都必须有比如运用转向力行进的能力。此外，每个单位都必须得知其局部的周遭情况，必须知道邻近单位在哪里、它们的方向如何以及它们和自身有多接近。
单位视野：
图4-1是一个单位（图中用粗线表示的那个）以r为半径画弧而定出其可见视野的说明。任何其他单位落入这个弧内，都能被这个单位看见。运用群聚规则时，这些可视的单位就会有用，而其他单位都会被忽略。弧由两个参数定义：弧半径和角度θ，这两个参数会影响最后的群聚行动。
弧半径：
较大的弧半径会让单位看到群体中更多的伙伴，从而产生更强的群体（也更多了）。也就是说，群体没有分裂成小群体的倾向，因为每个单位都可以看见多数邻近单位或全部邻近单位，再据此前进。另一方面，较小的半径会让整个群体分裂，形成较小群体的可能性较高。
角度θ：
角度θ量定了每个单位的视野范围。最宽广的视野是360度，不过我们一般不这样做，因为这样最后得到的群聚行为可能会失真。常用的视野范围类似于图4-1中，每个单位的身后都有一块看不见的区域。一般而言，视野宽广的话，如图4-2左侧所示，视野角度约为270度，会得到组织良好的群体。视野较窄的话，如图4-2右侧所示，视野角度约为45度，得到的群体像蚂蚁那样沿着单一路径行进。
宽视野和窄视野都有其作用。例如，如果你正在仿真一群喷射战机，可能会用宽视野，如果仿真一支军队鬼鬼祟祟地跟踪某人时，你也许会用窄视野，使其前后排成一条线。群聚实例
我们打算仿真大约20个单位，以群聚的方式移动，避开圆形的物体，群聚中的诸多单位和玩家（另一个飞行器）的互动就是去追玩家。
行进模式
这个实例考虑的是以物理机制为基础的范例，把每个单位视为刚体，通过在每个单位的前端施加转向力，来保证群聚的行进模式。每条规则都会影响施加的力，最终施加的力和方向是这些规则影响的综合。另外，需要考虑两件事：首先，要控制好每条规则贡献的转向力；其次，要调整行进模式，以确保每个单位都获得平衡。
对于避开规则：为了让单位不会彼此撞上，且单位根据对齐和凝聚规则而靠在一起。当单位彼此间距离够宽时，避开规则的转向力贡献就要小一点；反之，避开规则的转向力贡献就要大一些。对于避开用的反向力，一般使用反函数就够用了，分隔距离越大，得出的避开用转向力越小；分隔距离越小，得出的避开用转向力越大。
对于对齐规则：考虑当前单位的当前方向，与其邻近单位间平均方向间的角度。如果该角度较小，我们只对其方向做小幅度调整，然而，如果角度较大，就需要较大的调整。为了完成这样的任务，可以把对齐用的转向力贡献，设定成和该单位方向及其邻近单位平均方向间的角度成正比。
邻近单位
凝聚，对齐，分隔三个规则要起作用的前提是侦测每个当前单位的邻近单位。邻近单位就是当前单位视野范围内的单位，需要从图4-1所示的视野角度和视野半径两方面进行判断。
由于群体中单位所形成的排列会随时变动，因此，游戏循环每运行一轮时，每个单位都必须更新其视野。
在示例AIDemo4-1中，你会发现一个名为UpdateSimulation()的函数，每次走过游戏循环或仿真运算循环时，就会被调用。这个函数的责任是更新每个单位的位置并把每个单位画到画面显示缓冲区内。
例4-1是此例的UpdateSimulation()函数。
//例4-1：UpdateSimulation()函数voidUpdateSimulation(void){doubledt=_TIMESTEP;inti;//初始化后端缓冲区if(FrameCounter>=_RENDER_FRAME_COUNT){ClearBackBuffer();DrawObstacles();}//更新玩家控制的单位（Units[0]）Units[0].SetThrusters(false,false,1);Units[0].SetThrusters(false,false,1);if(IsKeyDown(VK_RIGHT))Units[0].SetThrusters(true,false,0.5);if(IsKeyDown(VK_LEFT))Units[0].SetThrusters(false,true,0.5);Units[0].UpdateBodyEuler(dt);if(FrameCounter>=_RENDER_FRAME_COUNT)DrawCraft(Units[0],RGB(0,255,0));if(Units[0].vPosition.x>_WINWIDTH)Units[0].vPosition.x=0;if(Units[0].vPosition.x_WINHEIGHT)Units[0].vPosition.y=0;if(Units[0].vPosition.y_WINWIDTH)Units[i].vPosition.x=0;if(Units[i].vPosition.x_WINHEIGHT)Units[i].vPosition.y=0;if(Units[i].vPosition.y=_RENDER_FRAME_COUNT){CopyBackBufferToWindow();FrameCounter=0;}elseFrameCounter++;}UpdateSimulation()完成的是平常的工作，清除即将绘制图像的后端缓冲区，处理玩家控制的单位的互动行为，更新计算机控制的单位，把一切都绘制进后端缓冲区，做好之后，再把后端缓冲区复制到屏幕上。UpdateSimulation()会以循环走遍计算机控制单位的数组，对每个单位而言，都会调用另一个名为DoUnitAI()的函数。
DoUnitAI()函数处理一切和计算机控制单位的移动有关的事。所有群聚规则都在此函数内实现。例4-2是DoUnitAI()开头的一小部分。
//例4-2：DoUnitAI()初始化voidDoUnitAI(inti){intj;intN;//邻近单位数量VectorPave;//平均位置向量VectorVave;//平均速度向量VectorFs;//总转向力VectorPfs;//Fs施加的位置Vectord,u,v,w;doublem;intNf;boolInView;boolDoFlock=WideView||LimitedView||NarrowView;intRadiusFactor;//初始化Fs.x=Fs.y=Fs.z=0;Pave.x=Pave.y=Pave.z=0;Vave.x=Vave.y=Vave.z=0;N=0;Pfs.x=0;Pfs.y=Units[i].fLength/2.0f;Nf=0;…参数i代表当前正在处理的单位的数组索引值，我们要收集这个单位所有邻近单位的数据，然后再实现群聚规则。变量j代表Units数组中，其他单位的数组索引值。这些是Units[i]潜在的邻近单位。
N代表邻近单位的数目，这些数目包含在当前正在处理的单位的视野内。Pave和Vave分别存放的是N个邻近单位的平均位置和速度向量。Fs代表施加到处理中单位的总转向力。Pfs代表转向力施加的位置，以固定于个体上的坐标表示。
d、u、v以及w用来存储计算函数时的各种向量值。向量值包含全局坐标系和局部坐标系的相对位置向量和方向向量。m是乘数变量，不是+1就是-1，用来指出我们所需的转向力施加点的方向，即目前处理的单位的右侧或是左侧。
InView是个标号，指出特定单位是否位于处理中单位的视野内。DoFlock也是个标号，指出是否使用群聚规则。此例中，你可以打开或关闭群聚规则，也可以实现三种不同的可见视野模式，以观察群聚行为。这些可见视野模式叫做WideView（宽广视野）、LimitedView（有限视野）以及NarrowView（狭窄视野）。最后，RadiusFactor代表的是图4-1中的r参数（即弧半径），每种可见视野模式的r值都不同，而且视野角度θ也不同。
完成初始化后，DoUnitAI()就会进入一个循环，收集当前单位周遭的邻近单位。
例4-3是DoUnitAI()中的一端，会检查所有的邻近单位并收集数据。到此时，会进入一个循环，即j循环中，在这个循环里面，Units数组的每个单位（Units[0]除外，这是玩家控制的单位（即被追逐的单位），另外，Units[1]也除外，这是当前单位，现在要找的是该单位的邻近单位）都会接受测试，以确认该单位是否在当前单位的视野内。如果是，其数据将被收集起来。
//例4-3：检查邻近单位并收集数据（DoUnitAI()中的一部分代码）…for(j=1;j0)&&(fabs(w.x)0);RadiusFactor=_LIMITEDVIEW_RADIUS_FACTOR;}if(NarrowView){InView=(((w.y>0)&&(fabs(w.x)0);RadiusFactor=_LIMITEDVIEW_RADIUS_FACTOR;}…狭窄视野
狭窄视野把每个单位可见的范围限制在正前方。
例4-6：狭窄视野的检查（依据视野角度θ）
//例4-6：狭窄视野的检查（依据视野角度θ）…if(NarrowView){InView=(((w.y>0)&&(fabs(w.x)0：邻近单位数量大于零Pave=Pave/N;//邻近单位的平均位置向量v=Units[i].vVelocity;//当前单位的速度向量v.Normalize();u=Pave-Units[i].vPosition;//邻近单位平均位置向量与当前单位向量的差值，相对位置向量u.Normalize();w.VRotate2D(-Units[i].fOrientation,u);if(w.x0)m=1;//相对位置向量（即u）在当前单位的左边，需要左转当前单位if(fabs(v*u)0)){Vave=Vave/N;u=Vave;//邻近单位的平均速度向量u.Normalize();v=Units[i].vVelocity;v.Normalize();w.VRotate2D(-Units[i].fOrientation,u);if(w.x0)m=1;if(fabs(v*u)0)&&(fabs(w.x)