本文内容：群聚方法是 A-life 算法的实例。 A-life 算法除了可以做出效果很好的群聚行为外，也是高级群体运动的基础。

群聚

通常在游戏中，有些非玩家角色必须群聚移动，而不是个别行动。举个例子，假设你在写角色扮演游戏，在主城镇外有一片绵羊的草地，如果你的绵羊是一整群的在吃草，而不是毫无目的的在闲逛，看起来会更真实些。

这种群体行为的核心就是基本的群聚算法，本章要详谈基本群聚算法，教你如何修改算法，用来处理诸如避开障碍物之类的情况。本章接下来将以“单位”代指组成群体的个别实体，例如：绵羊、鸟、等等。

基本群聚

基本的群聚算法来自于Craig Reynolds在1987年发表的论文《Flocks，Herds and Schools:A Distributed Behavioral Model》。在论文中，他提出基本群聚算法，用以仿真整群的鸟、鱼或其他生物。

算法的三个规则：

凝聚：每个单位都往其邻近单位的平均位置行动。
对齐：每个单位行动时，都要把自己对齐在其邻近单位的平均方向上。
分割：每个单位行动时，要避免撞上其邻近单位。

从这三条语句可以得知，每个单位都必须有比如运用转向力行进的能力。此外，每个单位都必须得知其局部的周遭情况，必须知道邻近单位在哪里、它们的方向如何以及它们和自身有多接近。

单位视野：

图4-1 是一个单位（图中用粗线表示的那个）以 r 为半径画弧而定出其可见视野的说明。任何其他单位落入这个弧内，都能被这个单位看见。运用群聚规则时，这些可视的单位就会有用，而其他单位都会被忽略。弧由两个参数定义：弧半径和角度 θ，这两个参数会影响最后的群聚行动。

弧半径：

较大的弧半径会让单位看到群体中更多的伙伴，从而产生更强的群体（也更多了）。也就是说，群体没有分裂成小群体的倾向，因为每个单位都可以看见多数邻近单位或全部邻近单位，再据此前进。另一方面，较小的半径会让整个群体分裂，形成较小群体的可能性较高。

角度 θ：

角度 θ 量定了每个单位的视野范围。最宽广的视野是360度，不过我们一般不这样做，因为这样最后得到的群聚行为可能会失真。常用的视野范围类似于图4-1 中，每个单位的身后都有一块看不见的区域。一般而言，视野宽广的话，如图4-2 左侧所示，视野角度约为270度，会得到组织良好的群体。视野较窄的话，如图4-2 右侧所示，视野角度约为45度，得到的群体像蚂蚁那样沿着单一路径行进。

宽视野和窄视野都有其作用。例如，如果你正在仿真一群喷射战机，可能会用宽视野，如果仿真一支军队鬼鬼祟祟地跟踪某人时，你也许会用窄视野，使其前后排成一条线。

群聚实例

我们打算仿真大约20个单位，以群聚的方式移动，避开圆形的物体，群聚中的诸多单位和玩家（另一个飞行器）的互动就是去追玩家。

行进模式

这个实例考虑的是以物理机制为基础的范例，把每个单位视为刚体，通过在每个单位的前端施加转向力，来保证群聚的行进模式。每条规则都会影响施加的力，最终施加的力和方向是这些规则影响的综合。另外，需要考虑两件事：首先，要控制好每条规则贡献的转向力；其次，要调整行进模式，以确保每个单位都获得平衡。

对于避开规则：为了让单位不会彼此撞上，且单位根据对齐和凝聚规则而靠在一起。当单位彼此间距离够宽时，避开规则的转向力贡献就要小一点；反之，避开规则的转向力贡献就要大一些。对于避开用的反向力，一般使用反函数就够用了，分隔距离越大，得出的避开用转向力越小；分隔距离越小，得出的避开用转向力越大。

对于对齐规则：考虑当前单位的当前方向，与其邻近单位间平均方向间的角度。如果该角度较小，我们只对其方向做小幅度调整，然而，如果角度较大，就需要较大的调整。为了完成这样的任务，可以把对齐用的转向力贡献，设定成和该单位方向及其邻近单位平均方向间的角度成正比。

邻近单位

凝聚，对齐，分隔三个规则要起作用的前提是侦测每个当前单位的邻近单位。邻近单位就是当前单位视野范围内的单位，需要从图4-1所示的视野角度和视野半径两方面进行判断。

由于群体中单位所形成的排列会随时变动，因此，游戏循环每运行一轮时，每个单位都必须更新其视野。

在示例 AIDemo4-1中，你会发现一个名为 UpdateSimulation( ) 的函数，每次走过游戏循环或仿真运算循环时，就会被调用。这个函数的责任是更新每个单位的位置并把每个单位画到画面显示缓冲区内。

例4-1 是此例的  UpdateSimulation( )  函数。

//例4-1：UpdateSimulation()函数

void    UpdateSimulation(void)
{
    double  dt = _TIMESTEP;
    int     i;

    // 初始化后端缓冲区
    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 < 0) Units[0].vPosition.x = _WINWIDTH;
    if(Units[0].vPosition.y > _WINHEIGHT) Units[0].vPosition.y = 0;
    if(Units[0].vPosition.y < 0) Units[0].vPosition.y = _WINHEIGHT;

    // 更新计算机控制的单位
    for(i=1; i<_MAX_NUM_UNITS; i++)
    {       
        DoUnitAI(i);

        Units[i].UpdateBodyEuler(dt);

        if(FrameCounter >= _RENDER_FRAME_COUNT)
        {
            if(Units[i].Leader)
                DrawCraft(Units[i], RGB(255,0,0));
            else {
                if(Units[i].Interceptor)
                    DrawCraft(Units[i], RGB(255,0,255));        
                else
                    DrawCraft(Units[i], RGB(0,0,255));
            }
        }

        if(Units[i].vPosition.x > _WINWIDTH) Units[i].vPosition.x = 0;
        if(Units[i].vPosition.x < 0) Units[i].vPosition.x = _WINWIDTH;
        if(Units[i].vPosition.y > _WINHEIGHT) Units[i].vPosition.y = 0;
        if(Units[i].vPosition.y < 0) Units[i].vPosition.y = _WINHEIGHT;     
    } 

    //把后端缓冲区复制到屏幕上
    if(FrameCounter >= _RENDER_FRAME_COUNT) {
        CopyBackBufferToWindow();
        FrameCounter = 0;
    }  else
        FrameCounter++;
}1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465

UpdateSimulation( ) 完成的是平常的工作，清除即将绘制图像的后端缓冲区，处理玩家控制的单位的互动行为，更新计算机控制的单位，把一切都绘制进后端缓冲区，做好之后，再把后端缓冲区复制到屏幕上。UpdateSimulation( ) 会以循环走遍计算机控制单位的数组，对每个单位而言，都会调用另一个名为 DoUnitAI( ) 的函数。

DoUnitAI( ) 函数处理一切和计算机控制单位的移动有关的事。所有群聚规则都在此函数内实现。例4-2 是 DoUnitAI( ) 开头的一小部分。

//例4-2：DoUnitAI() 初始化

void    DoUnitAI(int i)
{

        int     j;
        int     N;     //邻近单位数量
        Vector  Pave;  //平均位置向量
        Vector  Vave;  //平均速度向量
        Vector  Fs;    //总转向力
        Vector  Pfs;   //Fs施加的位置
        Vector  d, u, v, w;
        double  m;
        int     Nf;
        bool    InView;
        bool    DoFlock = WideView || LimitedView || NarrowView;
        int     RadiusFactor;

        // 初始化
        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;

        …12345678910111213141516171819202122232425262728

参数 i 代表当前正在处理的单位的数组索引值，我们要收集这个单位所有邻近单位的数据，然后再实现群聚规则。变量 j 代表 Units 数组中，其他单位的数组索引值。这些是 Units[i] 潜在的邻近单位。

N 代表邻近单位的数目，这些数目包含在当前正在处理的单位的视野内。Pave 和 Vave 分别存放的是 N 个邻近单位的