Boids集群算法

这篇博客灵感来源于https://www.voidgame.space/articles/Voidmatrix/boids-algorithm/

Boids算法常见应用领域

动画和图形学：在电影制作和游戏开发中，Boids算法可以用于模拟鱼群、鸟群、昆虫群等自然生物的群体行为，使得动画场景更加逼真。
交通流模拟：Boids算法可以用于模拟车辆、行人或飞行器等交通工具的行为，用于优化交通流、规划路径或测试交通规则。
虚拟现实：在虚拟现实环境中，Boids算法可以用于模拟人群行为，例如在模拟人群疏散、人群聚集等场景中应用。
群体智能研究：Boids算法提供了一种简单但有效的方法来研究群体行为和群体智能，可以用于研究生态系统、社会动态等领域。

Boids三规则

分离：个体之间相互排斥，避免成一团。
聚集：个体朝着大部队运动。
对齐：个体运动的方向是同伴的平均运动方向。

用EasyX模拟实现该算法

重载一个Vector2D容器

struct Vector2D 
{
    float x, y;

    Vector2D() = default;//生成默认构造函数
    Vector2D(float _x, float _y) : x(_x), y(_y) {}//参数列表传参

    //重载加法运算符
    Vector2D operator+(const Vector2D& other) const 
    //常量成员函数,不能在函数内修改该对象的成员变量。
    {
        return Vector2D(x + other.x, y + other.y);
    }

    //重载减法运算符
    Vector2D operator-(const Vector2D& other) const 
    {
        return Vector2D(x - other.x, y - other.y);
    }

    //重载乘法运算符
    Vector2D operator*(float scalar) const 
    {
        return Vector2D(x * scalar, y * scalar);
    }

    //计算长度
    float length() const 
    {
        return std::sqrt(x * x + y * y);
    }

    //标准化
    void normalize() 
    {
        float len = length();
        x /= len;
        y /= len;
    }
};

定义集群单位

struct Boid 
{
    COLORREF color;
    Vector2D position;
    Vector2D velocity;

    // 聚集规则
    Vector2D cohesion(const std::vector<Boid>& boids)/操作/位置
    {
        Vector2D center_of_mass(0, 0);//质心位置
        int total_neighbors = 0;//相邻同伴个数

        for (const Boid& b : boids)
        {
            //计算每个同伴与当前boid的距离
            float distance = (b.position - position).length();
            //注意：这里的.length()调用的是重载后的,返回的是圆心的距离

            if (distance > 0 && distance < neighbour_distance)
            {
                center_of_mass = center_of_mass + b.position;//累加质心位置
                total_neighbors++;//重置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);
    }

    // 分离规则
    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);
                //将向量差乘以一个距离调整系数（以确保距离越近，斥力越大），然后将其加到分离向量 separation 中
            }
        }

        return separation;
    }

    // 对齐规则
    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 < neighbour_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);
    }

    // 更新方法
    void update(const std::vector<Boid>& boids) 
    {
        Vector2D v1 = cohesion(boids); 
        Vector2D v2 = separation(boids);
        Vector2D v3 = alignment(boids);

        // 根据规则权重调节最终行为
        v1 = v1 * cohesion_weight;
        v2 = v2 * separation_weight;
        v3 = v3 * align_weight;

        // 更新速度
        velocity = velocity + v1 + v2 + v3;

        // 限制速度
        float speed = velocity.length();//水平和竖直方向速度合成
        if (speed > max_speed) velocity = velocity * (max_speed / speed);
        //通过将原始速度向量乘以一个比例因子来实现缩放
        //保持速度向量的方向不变，但是将其长度缩放到最大速度

        // 更新位置
        position = position + velocity;//更新一次就加一个velocity

        // 限制位置
        if (position.x < 0) position.x = 0;
        if (position.x > 1280) position.x = 1280;
        if (position.y < 0) position.y = 0;
        if (position.y > 720) position.y = 720;
    }

    float neighbour_distance = 100.0f;      // 判定为临近单位的距离
    float separation_distance = 50.0f;      // 临近单位的分离距离
    float cohesion_weight = 1.0f;           // "聚集" 规则强度
    float separation_weight = 1.0f;         // "分离" 规则强度 
    float align_weight = 1.0f;              // "对齐" 规则强度
    float max_speed = 5.0f;                 // 集群最大速度
};

在幕布上随机位置绘制随机颜色的boid

std::vector<Boid> boids(500);
    for (Boid& b : boids)
    {
        b.position.x = (float)(rand() % 1280);
        b.position.y = (float)(rand() % 720);
        b.color = RGB(rand() % 255, rand() % 255, rand() % 255);
    }

主循环

int main()
{
    initgraph(1280, 720, EW_SHOWCONSOLE);
    BeginBatchDraw();

    // 初始化集群
    std::vector<Boid> boids(500);
    for (Boid& b : boids)
    {
        b.position.x = (float)(rand() % 1280);
        b.position.y = (float)(rand() % 720);
        b.color = RGB(rand() % 255, rand() % 255, rand() % 255);
    }

    // 循环模拟
    while (true)
    {
        // 更新集群
        for (Boid& b : boids)
            b.update(boids);

        // 渲染集群
        cleardevice();//清除上一帧画面
        for (Boid& b : boids)
        {
            setfillcolor(b.color);
            fillcircle((int)b.position.x, (int)b.position.y, 10);
        }
        
        FlushBatchDraw();
        //刷新绘图缓冲区，将绘图操作更新到屏幕上，以实现图形界面的实时更新
        //通常在每一帧的绘图操作结束后调用

        Sleep(25);
    }

    return 0;
}

在某些图形库或绘图环境中，为了提高性能和减少屏幕闪烁，绘图操作可能被暂时存储在一个称为绘图缓冲区的内存区域中。当使用 FlushBatchDraw() 函数时，它会强制将这些存储的绘图操作立即应用到屏幕上，从而使用户能够看到更新后的图像