导入
集群算法是游戏编程中，经常会用到的一个算法，比如群体怪物的移动逻辑。而鸟群算法，又称为boids算法，是集群算法中一个十分优雅的算法，它不依赖集群中leader的移动逻辑，而是一种去中心化的集群算法。
正文
Boids鸟群算法只依赖于3个基本原则：
-
分离原则：计算附近Boids的排斥力，避免碰撞
-
对齐原则：计算附近Boids的平均速度方向，使群体运动一致
-
聚集原则：计算附近Boids的中心位置，产生向心力
分离原则
分离原则就是不让鸟群个体之间靠的太近，一旦小于一定的阈值，就产生排斥力。所谓排斥力，就是产生相反的速度变化，实际中一般使用加速度来表示。加速度不但收到分离原则的影响，还受到对齐原则和聚集原则的影响，说白了，就是三大原则计算结果就反应在加速度变量上，然后加速度应用在实际的当前速度上，就附加了这三个影响。
代码大致如下：
for other, dist_sq in self.neighbors:
dist = math.sqrt(dist_sq)
# 分离原则
if dist < 25:
diff = self.position - other.position
diff /= dist # 归一化
separation += diff
if total > 0:
separation = separation.normalize() * 0.1 if separation.length() > 0 else separation
self.acceleration += separation
对齐原则
对齐原则就是要跟周围集群中的其他个体尽量保持一个移动方向，因此就是要计算附近邻居的平均速度，然后附加在加速度上。
for other, dist_sq in self.neighbors:
dist = math.sqrt(dist_sq)
# 对齐原则
alignment += other.velocity
if total > 0:
alignment = (alignment / total).normalize() * 0.1
self.acceleration += alignment
聚集原则
聚集原则就是鸟群的每个个体，保持向鸟群中心靠拢的趋势，因此也就是计算鸟群的平均位置，然后往这个平均位置移动。
for other, dist_sq in self.neighbors:
dist = math.sqrt(dist_sq)
# 聚集原则
cohesion += other.position
if total > 0:
cohesion = ((cohesion / total) - self.position).normalize() * 0.05
self.acceleration += cohesion
给出一个简单的完整鸟群个体的代码：
class Boid:
def __init__(self, x, y):
self.position = pygame.Vector2(x, y)
self.velocity = pygame.Vector2(random.uniform(-1, 1), random.uniform(-1, 1))
self.velocity.scale_to_length(MAX_SPEED)
self.acceleration = pygame.Vector2(0, 0)
self.neighbors = [] # 存储附近Boid缓存
def update_neighbors(self, boids):
#预计算附近Boid
self.neighbors = []
for other in boids:
if other == self: continue
dist_sq = (self.position - other.position).length_squared()# 使用平方距离避免开方
if dist_sq < PERCEPTION_RADIUS**2:
self.neighbors.append((other, dist_sq))
def update(self):
self.velocity += self.acceleration
if self.velocity.length() > MAX_SPEED:
self.velocity.scale_to_length(MAX_SPEED)
self.position += self.velocity
self.acceleration *= 0
# 边界检查
self.position.x %= WIDTH
self.position.y %= HEIGHT
def apply_rules(self):
separation = pygame.Vector2(0, 0)
alignment = pygame.Vector2(0, 0)
cohesion = pygame.Vector2(0, 0)
total = len(self.neighbors)
# 使用预存的邻居数据
for other, dist_sq in self.neighbors:
dist = math.sqrt(dist_sq)
# 分离原则
if dist < 25:
diff = self.position - other.position
diff /= dist # 归一化
separation += diff
# 对齐原则
alignment += other.velocity
# 聚集原则
cohesion += other.position
if total > 0:
separation = separation.normalize() * 0.1 if separation.length() > 0 else separation
alignment = (alignment / total).normalize() * 0.1
cohesion = ((cohesion / total) - self.position).normalize() * 0.05
self.acceleration += separation + alignment + cohesion
def draw(self, screen):
angle = math.atan2(self.velocity.y, self.velocity.x)
points = [
self.position + pygame.Vector2(math.cos(angle), math.sin(angle)) * BOID_SIZE,
self.position + pygame.Vector2(math.cos(angle + 2.5), math.sin(angle + 2.5)) * BOID_SIZE/2,
self.position + pygame.Vector2(math.cos(angle - 2.5), math.sin(angle - 2.5)) * BOID_SIZE/2
]
pygame.draw.polygon(screen, BLUE, points)
可以看到三个原则十分简单清晰，可以说是优雅，但是效果却很不错，可以清晰的看到鸟群的移动逻辑，还注意到也有单独的个体加入新的鸟群，也有个体脱离旧的鸟群。
加入玩家
如果加入玩家的话，其实逻辑也很简单，只需要增加玩家距离小于一定阈值时的鸟群个体的分离原则即可，或者实际中直接附加到加速度上也是一样得，比如：
# 玩家避让
player_dist = (self.position - player_pos).length()
if player_dist < 100:
flee_dir = (self.position - player_pos).normalize() * 0.5
self.acceleration += flee_dir
加入玩家后的效果：
更高效邻居搜索
上面每次搜索邻居都要先计算一下和所有其他boid之间的距离，或者距离的平方，即使这个boid和你相差非常远，但是你不计算距离，也无法得知原来相差竟然这么远。这时候就需要更高效的数据结构，比如四叉树。四叉树原理很简单，就是对整个空间进行四象限的不断分割，保证最后的小象限区域内只有少量几个boid，然后寻找邻居只需要判断boid的感知区域和哪些象限区域相交，当然我们只需要计算叶子节点表示的象限，然后计算距离只需要计算这些区域内包含的boid即可。 针对这个简单的boids鸟群算法，可以简单写出如下的四叉树结构：
class QuadTreeNode:
def __init__(self, x, y, width, height):
self.bounds = (x, y, width, height) # 节点边界 (x,y,w,h)
self.boids = [] # 存储的Boid对象
self.children = [] # 四个子节点 [NW, NE, SW, SE]
def subdivide(self):
"""分裂当前节点为四个子象限"""
x, y, w, h = self.bounds
half_w, half_h = w//2, h//2
# 创建四个子节点
self.children = [
QuadTreeNode(x, y, half_w, half_h), # NW
QuadTreeNode(x + half_w, y, half_w, half_h), # NE
QuadTreeNode(x, y + half_h, half_w, half_h), # SW
QuadTreeNode(x + half_w, y + half_h, half_w, half_h) # SE
]
# 将当前节点Boid重新分配到子节点
for boid in self.boids:
for child in self.children:
if child.contains(boid.position):
child.insert(boid)
self.boids = [] # 清空当前节点
def contains(self, point):
"""检查点是否在节点范围内"""
x, y, w, h = self.bounds
return (x <= point.x <= x + w and
y <= point.y <= y + h)
def insert(self, boid):
"""插入Boid到四叉树"""
# 如果有子节点则插入到子节点
if self.children:
for child in self.children:
if child.contains(boid.position):
child.insert(boid)
return
# 添加到当前节点
self.boids.append(boid)
# 超过容量则分裂
if len(self.boids) > QUADTREE_CAPACITY:
self.subdivide()
def query_range(self, center, radius):
"""查询圆形范围内的所有Boid"""
found = []
# 检查是否与当前节点相交
if not self._intersects_circle(center, radius):
return found
# 如果有子节点则递归查询
if self.children:
for child in self.children:
found.extend(child.query_range(center, radius))
else:
# 检查当前节点内的Boid
for boid in self.boids:
if (boid.position - center).length() <= radius:
found.append(boid)
return found
def _intersects_circle(self, center, radius):
"""圆形与矩形相交检测"""
x, y, w, h = self.bounds
# 计算矩形最近点
closest_x = max(x, min(center.x, x + w))
closest_y = max(y, min(center.y, y + h))
# 计算距离
distance = math.sqrt((center.x - closest_x)**2 +
(center.y - closest_y)**2)
return distance <= radius
应用到Boid类中，就是apply_rules方法计算的邻居直接从四叉树中查询即可，其他逻辑没有任何变化。
def update(self, quadtree,player_pos):
"""使用四叉树查询邻居并更新状态"""
neighbors = quadtree.query_range(self.position, PERCEPTION_RADIUS)
self.apply_rules(neighbors,player_pos)
...# 其他更新代码
总结
相信上面的效果会让不少读者感到惊讶，就这么简单的三条原则，代码实现也是同样简单，但是就可以实现非常好的集群效果。我第一次了解到鸟群算法的时候也是如此，哪怕现在再次想到，依然觉得这个算法实在是太优雅了。
且鸟群算法集成游戏中，也几乎没有多少的成本，就可以实现优秀的集群效果。不单是鸟群的移动，还有比如海中鱼群的移动，大规模密集型敌人的移动等。