目录
学习资源参考：
算法简介
计算机专家克雷格 · 雷诺兹在1987年发表了一篇关于模拟鸟类集群行为的论文，论文中首次介绍了名为 Boids 的算法，随后这种算法快速被应用于电影或者游戏中，比如92年《蝙蝠侠归来》的蝙蝠群和企鹅群，98年《半条命》中的鸟型生物群中。
Boids算法是一种去中心化思想，它负责描述每个个体的行为规则，而不关心所谓的“集群”。“集群”是它所表现出来的外观而非最小规则。对于每个个体，只遵循三条简单的规则：
- 分离规则：个体会自主移动避开拥挤处
- 对齐规则：个体会朝着周围同伴的平均移动方向前进
- 聚集规则：个体会朝着周围同伴的平均位置移动
规则详解
分离规则
集群中个体的一个关键行为就是向着远离周围其他个体的趋势运动，就像磁铁的同极相斥，离得越近这种斥力就会越大。这是个体间不会发生碰撞和重叠的基础。
分离规则的代码可以这样写：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
// 分离规则
Vector2D separation(const std::vector<Boid>& boids)
{
Vector2D separation(0, 0);
for (const Boid& b : boids)
{
float distance = (b.position - position).length();
if (distance > 0 && distance < separation_distance)
{
Vector2D diff = position - b.position;
separation = separation + diff * (1.0f / distance);
}
}
return separation;
}
|
对齐规则
“对齐”在群体模拟中起到了控制个体移动转向的作用。从直觉上，我们根据判断一个群体是否具有一致的行动朝向，来判断它是否是一个“集群”还是“乌合之众”。
对齐规则可以这样实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
// 对齐规则
Vector2D alignment(const std::vector<Boid>& boids)
{
Vector2D avg_velocity(0, 0);
int total_neighbors = 0;
for (const Boid& b : boids)
{
float distance = (b.position - position).length();
if (distance > 0 && distance < neighbor_distance)
{
avg_velocity = avg_velocity + b.velocity;
total_neighbors++;
}
}
if (total_neighbors > 0)
{
avg_velocity = avg_velocity * (1.0f / total_neighbors);
return avg_velocity - velocity;
}
return Vector2D(0, 0);
}
|
聚集规则
与分离规则相反，聚集规则是一种凝聚力，像磁铁的异性相吸。它保证了集群中的个体不会因为分离规则而过度分散，导致无法产生“邻居个体”。
聚集规则的实现代码：我们先得到个体邻居包围得到的质心位置，然后让它拥有向着质心移动的趋势，从而产生聚集的效果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
// 聚集规则
Vector2D cohesion(const std::vector<Boid>& boids)
{
Vector2D center_of_mass(0, 0);
int total_neighbors = 0;
for (const Boid& b : boids)
{
float distance = (b.position - position).length();
if (distance > 0 && distance < neighbor_distance)
{
center_of_mass = center_of_mass + b.position;
total_neighbors++;
}
}
if (total_neighbors > 0)
{
center_of_mass = center_of_mass * (1.0f / total_neighbors);
return (center_of_mass - position);
}
return Vector2D(0, 0);
}
|
- 这三条规则互相博弈，仅依靠最基础的数学和向量运算，就让简单个体涌现出复杂的 群体智慧。
- 在不同情景下的集群模拟，本质上是对这三条规则的“参数微调”。比如鱼群，我们常需要模拟水中阻力导致的间距不规则，这可以通过降低“对齐规则”强度实现，让鱼群在拐弯时出现“尾部延迟”的真实感；如一些鼠群或者僵尸群，则可以加大“聚集规则”的权重，让怪群可以如流水般快速绕过障碍物；在一些需要打造较强科技感的场景中，我们可以让群体尽量保持尖锐的三角锥形态，这可以通过在聚集规则之上添加形状进行约束。
完整实现
实现思路和流程
创建 Boid 类
对于每一个个体而言，它需要三个成员变量：位置、速度和加速度，这三者都是一个二维向量（此项目实现2D图像Boids算法）。
于是 Boid 类可以这样写：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
// boid.js
class Boid
{
constructor()
{
this.position = createVector(width / 2, height / 2); // boid的位置
this.velocity = p5.Vector.random2D(); // boid的速度
this.velocity.setMag(random(0.5, 1.5 )) // 设置群体中每个boid的速度不同
this.acceleration = createVector(); // boid的加速度
}
update(){
this.position.add(this.velocity);
this.velocity.add(this.acceleration);
}
show(){
strokeWeight(16);
stroke(255);
point(this.position.x, this.position.y);
}
}
|
假设我们共有100个boid，那么在 sketch.js 中可以用一个数组来表示它们：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
// sketch.js
const flock = [];
function setup() {
createCanvas(640, 360);
for (let i = 0; i < 100; i++){
flock.push(new Boid());
}
}
function draw() {
background(51);
for (let boid of flock){
boid.show();
boid.update();
}
}
|
现在可以看到这样的效果：
“对齐规则”的实现
“对齐”是三个规则中最简单的，所以我们先来实现它。
实现思路：我们以个体boid为中心，检测以它为圆心一定距离为半径的圆，计算这个圆里的所有其他个体（邻居）的平均速度，这个“平均速度”就是目标boid需要转向的目标速度，从而可以得到这个boid转到目标速度所需要的“转向力”。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
// boid.js
align(boids){
let perceptionRadius = 50; // 检测半径为50像素的圆
let steering = createVector(); // boid待转向的速度
let total = 0; // 邻居数量
for (let other of boids){
let d = dist(this.position.x, this.position.y, other.position.x, other.position.y);
if (other != this && d < perceptionRadius) {
steering.add(other.velocity); // 把邻居的速度加起来
total++;
}
}
if (total > 0){
steering.div(total); // 计算邻居们的平均速度（小群体的目标速度）
steering.setMag(this.maxSpeed); // 限制平均速度
steering.sub(this.velocity); // 二维向量计算：目标速度 - 当前boid速度 = 当前boid需要转向的速度
steering.limit(this.maxForce); // 将转向力限制在一定范围内
}
return steering;
}
flock(boids){
let alignment = this.align(boids);
this.acceleration = alignment; // 将对齐行为的转向力赋值为当前加速度（假设质量为1）
// 力 = 加速度 * 质量，此处质量为1，所以加速度其实就是boid朝向目标朝向的转向力
}
|
再给集群加上“飞进飞出”的效果：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
// boid.js
edges(){
if (this.position.x > width){
this.position.x = 0;
} else if (this.position.x < 0){
this.position.x = width;
}
if (this.position.y > height){
this.position.y = 0;
} else if (this.position.y < 0){
this.position.y = height;
}
}
|
于是可以得到这样的“对齐”效果：
“聚集规则”的实现
这一规则的实现和“对齐规则”类似，只不过我们不需要邻居们的平均速度了，取而代之，需要邻居们的平均位置作为“目标位置”来进行实际的移动“
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
cohesion(boids){
let perceptionRadius = 50;
let steering = createVector();
let total = 0;
for (let other of boids){
let d = dist(this.position.x, this.position.y, other.position.x, other.position.y);
if (other != this && d < perceptionRadius) {
steering.add(other.position); // 此处需要计算位置而非速度了
total++;
}
}
if (total > 0){
steering.div(total); // 计算邻居们的平均位置（目标位置）
steering.sub(this.position); // 目标位置 - 当前boid位置 = boid需要运动的位移
steering.setMag(this.maxSpeed); // 限制平均速度
steering.sub(this.velocity); // 二维向量计算：目标速度 - 当前boid速度 = 当前boid需要转向的速度
steering.limit(this.maxForce); // 将聚集力限制在一定范围内
}
return steering;
}
|
在”聚集规则“中，maxForce 不是特别重要，重要的是 perceptionRadius 的数值大小，决定了boid能够”看到多大范围“，从而产生聚集行为。
将两条规则结合起来也非常简单，使用初中物理知识：作用在一个物体上的作用力等于两个作用力之和。
1
2
3
4
5
6
7
8
9
10
|
// boid.js
flock(boids){
let alignment = this.align(boids);
let cohesion = this.cohesion(boids);
// 将两个力相加，得到共同作用力
this.acceleration.add(alignment);
this.acceleration.add(cohesion);
}
|
在两条规则的加持下，集群的运动轨迹目前是这样的：
“分离规则”的实现
在分离规则下，我们可以这样得到boid想要的速度：
于是，separation 是 cohesion 的相反的过程，所以我们可以基于 cohesion 这样来写 separation:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
// boid.js
separation(boids){
let perceptionRadius = 50;
let steering = createVector();
let total = 0;
for (let other of boids){
let d = dist(this.position.x, this.position.y, other.position.x, other.position.y);
if (other != this && d < perceptionRadius) {
let diff = p5.Vector.sub(this.position, other.position); // boid的位置-邻居的位置，得到boid想要的速度
diff.div(d); // 距离越远的邻居对boid产生的影响越小，距离越近影响越大
steering.add(diff);
total++;
}
}
if (total > 0){
steering.div(total);
steering.setMag(this.maxSpeed);
steering.sub(this.velocity);
steering.limit(this.maxForce);
}
return steering;
}
|
最终得到“分离规则”的效果是这样的：
至此，简单版的boids算法已经实现，我们可以通过调节三条规则的权重来得到想要的集群行为：
完整源码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
|
// boid.js
class Boid
{
constructor()
{
this.position = createVector(random(width), random(height)); // boid的初始位置
this.velocity = p5.Vector.random2D(); // boid的速度
this.velocity.setMag(random(0.5, 2)) // 设置flock中每个boid的速度不同
this.acceleration = createVector(); // boid的加速度
this.maxForce = 0.2; // boid的最大转向力
this.maxSpeed = 2; // boid的最大速度
}
// 在屏幕上显示“飞进飞出”的效果
edges(){
if (this.position.x > width){
this.position.x = 0;
} else if (this.position.x < 0){
this.position.x = width;
}
if (this.position.y > height){
this.position.y = 0;
} else if (this.position.y < 0){
this.position.y = height;
}
}
align(boids){
let perceptionRadius = 50; // 检测半径为50像素的圆
let steering = createVector(); // boid待转向的速度
let total = 0; // 邻居数量
for (let other of boids){
let d = dist(this.position.x, this.position.y, other.position.x, other.position.y);
if (other != this && d < perceptionRadius) {
steering.add(other.velocity); // 把邻居的速度加起来
total++;
}
}
if (total > 0){
steering.div(total); // 计算邻居们的平均速度（小群体的目标速度）
steering.setMag(this.maxSpeed); // 限制平均速度
steering.sub(this.velocity); // 二维向量计算：目标速度 - 当前boid速度 = 当前boid需要转向的速度
steering.limit(this.maxForce); // 将转向力限制在一定范围内
}
return steering;
}
cohesion(boids){
let perceptionRadius = 100;
let steering = createVector();
let total = 0;
for (let other of boids){
let d = dist(this.position.x, this.position.y, other.position.x, other.position.y);
if (other != this && d < perceptionRadius) {
steering.add(other.position); // 此处需要计算位置而非速度了
total++;
}
}
if (total > 0){
steering.div(total); // 计算邻居们的平均位置（目标位置）
steering.sub(this.position); // 目标位置 - 当前boid位置 = boid需要运动的位移
steering.setMag(this.maxSpeed); // 限制平均速度
steering.sub(this.velocity); // 二维向量计算：目标速度 - 当前boid速度 = 当前boid需要转向的速度
steering.limit(this.maxForce); // 将聚集力限制在一定范围内
}
return steering;
}
separation(boids){
let perceptionRadius = 50;
let steering = createVector();
let total = 0;
for (let other of boids){
let d = dist(this.position.x, this.position.y, other.position.x, other.position.y);
if (other != this && d < perceptionRadius) {
let diff = p5.Vector.sub(this.position, other.position); // boid的位置-邻居的位置，得到boid想要的速度
diff.div(d); // 距离越远的邻居对boid产生的影响越小，距离越近影响越大
steering.add(diff);
total++;
}
}
if (total > 0){
steering.div(total);
steering.setMag(this.maxSpeed);
steering.sub(this.velocity);
steering.limit(this.maxForce);
}
return steering;
}
flock(boids){
let alignment = this.align(boids);
let cohesion = this.cohesion(boids);
let separation = this.separation(boids);
// 设置规则权重
alignment.mult(alignSlider.value());
cohesion.mult(cohesionSlider.value());
separation.mult(separationSlider.value());
// 将两个力相加，得到共同作用力
this.acceleration.add(alignment);
this.acceleration.add(cohesion);
this.acceleration.add(separation);
}
update(){
this.position.add(this.velocity);
this.velocity.add(this.acceleration);
this.velocity.limit(this.maxSpeed);
this.acceleration.set(0, 0); // 重置加速度（不让加速度越来越快）
}
show()
{
strokeWeight(8);
stroke(255);
point(this.position.x, this.position.y);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
// sketch.js
const flock = [];
let alignSlider, cohesionSlider, separationSlider
function setup() {
createCanvas(640, 360);
alignSlider = createSlider(0, 5, 1, 0.1);
cohesionSlider = createSlider(0, 5, 1, 0.1);
separationSlider = createSlider(0, 5, 1, 0.1);
for (let i = 0; i < 100; i++){
flock.push(new Boid());
}
}
function draw() {
background(51);
for (let boid of flock){
boid.edges();
boid.flock(flock);
boid.show();
boid.update();
}
}
|
