Boids

Boids是模拟鸟群和其他生物群行行為的一种人工生命算法，由克雷格·雷诺兹（Craig Reynolds）于1986年开发，他介绍该算法的论文最初发表于1987年计算机协会（ACM）的SIGGRAPH会议上。Boids算法中个体行为遵循“分离、对齐、聚集”三条原则，其中“boids”一词为“bird-oid objects”（类鸟群对象）的缩写。该算法在面世后出现多种变体，并启发了之后的一系列群体智能算法，被广泛应用于计算机图形领域和电影特效等的制作中。

 原理 
和其他群行行為模拟一样，Boids算法也体现了涌现现象和去中心化，即群体的复杂性是单个个体简单相互作用的结果。克雷格·雷诺兹认为通过给单个个体不断施加条件，就能用个体的运动模拟出鸟群的整体运动，并针对个体的行为总结出三条原则：

 分离（Separation）：个体会避开群体拥挤处，以免与其他个体发生碰撞。
 对齐（Alignment）：个体会朝着周围个体的平均速度矢量方向前进。
 聚集（Cohesion）：个体会尽量相互靠近，朝着周围个体的中心位置移动。
雷诺兹还指出，真实的群行行为依赖于个体局部的世界观，所以在模拟中应当仅给个体提供有限而非全面的信息。

 变体 
Boids算法在以上三条原则的基础上还可以补充更为复杂的规则，进而产生不同的变体模型，比如使个体自动避开障碍物，引入使个体产生恐惧的天敌对象或使个体跟随的领导者对象等。作为群体智能领域的开创性研究，Boids算法也启发了后续一系列算法研究，包括粒子群优化（PSO）、蚁群算法（ACO）等。

需要注意的是，Boids并非最早的群行行为模拟算法，日本研究者青木一郎于1982年对鱼群行为进行了模拟研究，并提出类似模型。

 应用 
克雷格·雷诺兹于1986年使用自己和同事在Symbolics开发的一款图形软件工具编写了Boids算法的初代版本，之后该算法被广泛应用于计算机图形领域和电影特效等的制作中。1987年Symbolics制作的动画《》中首次使用了该算法，这部动画旨在宣传公司的产品和Boids算法。首次应用该算法的商业电影是蒂姆·伯顿的《蝙蝠侠归来》（1992年），电影中蝙蝠群和企鹅群场景是使用雷诺兹开发的Boids软件的修改版本制作的。类似Boids的算法也被用于《狮子王》（1994年）、《星際大戰》系列、《指环王》三部曲、《泰坦尼克号》（1997年）等电影中。1998年，雷诺兹因“对电影制作中三维计算机动画的发展作出的开创性贡献”获得奥斯卡科技成果奖。

除电影制作外，类似Boids的算法也被应用于电子游戏制作、人群模拟、和无人机（UAV）等领域。

 参见 

 群体智能
 人工生命
 粒子群优化
 进化算法
 蚁群算法


 参考资料 

 外部链接 

 克雷格·雷诺兹介绍Boids的页面
 基于Unity的鸟群群行行为3D实时模拟
 基于OpenGL的3D Boids模拟（存于互联网档案馆）
 基于JavaScript的Boids模拟

Category:人工生命
Category:人工生命模型
Category:算法
Category:群集智能
Category:最优化算法