Here we have a 4x4 blockmap, containing three particles of various sizes.
The GREEN one covers block d1
The YELLOW one covers blocks a2, a3, b2, b3
The RED one covers blocks b3, b4, c3, c4
So now each block is marked as containing certain particles.
Now, you have two choices. Either:
Go through block, check that it has more than two particles in it, and if so, perform all the
comparisons on them. This is best done when most of the blocks will contain particles.
We can see from the small diagram that block b3 contains two
particles. So, you know that those two particles might be touching.
Go through each particle, calculate (again) which blocks it covers and check if there are
any other particles in those blocks. If there are, then perform the comparisons on them. This is
best done if the particles are distributed sparsely about the area.
So how do you store the blocks? Well, this depends on your particle system.
Either you can allocate space in each block for a finite number of particles:
POINTER p1, p2, p3, p4, p5
. . . or you can use linked lists.
If you can be sure that there won't ever be any more than, say, five particles covering any one
block, then it is well worth using the first method. If, however, you cannot be sure, then it's
best to use the second, although it may be slower.
Notes on BlockMaps
One thing to be wary of. It is quite easy to accidently compare a pair of particles twice.
Imagine if the yellow block was one block higher. The block map would look like this:
If you're not careful, the program would think that the red and yellow particles had
collided twice. Now, this may or may not matter. If it does, then you will have to take steps
to avoid it.
The blockmap is only suitable for particle systems with short range interactions, like snooker
balls. Long, or infinite range systems, like gravity stars are best left to the brute force method.