Collision detection trick.

Imagine you need to collide large groups of soldiers that moves all the time. Use of spatial structures in this case became a pain because of update times. To overcome this we've developed simple solution (I believe it used widely in modern physics engines for broad phase).

Consider picture below (we are looking on 2D version, but algorithm will work in 3D as well). We want to collide two circles:

Simple radius check is good enough in this case. But if you want to collide 1K circles - it will just become impractical. So, what about this colored lines on picture?

Red lines represent left bounds of each object on each axis and green lines represent right bounds. To detect possible collision between all objects on grid, we can perform the following.

Push all bounds to two arrays, one for each axis. Sort arrays by bound position. Iterate through arrays with logic:

• For each left bound consider object as open.
• For each right bound consider object as closed.
• For any bound met ->
• For each opened object ->
• Put potential collision bit into bit-table.
• Repeat for next axis.

If both tables are now show that there is potential collision between two objects (both bits are set) - perform radius check and report collision, if any.

To extent this method, presort bounds of groups of objects (for example units of soldiers). To perform collision between any groups you can do cheap mix of presorted arrays to avoid sorting of very large arrays.