Particle-Particle Interaction: boids, crowds, etc

CS 493/693 Lecture, Dr. Lawlor

So far, each of our particles has interacted with the environment independently, not caring about any other particle.  But many objects, such as fish or birds or crowds of people, take most of their motion cues from the environment. 

The simplest sort of interaction is to "chase" a target point: just apply an accelleration in the direction you want to go.  The interplay between inertia, wind drag, and targetting causes some interesting behavior, as shown in the example code "particles4_chasers".

Back in 1987, Craig Reynolds published a highly influential SIGGRAPH paper on "boids", a detailed model of bird flocks.  An individual "boid" chooses its motion based on a priority hierarchy: avoid obstacles, don't hit your neighbors, stay with the flock, and get where you're going.  You can see Craig's nice 3D applet and informal writeup, or play with an interactive 2D JavaScript implementation here (hit "Object: Obstacle" to create yellow blocking spheres; you can also adjust priorities).

In 1999, after one grueling weekend of work Gregg Christopher and I published a winning MCM paper simulating disk-people fleeing a crowded room.  You can read the writeup and download a Windows executable here.  The trickiest part about this simulation was keeping disk-people from overlapping--Jason Tedor suggested an excellent hack for this, which is to move only one person at a time, and not allow that person to move if they'd be stepping on top of somebody else.  Another problem was disk people piling up in a sort of "arch" formation around a door, where nobody could move forward because everybody else is blocking the way--we solved this by adding a "shuffle" function: if your path is blocked, you take a step in a random direction.

Search Grid

In each case above, we need an efficient data structure to find nearby particles.  One decent data structure of this type is a "search grid": we keep a list of particles at each grid cell in a 3D grid through space.  At each step, we:
  1. Sift the particles into the search grid, adding it to the neighbor list there.  This is the "scatter" phase.
  2. Find your neighbors by looking through the list in your own grid cell (and the neighboring grid cells, if you want to be perfectly accurate).  Careful: you are your own neighbor, but you probably don't want to push yourself away!
Here's a typical implementation, where the grid is a std::map from an index to a vector of particles:
/* A search grid index.  This is used to locate nearby particles. */
class searchIndex {
public:
	int x,y,z; /* our grid cell's 3D index */
	searchIndex(const vec3 &loc) {
		x=(int)floor(loc.x*loc2grid);
		y=(int)floor(loc.y*loc2grid);
		z=(int)floor(loc.z*loc2grid);
	}
	bool operator<(const searchIndex &other) const { // used by std::map
		/* Compare x... */
		if (x<other.x) return true;
		if (x>other.x) return false;
		/* ... now y... */
		if (y<other.y) return true;
		if (y>other.y) return false;
		/* ...finally z */
		return z<other.z;
	}
};

typedef std::vector<particle *> neighborList;

/* Input: your 3D location.  Output: a list of your neighbors */
typedef std::map<searchIndex,neighborList > searchGrid;
searchGrid grid;

... before working on the particles ...
	/* Set up the neighbor grid: add each particle to its grid cell */
	for (unsigned int i=0;i<p.size();i++) {
		grid[p[i].pos].push_back(&p[i]);
	}

... for each particle ...
	/* look up the list of particles near my position */
	const neighborList &neighbors=grid[pos];
	for (neighborList::const_iterator ni=neighbors.begin();ni!=neighbors.end();ni++)
	{
		particle *p=*ni;
		if (p==this) continue; /* don't repel myself! */
		... apply forces between myself and my neighbor p ...
	}
See "particles5_searchgrid" for a complete example.  Entertaining things to try: