Boids群体行为模拟｜冰岩分享
1992年蒂姆伯顿执导的电影《蝙蝠侠归来》是第一部包含计算机模拟群体行为的电影。安迪·科普拉（当时在VIFX工作）制作了蝙蝠群的画面。安德里亚·洛施（当时在Boss Films工作）和保罗·阿什当创作了企鹅军队行进的动画。
影片中的蝙蝠群与企鹅群呈现出逼真的群体行为，用于实现这一效果的软件Symbolics功不可没。实际上，该软件所基于的Boids集群模型早在1987年就被提出，并在接下来的几十年间持续影响着社会学、生物学、计算机科学等学科的发展。本文将简要介绍Boids集群模型的基本概念和实践中的优化方法。
Boids是什么
1987年，克雷格·雷诺兹（Craig W. Reynolds）发表了《兽群，鸟群和鱼群：分布式行为模型》（Flocks, herds and schools: A distributed behavioral model）。论文描述了一种模拟生物集群行为的模型，也是最早具有社会特征的生物智能体基模型（agent-based model），克雷格依据该模型开发的集群模拟程序与Boids同名。
词语“ boid”对应于“类似鸟的对象”（bird-oid object）的缩写形式，在复杂性科学（complexity science）中将克雷格的行为模型称为“Boids”，论文中亦将集群中的单个个体称为“boid”。
在自然世界中，动物集群没有一击而溃的弱点。一大群鸟迁徙的时候，即使几只鸟脱离了阵型，鸟群的总体动力学也不会变化。鸟群没有中心节点，没有自上而下的控制机制，但总体表现出受控的秩序。
克雷格的Boids模型正是以“自下而上的控制”为核心，为集群个体抽象出三个基本行为：队列（alignment）、分离（seperation）、与聚集（cohesion）。将这三种行为的按一定权重进行混合，可以让群体出现秩序化的社会性行为。
Boids的基本规则
在克雷格的模型中，个体具有有限的感知范围，感知范围内的其他个体称为“邻居”（neighbors）或“伙伴”（flockmates），下文中使用用第二种称呼。在没有加入障碍物回避的简单模型中，个体的行为仅受到其伙伴的影响。
队列（Alignment）
“队列”这个广为传播的翻译比较具有误导性，在复杂性科学中，这种行为被称为“一致”，这个称呼比前者更接近行为的本质：个体的速度大小与方向倾向于与伙伴保持一致，该行为不一定会带来广义上的队列行为。
float3 alignment = float3(0, 0, 0);
foreach(boid in flockmates){
alignmentDirection += boid.forward;
}
alignment /= flockmates.Length;
分离（Seperation）
个体有远离周围个体的趋势，防止相互碰撞。
float3 seperation = float3(0, 0, 0);
foreach(boid in flockmates){
float distance = (boid.position - this.position).magnitude;
seperation += (boid.position - this.position) / distance;
}
seperation /= flockmates.Length;
聚集（Cohesion）
个体有向伙伴平均位置移动的趋势。
float3 cohesionPosition = float3(0, 0, 0);
foreach(boid in flockmates){
cohesionPosition += boid.position;
}
cohesionPosition /= flockmates.Length;
简单实现
简单的实现思路中，每个个体都要遍历所有的个体，逐个判断与自己的距离并对感知范围内的个体进行计算。
每个个体都会携带此脚本，并按照一定的间隔时间执行，执行一次计算的过程被称为进行一次“思考“。
float3 alignment = float3(0, 0, 0);
float3 seperation = float3(0, 0, 0);
float3 cohesionPosition = float3(0, 0, 0);
foreach(boid in allBoids){
float distance = (boid.position - this.position).magnitude;
if(distance < senseDi && boid != this){
alignmentDirection += boid.forward;
seperation += (boid.position - this.position) / distance;
cohesionPosition += boid.position;
}
}
alignment /= flockmates.Length;
seperation /= flockmates.Length;
cohesionPosition /= flockmates.Length;
cohesion = cohesionPosition - this.position;
acceleration = alignment * weight1 + seperation * weight2 + cohesionPos * weight3;
Boids模型的进一步优化
按照以上规则实现的简易模型，配合繁琐的参数微调，已经可以达到非常不错的效果，群体可以像迁徙的鸟群一样稀疏，也可以像鱼群一样拥挤。但是简单模型并不是完备的，以下是一些让boids表现更真实的方法。
有限视角
Limited Field of View
为个体的视野加入视角参数，位于盲区的伙伴不影响自身行为。
向前加权的感知范围
Forward-weighted Sensitivity
在模拟对象是鸟群的时候，由于鸟类的生理构造，尽管它们具有300度左右的视角，但是两只眼睛重叠的视角仅有10到15度，因此鸟类具有立体深度的视野十分狭窄，但视觉优于两侧。
如图所示的是以某个个体为原点的坐标系，感知范围的下半部分是半圆，上半部分是长半轴随着速度增大而边长的椭圆。意味着当个体快速前进的时候，其对正前方的感知力更敏锐。
Pigeons in the Park by Craig W. Reynolds
分布式模型的性能优化
在Boids模型中，每个个体都要遍历整个群体，逐个判断是否在感知范围内，因此具有O(n^2)的性能，以下是三种从不同方面提升性能的优化方案。
这些方案的具体实现难以简要概括，因此仅作概念上的科普。
Compute Shader
加速集群的“思考”
在图形渲染的过程中，大量顶点与片元是被独立处理的，GPU的架构适应大量并行运算。现代GPU可以被设计为用来进行并行性较强的通用计算。与图形渲染无关通用计算也称为GPGPU（General Purpose GPU）。
Compute shader是一种可编程的着色器，独立于一般的渲染管线，可以单独用作GPGPU编程，也可以与图形渲染一起使用。用户在游戏脚本中指定传入shader的数据与所使用的shader，并开始计算（Dispatch Call），计算结束后从脚本获取结果。
该方法并未改变O(n^2)的复杂度，仅仅通过并发计算的方式加速集群进行一次思考的过程。
优点：
实现简单，性能提升显著
缺点：
至少需要GLES3.1/DX11/OpenGL4.3，DX10仅支持具有诸多限制的direct compute。 线程以线程组的形式分散在多个处理器上执行，线程组之间交互容易出问题。 CPU与GPU之间的通信存在性能瓶颈。
推荐阅读：
《Introduction to 3D Game Programming with DirectX 11》Chapter 12：The Compute Shader
GPU Instancing
加速渲染
Draw Call是CPU调用图形编程接口，来命令GPU进行渲染的操作。每次draw call前，CPU都需要检查渲染状态，向GPU发送渲染所需的数据等。与渲染前的准备工作相比，GPU渲染所用的时间很短，因此大量零散的draw call会造成CPU性能瓶颈。在渲染整个鸟群时，往往会绘制大量重复的模型，这正是“大量零散draw dall”的情形。
GPU instancing（aka Geometry Instancing）是一种在少量draw call的情况下，绘制大量具有相同mesh的物体的方法。GPU instancing每次draw call渲染一批具有相同顶点的物体，同一批绘制的物体可以具有不同的参数（位置，缩放，颜色等），比如在一次draw call中渲染100个位置，旋转，和颜色随机的长方体。
该方法并未改变O(n^2)的复杂度，而是减少了渲染所需的时间。
优点：
实现简单 从OpenGL2.0/GLES2.0/DX9.0就得到支持，移动平台广泛支持。
推荐阅读：
《GPU Gems 2》Chapter 3：Inside Geometry Instancing
Spatial Database
加速位置查询
以上两种方式都是通过加速某些过程来提升性能，但并未改变O(n^2)的复杂度。O(n^2)的复杂度来自于遍历所有个体来寻找伙伴的操作，最终被纳入计算的实际上只有感知范围内的伙伴而已。因此使用空间数据结构（spatial data structure / spatial database）储存所有个体是一个有效的优化方法。
使用空间数据结构储存所有个体，类似于对所有个体依据空间位置进行了“预排序”，一个个体可以快速访问所有与其可能相交的个体，而不用遍历整个集群。
以“Pigeons in the Park”使用的bin-lattice spatial subdivision为例，整个集群被网格分割储存在若干个“格子”中，每次查询地址会确定一个以个体视野为半径的圆，查询函数会确认所有与圆相交的网格，只有这些网格中的个体是可能在感知范围内的。
对于一个参数确定的boid模型中，集群对应地会有一个最大密度，因此对于固定半径的感知范围而言，能容纳的伙伴个数也是有限的，假定最大伙伴数为K，则在使用空间数据结构优化查询的情况下，整个集群“思考”一次的开销从O(n^2)变为O(Kn)。而在参数确定的集群中，K可以被视为常数，因此集群思考的开销从O(n^2)变为O(n)。
结语
Boids模型只是学者们对“集群模拟”这一主题探索的开始，克雷格在1999年发表《Steering Behaviors For Autonomous Characters 》，论述了更完备的自治体智能移动体模型。当然，这是另一个更复杂的故事了。
相信在阅读本文后，读者们对鸽子的思维和行为模式有了更深入的理解。