Spatial partitioning.
Is it 2D or 3D? If it's 2D this is what I do:
Code:
class SPGridSpace;
class SPGrid
{
public:
SPGrid(const Vector2D &Pos,const Dimension2D &SPWorldSize,const Dimension2D &Grid);
~SPGrid();
void Update();
SPGridSpace *GetGridSpaceAtPos(const Vector2D &Pos);
bool AddBoidToGrid(Boid *B);
bool GetNeighbors(Boid *B,vector <Boid *>&Neighbors);
vector <SPGridSpace *>Spaces;
Dimension2D WorldSize;
Dimension2D GridSize;
Dimension2D GSpaceSize;
Vector2D Position;
};
class SPGridSpace
{
public:
SPGridSpace(const Vector2D &GSCoord,SPGrid *PGrid);
~SPGridSpace();
Rectangle2D GetArea() const;
bool IsBoidInSpace(Boid *B) const;
void Update();
list <Boid *>Boids;
SPGrid *Parent;
Vector2D Coord;
Rectangle2D Area;
};
Code:
#include "SPGrid.h"
/* * * * * * * *
* *
* SPGrid *
* *
* * * * * * * */
SPGrid::SPGrid(const Vector2D &Pos,const Dimension2D &SPWorldSize,const Dimension2D &Grid) : Position(Pos), WorldSize(SPWorldSize), GridSize(Grid)
{
GSpaceSize = WorldSize / GridSize;
for(int X = 0;X < Grid.Width;X++)
{
for(int Y = 0;Y < Grid.Height;Y++)
{
SPGridSpace *GSpace = new SPGridSpace(V(X,Y),this);
Spaces.push_back(GSpace);
}
}
}
SPGrid::~SPGrid()
{
for(int i = 0;i < (int)Spaces.size();i++) delete Spaces[i];
}
void SPGrid::Update()
{
for(int i = 0;i < (int)Spaces.size();i++)
{
Spaces[i]->Update();
}
}
SPGridSpace *SPGrid::GetGridSpaceAtPos(const Vector2D &Pos)
{
SE_Assert((int)Spaces.size() > 0);
if(!Pos.InsideRect(V(0,0),WorldSize)) return NULL;
int X = Pos.X / GSpaceSize.Width;
int Y = Pos.Y / GSpaceSize.Height;
return Spaces[X * GridSize.Width + Y];
}
bool SPGrid::AddBoidToGrid(Boid *B)
{
SE_Assert(B != NULL);
SPGridSpace *Space = GetGridSpaceAtPos(B->Position);
if(!Space) return false;
B->Space = Space;
B->NewToSpace = true;
Space->Boids.push_back(B);
return true;
}
bool SPGrid::GetNeighbors(Boid *B,vector <Boid *>&Neighbors)
{
SE_Assert(B != NULL);
Neighbors.clear();
SPGridSpace *NearSpaces[9];
#define Spc(Coord) Spaces[(Coord).X * GridSize.Width + (Coord).Y]
NearSpaces[0] = Spc(B->Space->Coord + Vector2D(-1,-1));
NearSpaces[1] = Spc(B->Space->Coord + Vector2D( 0,-1));
NearSpaces[2] = Spc(B->Space->Coord + Vector2D( 1,-1));
NearSpaces[3] = Spc(B->Space->Coord + Vector2D(-1, 0));
NearSpaces[4] = Spc(B->Space->Coord + Vector2D( 1, 0));
NearSpaces[5] = Spc(B->Space->Coord + Vector2D(-1, 1));
NearSpaces[6] = Spc(B->Space->Coord + Vector2D( 0, 1));
NearSpaces[7] = Spc(B->Space->Coord + Vector2D( 1, 1));
NearSpaces[8] = B->Space;
#undef Spc
int Sum = 0;
for(int s = 0;s < 9;s++)
{
if(NearSpaces[s])
{
for(list <Boid *>::iterator it = NearSpaces[s]->Boids.begin();it != NearSpaces[s]->Boids.end();it++)
{
Boid *CBoid = *it;
if(CBoid != B)
{
if(CBoid->Position.DistanceFrom(B->Position) < B->Radius + CBoid->Radius)
{
Neighbors.push_back(CBoid);
Sum++;
}
}
}
}
}
return Sum != 0;
}
/* * * * * * * *\
|* *|
|* SPGridSpace *|
|* *|
\* * * * * * * */
SPGridSpace::SPGridSpace(const Vector2D &GSCoord,SPGrid *PGrid) : Coord(GSCoord), Parent(PGrid)
{
Area = Rect2D(PGrid->Position + V(PGrid->GSpaceSize.Width * GSCoord.X,PGrid->GSpaceSize.Height * GSCoord.Y),PGrid->GSpaceSize);
}
SPGridSpace::~SPGridSpace()
{
}
Rectangle2D SPGridSpace::GetArea() const
{
return Rect2D(Coord * Parent->GSpaceSize,Parent->GSpaceSize);
}
bool SPGridSpace::IsBoidInSpace(Boid *B) const
{
SE_Assert(B != NULL);
return B->Position.InsideRect(Coord * Parent->GSpaceSize,Parent->GSpaceSize);
}
void SPGridSpace::Update()
{
for(list <Boid *>::iterator it = Boids.begin();it != Boids.end();it++)
{
Boid *CBoid = *it;
SE_Assert(CBoid != NULL);
/*if(CBoid->NewToSpace)
{
CBoid->NewToSpace = false;
}
else*/
{
CBoid->Update();
if(!CBoid->Following && CBoid->Follower) DrawRect(GREEN , CBoid->Position, D(3,3), true, true, 0.0f); //String start
if( CBoid->Following && !CBoid->Follower) DrawRect(RED , CBoid->Position, D(3,3), true, true, 0.0f); //String end
if( CBoid->Following && CBoid->Follower) DrawRect(PURPLE , CBoid->Position, D(3,3), true, true, 0.0f); //String middle
if(!CBoid->Following && !CBoid->Follower) DrawRect(GREY , CBoid->Position, D(3,3), true, true, 0.0f); //Wandering
}
if(!IsBoidInSpace(CBoid))
{
it = Boids.erase(it);
if(!Parent->AddBoidToGrid(CBoid))
{
delete CBoid;
printf("Boid deleted!\n");
}
}
}
}
Code:
#include "SPGrid.h"
#include <vector>
class Boid : public FiniteStateMachine
{
public:
Boid();
~Boid();
float Radius;
Vector2D CalculateSteering();
Vector2D Wander();
Vector2D Seek();
Vector2D Position;
Vector2D Velocity;
Vector2D Acceleration;
Vector2D *Target;
bool WanderEnabled;
bool SeekEnabled;
bool SeparationEnabled;
bool CohesionEnabled;
bool AlignmentEnabled;
float WanderWeight;
float SeekWeight;
float SeparationWeight;
float CohesionWeight;
float AlignmentWeight;
vector <Boid *>Neighbors;
SPGridSpace *Space;
bool NewToSpace;
Boid *Follower;
Boid *Following;
};
You can ignore most of the Boid class, I put the important stuff in bold. The main thing you should look at is SPGrid::GetNeighbors. The way this works is simple. There's a grid that is the size of the 2D "World". This "World" grid is divided into x width spaces and y height spaces (see the SPGrid constructor and the "SPGrid::GetGridSpaceAtPos" function). Each one of these spaces updates itself and all of the objects in it with its own Update method. After updating each object in its own area, it checks if it is still inside its area. If not, it attempts to add the object to the parent SPGrid. If this fails, it means that the object is outside of the world and the object is deleted. Of course you could change how it handles that instead of just deleting them or whatever.
And that's pretty much it. It's easy. In the GetNeighbors function of SPGrid, it searches all the object's space's neighbors for objects. If any of the space's neighbors have objects, the distance between that object and the object you want to find the neighbors of. If the distance is less than the sum of their radii, then they are neighbors. I'm sure there's room for improvement here, but I wasn't using this for anything really intense yet.
I hope this helps in some way!
Check for nearest Object
Linear Mode
