First off, you can download and play around with the demo here. The zip contains an xml file, txt file, and an .exe which I promise won't kill your computer. Click the mouse button to set the flock's target, 'z' and 'x' make the flock speed up and slow down, respectively. It's win32, so if you're using a Mac or *nix system, no luck for you. I'd say I was sorry about that, but I'm not [wink].
Right, so flocking. The general flocking algorithm was put forth by Craig Reynolds in 1986. Basically, your flock is made up of individual agents, called "boids". Each boid has several steering behaviors to try to keep it with the rest of the flock: separation, alignment, and cohesion. Basically, you want a boid to stay a certain distance from all the others (separation), go in the same direction as the rest of the flock (alignment), and try to stay with the flock in general (cohesion).
This is simple enough to code. Every update, get all nearby boids. Then you need to get three steering vectors for that update. For separation, look at the nearest boid to you. If it is too close, steer away from it. For alignment, simply steer in the same direction as the nearest boid. For cohesion, find the center of the visible flock and steer towards that. These three vectors are then combined with a weighted sum, and results in your new velocity.
That's the basic idea, and it's simple to expand upon. If you want to flock to a set goal, add a fourth steering behavior that moves the boid toward its goal every frame. For obstacle avoidance, add a steering behavior that will look ahead for collision and will avoid anything you may collide with in the near future.
Simple stuff, but you can get some neat emergent behavior out of just these few steering behaviors. Here's what my final boid code looked like (hint: it's not very good):
Boid.cpp
#include "../Header Files/Boid.h"#include "../../Main/Header Files/Event.h"#include "../../Main/Header Files/Input.h"#include "../../Physics/Header Files/Object.h"#include #include #include #include #include #include extern CS380::Base::EventManager *g_Events;extern Mouse *g_mouse;extern std::vector g_Circles;CS380::AI::Boid::BoidContainer CS380::AI::Boid::AllBoids;CS380::Math::CVector3 CS380::AI::Boid::PointOfInterest;CS380::AI::Boid::Boid(CS380::Math::CVector3 *pos, CS380::Math::CVector3 *dir): m_angle(0),m_radius(100),m_position(*pos),m_heading(*dir),m_DrawBounds((int)(pos->x - 5), (int)(pos->y - 5), 10, 10),m_DrawAngleStart(0.f),m_DrawAngleSweep(45.f){ ReadWeights(); AllBoids.push_back(this); g_Events->RegisterEventHandler("flock", this, &Boid::Flock); g_Events->RegisterEventHandler("draw", this, &Boid::Draw);}CS380::AI::Boid::~Boid(){ assert( std::find(AllBoids.begin(), AllBoids.end(), this) != AllBoids.end() ); AllBoids.erase( std::find(AllBoids.begin(), AllBoids.end(), this) );}void CS380::AI::Boid::Flock( const Base::Event* /*evt*/ ){ UpdateVisibleBoids(); Math::CVector3 newAccel; if ( !m_VisibleBoids.empty() ) { Boid *closest = NULL; float dist = m_radius; for (BoidIter it = m_VisibleBoids.begin(); it != m_VisibleBoids.end(); ++it) { float d = ((*it)->m_position - m_position).Length(); if ( d < dist ) { dist = d; closest = *it; } } newAccel += GetSeparation(closest, dist); newAccel += GetHeading(closest); newAccel += GetCenter(); } newAccel += GetForward(); newAccel += AvoidObsticles(); m_heading = (m_heading + newAccel);//.Norm(); if (m_heading.Length() > 1.f) { m_heading.Normalize(); } bool inCollision = false; for (std::vector::iterator it = g_Circles.begin(); it != g_Circles.end(); ++it) { if ( (*it)->Intersects(m_position + m_heading) ) { inCollision = true; break; } } if (!inCollision) { m_position += m_heading; } m_DrawBounds = Gdiplus::Rect((int)(m_position.x - 5), (int)(m_position.y - 5), 10, 10);}void CS380::AI::Boid::Draw( const Base::Event* evt ){ assert( evt->IsA(CS380::Base::EVT_1) ); const CS380::Base::Event1 *evt1 = dynamic_cast<const CS380::Base::Event1 *>(evt); assert( evt1 ); Math::CVector3 temp(m_heading); if (temp.y < 0.f) { temp.x = -temp.x; } float headingAngle = Math::RadToDeg( acosf( temp * Math::CVector3( 1, 0, 0 ) ) ) + (temp.y < 0.f ? 0.f : 180.f); m_DrawAngleStart = headingAngle - 25; Gdiplus::SolidBrush sbrush(Gdiplus::Color::Red); Gdiplus::Pen pen(&sbrush, 5.0); Gdiplus::Status status = evt1->param1->DrawPie(&pen, m_DrawBounds, m_DrawAngleStart, m_DrawAngleSweep);}void CS380::AI::Boid::UpdateVisibleBoids(){ m_VisibleBoids.clear(); for (BoidIter it = AllBoids.begin(); it != AllBoids.end(); ++it) { if (*it == this) { continue; } Math::CVector3 diff = (*it)->m_position - m_position; if (diff.Length() > m_radius) { continue; } if (diff.Norm() * m_heading.Norm() < -.86f) { continue; } m_VisibleBoids.push_back(*it); }}CS380::Math::CVector3 CS380::AI::Boid::GetSeparation(Boid *closest, float dist){ assert( closest ); float ratio = dist / m_SeparationDist; ratio = min( m_SeparationWeightMax, max(m_SeparationWeightMin, dist) ); if (dist == m_SeparationDist) { return Math::CVector3(); } else { return (closest->m_position - m_position).Norm() * (dist > m_SeparationDist ? ratio : -ratio); }}CS380::Math::CVector3 CS380::AI::Boid::GetHeading(Boid *closest){ assert( closest ); return closest->m_heading.Norm() * m_HeadingWeight;}CS380::Math::CVector3 CS380::AI::Boid::GetCenter(){ Math::CVector3 center; for (BoidIter it = m_VisibleBoids.begin(); it != m_VisibleBoids.end(); ++it) { center += (*it)->m_position; } center /= static_cast<float>(m_VisibleBoids.size()); return (center - m_position).Norm() * m_CenterWeight;}CS380::Math::CVector3 CS380::AI::Boid::GetForward(){ Math::CVector3 forward = PointOfInterest - m_position; float diff = (forward.Length() - m_ForwardWeightMin); float urgency = fabs(diff); urgency = min(m_ForwardWeightMax, max(m_ForwardWeightMin, urgency)); return forward.Norm() * ( urgency * (diff > 0 ? 1 : -1) );}CS380::Math::CVector3 CS380::AI::Boid::AvoidObsticles(){ CS380::Physics::Circle *c = NULL; float dist = m_CollisionDist; //get nearest obsticle for (std::vector::iterator it = g_Circles.begin(); it != g_Circles.end(); ++it) { float d = ((*it)->m_position - m_position).Length(); if ( d < dist ) { dist = d; c = *it; } } if (!c) { return Math::CVector3(); } Math::CVector3 toCircle = c->m_position - m_position; if (toCircle.Length() > m_CollisionDist) { return Math::CVector3(); } toCircle.Normalize(); float dot = toCircle * m_heading.Norm(); if (dot < 0.f) { return Math::CVector3(); } dot = 1 - dot; dot *= (m_CollisionDist - dist + c->m_radius) / m_CollisionDist; float urgency = min(m_CollisionWeightMax, max(m_CollisionWeightMin, dot)); Math::CVector3 ret = (m_heading.Norm() - toCircle).Norm(); return ret * urgency;}void CS380::AI::Boid::ReadWeights(){ std::ifstream file("flocking constants.txt"); std::string line; std::getline(file, line); std::stringstream ss(line); ss >> m_SeparationDist; ss >> m_SeparationWeightMax; ss >> m_SeparationWeightMin; std::getline(file, line); std::stringstream ss2(line); ss2 >> m_HeadingWeight; std::getline(file, line); std::stringstream ss3(line); ss3 >> m_CenterWeight; std::getline(file, line); std::stringstream ss4(line); ss4 >> m_ForwardWeightMax; ss4 >> m_ForwardWeightMin; std::getline(file, line); std::stringstream ss5(line); ss5 >> m_CollisionDist; ss5 >> m_CollisionWeightMax; ss5 >> m_CollisionWeightMin;}
