Re: [pygame] Strategies for pixel-based collision

[andrew baker <failrate@gmail.com>]

If you're going to have loads of on-screen objects, it becomes less
significant what kind of collision-detection you're using and more
significant what collisions are going to be tested.  If two cars are
on opposite sides of the screen, they should never even be tested
against each other, saving you the overhead.

Sort first, then test.  Guarunteed to be faster.

Quoted from Way of the Rodent
(http://www.wayoftherodent.com/gd101/gd_robotronremake.htm):
"But, as expected, the additional demands on the collision detection
method made by increasing the number of Robotrons to around the 50
mark start bringing the game to a grinding halt. So, what does this
tell us about Robotron?

Simply this – a brute force collision detection strategy just won't
work. There are far too many things happening and interacting on
screen at once to effectively deal with them all, all of the time. So,
we have to try and apply some intelligence to our collision detection.

Firstly, it only makes sense to test collisions for objects which are
close to each other. Why should we waste precious time testing for
collision between a shot on the left of the screen and a Robotron on
the right. So, by dividing the screen into (slightly) overlapping
areas, we can narrow down the sheer volume of collision tests required
by only testing those collisions which occur within each area – a bit
like when your Grandad told you what "back to square one" really
meant.

The other tactic worth pursuing is that not all collisions need to be
tested in every frame. Because collisions occur on a sub-pixel basis,
any two colliding objects will remain in a "collision" state for
several frames. This is especially obvious when playing the original
in the Hulk/Family collisions – it is, quite often, possible to steal
a family member from underneath a Hulk. A surefire sign that some form
of selective collision detection is going on under the surface.

These are both classic coding tricks – the first is that, given an
arbitary list of data to process, it is almost always faster to sort
your data first. The second one is more subtle, but it basically boils
down to ensuring that critical tests (in this case collisions between
the player and the Robotrons) are always performed while less critical
tests (collisions between the Robotrons and the family) can be done in
slower time."