From: Shawn Hargreaves <Shawn AT talula DOT demon DOT co DOT uk>
Newsgroups: comp.os.msdos.djgpp
Subject: Re: Collison detection fo Action game
Date: Wed, 5 Feb 1997 20:34:51 +0000
Organization: None
Distribution: world
Message-ID: <vgpI$hAr7O+yEwGt@talula.demon.co.uk>
References: <855142026 DOT 12716 AT dejanews DOT com>
NNTP-Posting-Host: talula.demon.co.uk
MIME-Version: 1.0
Lines: 41
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp

>What is the best/fastest way to do collision detection routines for a
>Action game in Allegro?

It really depends on the size and shape of your objects, and how much
accuracy you need. Here are a couple of approaches that I find useful,
but they are many hundreds of other good systems that you could use...

One of the simplest and fastest is to model each object as a circle.
Given the centre points of two objects (x1,y1 and x2,y1), and their
radius (radiii? what's the plural?) r1 and r2, they have collided if
sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)) < sqrt(r1*r1 + r2*r2).

Handy tip: avoid square roots: they are slow. Since all you need is the
result of the comparison, rather than the actual values, you can just
compare the squares and leave out both calls to sqrt().

If that isn't accurate enough, you may need to define 'hotspot' areas on
each sprite, which are sensitive to collisions. Store a list of regions
(circles or rectangles work well), which approximate the shape of the
sprite, and to test if two objects have collided, loop through these
hotspots checking each combination. This can be slow if you aren't
careful, so you should use a simple bounding box test first to avoid
having to test every single region if the objects are a long way away.
It may also be worth sorting the hotspots in some way, to reduce the
number of tests that are required. It depends how many you have, and how
many objects have to be tested each frame...

If true pixel-perfect testing is needed, one of the fastest approaches
is to pregenerate a monochrome mask for each sprite, containing one bits
for the pixels that are set and zeros for the ones that aren't. To test
two objects for a collision, line up these bitmasks depending on the
relative positions of the sprites (this involves a lot of shifting and
can be a big pain to get right), and then bitwise-or the two masks
together. If the resulting value is non-zero, the objects have collided.
This technique lets you check 32 pixels with each test, rather than
having to laboriously loop through every single pixel in the sprite...

/*
 *  Shawn Hargreaves - shawn AT talula DOT demon DOT co DOT uk - http://www.talula.demon.co.uk/
 *  Ghoti: 'gh' as in 'enough', 'o' as in 'women', and 'ti' as in 'nation'.
 */