Boids 알고리즘 - Bird Flocking Simulation in C++

Boids?

Boids(Bird-oid objects)는 새 떼의 움직임을 구현하기 위해 Craig Reynolds가 개발한 알고리즘 체계이다.

새 떼의 움직임을 구현하는 Boids엔 세개의 Rule이 존재한다.

---

1. Separation

가까운 거리 내에 있는 다른 새들에게서 멀어지려는 특성이다.

• 구현

1. 정해진 반경(desiredSeparation) 내 들어오는 모든 새들에 대해 거리에 반비례하는 away 벡터를 구한다.
2. 모든 away 벡터를 더하고 normalize한 결과값인 steer벡터를 새의 현재 velocity에 더한다.

void BirdShape::Separation(const std::vector<BirdShape>& flock)
{
    float desiredSeparation = config.desiredSeparation;
    float separationStrength = config.separationStrength;
    float maxSeparationForce = config.maxSeparationForce;

    sf::Vector2f steer{0.f, 0.f};
    int count = 0;

    for (const auto& other : flock) {
        if (&other == this) continue;

        sf::Vector2f diff = getPosition() - other.getPosition();
        float distSquared = diff.x * diff.x + diff.y * diff.y;

        if (distSquared > 0.f && distSquared < desiredSeparation * desiredSeparation) {
            sf::Vector2f away = diff / distSquared;
            steer += away;
            count++;
        }
    }

    if (count > 0) {
        steer /= static_cast<float>(count);

        float len = std::sqrt(steer.x * steer.x + steer.y * steer.y);
        if (len > 0.f) {
            steer = (steer / len) * std::min(separationStrength * len, maxSeparationForce);
            m_velocity += steer;
        }
    }
}

---

2. Alignment

주변 flockmate들과 비슷한 방향으로 진행하려는 특성이다.

• 구현

1. 새의 진행 각도(arctan)를 구한다.
2. 전체 flock의 진행 각도 평균을 구한 후, 새의 진행각도와의 차이를 구한다.
3. 새의 진행 방향을 그 차이에 따라 수정한다.

void BirdShape::Alignment(const std::vector<BirdShape>& flock)
{
    sf::Vector2f velocity = this->getVelocity();
    float birdAngle = std::atan2(velocity.y, velocity.x);
    float speed = std::sqrt(velocity.x * velocity.x + velocity.y * velocity.y);

    int count = 0;
    float angleSum = 0.f;

    for (const auto& other : flock) {
        if (&other == this) continue;
        sf::Vector2f otherVel = other.getVelocity();
        angleSum += std::atan2(otherVel.y, otherVel.x);
        count++;
    }

    if (count > 0) {
        float avgAngle = angleSum / static_cast<float>(count);

        float newAngle = birdAngle + (avgAngle - birdAngle) * config.alignmentStrength;

        m_velocity.x = std::cos(newAngle) * speed;
        m_velocity.y = std::sin(newAngle) * speed;
    }
}

---

3. Cohesion

뭉치려는 특성으로, center mass 방향으로 진행하려는 특성이다.

• 구현

1. Flock의 center mass를 구한다.
2. 새의 현재 위치벡터와 center mass의 차이벡터를 구한다.
3. 새의 Velocity에 차이벡터를 더한다.

void BirdShape::Cohesion(const std::vector<BirdShape>& flock)
{
    sf::Vector2f centerMass{0.f, 0.f};
    int count = 0;

    for (const auto& other : flock){
        if (&other == this) continue;
        centerMass += other.getPosition();
        count++;
    }
    if (count > 0) {
        centerMass /= static_cast<float>(count);
    }

    sf::Vector2f toCenter = centerMass - getPosition();
    float distance = std::sqrt(toCenter.x * toCenter.x + toCenter.y * toCenter.y);

    if (distance > 0.f) {
        toCenter /= distance;
        m_velocity += toCenter * config.cohesionStrength;
    }
}

---

Boids는 인공지능을 사용하는 Swarm Intelligence의 기반이 되며, Crowd Simulation등 다양한 분야에 적용된다.

전체 코드 -> Github Repo

---

한계점

상수값 결정

Boids는 자연스러운 움직임을 위해 다양한 상수값을 지정해야 한다. 어느 정도 본인이 조정하면서 만들 수 있지만, 귀찮고 힘들다.

아래는 내 프로그램의 상수값들이다.

머신러닝 모델 또는 CV를 도입하여 상수 파라미터를 결정하면 좋을 것 같다.

정말 부자연스럽다

물론 내 프로그램 자체가 매우 단순하기에 자연스러운 움직임을 바랄 순 없지만, 이 세가지 Rule만으론 제대로된 Flocking simulation을 만들 순 없다.

장애물 또는 포식자가 나오도록 만들고, 그에 따라 Flock이 반응하는 장치를 추가하고, 더 자연스러운 Random Noise 를 구현한다면 더 자연스러워질 것이다.