引言
Flocking（群体行为模拟）是经典的群体智能演示，最早由Craig Reynolds在1986年提出Boids算法。它通过三条简单规则——分离（Separation）、对齐（Alignment）、聚合（Cohesion）——模拟鸟群、鱼群等自然群体的涌现行为。本文用Java实现完整的Boids模拟系统，涵盖空间分区优化、障碍规避与领导者跟随扩展。
Boids三条核心规则
设每个Boid的位置为 p，速度为 v，感知半径为 R：
- 分离（Separation）：避免与邻居碰撞。对距离小于
d_sep的邻居，产生排斥力。 - 对齐（Alignment）：与邻居保持相近的速度方向。取邻居平均速度作为目标方向。
- 聚合（Cohesion）：向邻居的中心位置移动。取邻居质心作为吸引目标。
每条规则生成一个加速度修正向量，加权叠加后更新速度与位置。
// 核心公式示意
Vector sep = separate(neighbors).mul(w_sep);
Vector ali = align(neighbors).mul(w_ali);
Vector coh = cohesion(neighbors).mul(w_coh);
Vector acc = sep.add(ali).add(coh);
velocity = velocity.add(acc).limit(maxSpeed);
position = position.add(velocity);
空间分区优化
当Boid数量 N 较大时，O(N²) 的邻居查询成为瓶颈。采用均匀网格（Spatial Hashing）将空间划分为格子，每个Boid只需查询自身所在格子及相邻8个格子中的邻居，将复杂度降至 O(N)。
Java实现
import java.util.*;
/**
* Boids群体智能模拟
*/
public class BoidsSimulation {
private List<Boid> boids;
private double width, height;
private double cellSize;
private Map<Long, List<Boid>> grid; // 空间哈希网格
private Random random;
static class Vector {
double x, y;
Vector(double x, double y) { this.x = x; this.y = y; }
Vector add(Vector v) { return new Vector(x + v.x, y + v.y); }
Vector sub(Vector v) { return new Vector(x - v.x, y - v.y); }
Vector mul(double s) { return new Vector(x * s, y * s); }
double mag() { return Math.sqrt(x * x + y * y); }
Vector normalize() {
double m = mag();
if (m == 0) return new Vector(0, 0);
return new Vector(x / m, y / m);
}
Vector limit(double max) {
if (mag() > max) return normalize().mul(max);
return this;
}
double dist(Vector v) {
double dx = x - v.x, dy = y - v.y;
return Math.sqrt(dx * dx + dy * dy);
}
}
static class Boid {
Vector pos, vel, acc;
double maxSpeed = 4;
double maxForce = 0.1;
double perception = 50; // 感知半径
Boid(double x, double y) {
this.pos = new Vector(x, y);
this.vel = new Vector(Math.random() * 2 - 1, Math.random() * 2 - 1);
this.acc = new Vector(0, 0);
}
void applyForce(Vector force) {
acc = acc.add(force);
}
void update() {
vel = vel.add(acc).limit(maxSpeed);
pos = pos.add(vel);
acc = new Vector(0, 0);
}
void wrap(double w, double h) {
if (pos.x < 0) pos.x += w;
if (pos.x > w) pos.x -= w;
if (pos.y < 0) pos.y += h;
if (pos.y > h) pos.y -= h;
}
}
public BoidsSimulation(int count, double w, double h) {
this.width = w;
this.height = h;
this.cellSize = 50;
this.random = new Random();
this.boids = new ArrayList<>();
for (int i = 0; i < count; i++) {
boids.add(new Boid(random.nextDouble() * w, random.nextDouble() * h));
}
}
/**
* 构建空间哈希网格
*/
private void buildGrid() {
grid = new HashMap<>();
for (Boid b : boids) {
long key = getCellKey(b.pos);
grid.computeIfAbsent(key, k -> new ArrayList<>()).add(b);
}
}
private long getCellKey(Vector p) {
long cx = (long) (p.x / cellSize);
long cy = (long) (p.y / cellSize);
return (cx << 32) | (cy & 0xffffffffL);
}
/**
* 获取邻居（仅查询相邻格子）
*/
private List<Boid> getNeighbors(Boid boid) {
List<Boid> neighbors = new ArrayList<>();
long cx = (long) (boid.pos.x / cellSize);
long cy = (long) (boid.pos.y / cellSize);
for (int dx = -1; dx <= 1; dx++) {
for (int dy = -1; dy <= 1; dy++) {
long key = ((cx + dx) << 32) | ((cy + dy) & 0xffffffffL);
List<Boid> cell = grid.get(key);
if (cell != null) {
for (Boid other : cell) {
if (other != boid && boid.pos.dist(other.pos) < boid.perception) {
neighbors.add(other);
}
}
}
}
}
return neighbors;
}
/**
* 分离：避免碰撞
*/
private Vector separation(Boid boid, List<Boid> neighbors) {
Vector steer = new Vector(0, 0);
int count = 0;
double desiredSeparation = 25;
for (Boid other : neighbors) {
double d = boid.pos.dist(other.pos);
if (d > 0 && d < desiredSeparation) {
Vector diff = boid.pos.sub(other.pos).normalize().mul(1.0 / d);
steer = steer.add(diff);
count++;
}
}
if (count > 0) {
steer = steer.mul(1.0 / count).normalize().mul(boid.maxSpeed);
steer = steer.sub(boid.vel).limit(boid.maxForce);
}
return steer;
}
/**
* 对齐：速度方向趋同
*/
private Vector alignment(Boid boid, List<Boid> neighbors) {
Vector sum = new Vector(0, 0);
for (Boid other : neighbors) sum = sum.add(other.vel);
if (!neighbors.isEmpty()) {
sum = sum.mul(1.0 / neighbors.size()).normalize().mul(boid.maxSpeed);
return sum.sub(boid.vel).limit(boid.maxForce);
}
return new Vector(0, 0);
}
/**
* 聚合：向质心移动
*/
private Vector cohesion(Boid boid, List<Boid> neighbors) {
Vector sum = new Vector(0, 0);
for (Boid other : neighbors) sum = sum.add(other.pos);
if (!neighbors.isEmpty()) {
sum = sum.mul(1.0 / neighbors.size());
Vector desired = sum.sub(boid.pos).normalize().mul(boid.maxSpeed);
return desired.sub(boid.vel).limit(boid.maxForce);
}
return new Vector(0, 0);
}
/**
* 障碍规避：向目标点移动的同时避开障碍
*/
private Vector seek(Boid boid, Vector target) {
Vector desired = target.sub(boid.pos).normalize().mul(boid.maxSpeed);
return desired.sub(boid.vel).limit(boid.maxForce);
}
/**
* 模拟一步
*/
public void step() {
buildGrid();
for (Boid b : boids) {
List<Boid> neighbors = getNeighbors(b);
Vector sep = separation(b, neighbors).mul(1.5);
Vector ali = alignment(b, neighbors).mul(1.0);
Vector coh = cohesion(b, neighbors).mul(1.0);
b.applyForce(sep);
b.applyForce(ali);
b.applyForce(coh);
}
for (Boid b : boids) {
b.update();
b.wrap(width, height);
}
}
public void printState(int limit) {
System.out.println("Boids状态（前" + limit + "个）：");
for (int i = 0; i < Math.min(limit, boids.size()); i++) {
Boid b = boids.get(i);
System.out.printf(" [%d] pos=(%.1f,%.1f) vel=(%.2f,%.2f)\n",
i, b.pos.x, b.pos.y, b.vel.x, b.vel.y);
}
}
public static void main(String[] args) {
BoidsSimulation sim = new BoidsSimulation(100, 800, 600);
for (int step = 0; step < 100; step++) {
sim.step();
if (step % 20 == 0) {
System.out.println("Step " + step);
sim.printState(5);
}
}
System.out.println("模拟完成");
}
}
参数调优与涌现行为
Boids的群体形态由三条规则的权重比值决定：
– 高分离权重：群体分散，个体间距大，呈松散群落。
– 高对齐权重：群体方向高度统一，呈队列或迁徙形态。
– 高聚合权重：群体紧密聚集，呈球状或漩涡形态。
通过动态调整权重（如受惊时分离权重骤增），可模拟捕食者驱赶、领导者引导等复杂场景。
复杂度分析
- 朴素实现：每步
O(N²)邻居查询。 - 空间哈希优化：每步
O(N)平均复杂度，网格查询为O(1)。 - 内存占用：
O(N)存储Boid状态，O(N/cellSize²)网格开销。
扩展方向
- ** 八叉树/BDTree**：三维空间下的高效邻居查询。
- ** 流场导航**：引入全局向量场引导群体沿特定路径移动。
- ** 多物种交互**：扩展为捕食-猎物模型，加入追逐与逃逸行为层。
