From: mert0407 AT sable DOT ox DOT ac DOT uk (George Foot)
Newsgroups: comp.os.msdos.djgpp
Subject: Re: Collision Detection
Date: 30 Apr 1997 10:03:54 GMT
Organization: Oxford University, England
Lines: 62
Message-ID: <5k75ea$j15@news.ox.ac.uk>
References: <MPG DOT dcddb78f470c89c98968a AT news DOT demon DOT co DOT uk> <Pine DOT SV4 DOT 3 DOT 94 DOT 970428125700 DOT 28102C-100000 AT aludra DOT usc DOT edu>
NNTP-Posting-Host: sable.ox.ac.uk
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Precedence: bulk

rellwood (rellwood AT aludra DOT usc DOT edu) wrote:

: The best method is the slowest, and that is to AND each nonzero pixel in
: sprite A with each nonzero pixel in sprite B.  If any of the ANDs return

I think you mean OR.

: A much quicker method is to detect a collision of just the bounding box
: around each sprite.  If the boxes overlap the detector returns true.  The
: problem with this, of course, is that usually a given sprite doesn't fill
: the bounding box completely and the detector will return a true if the
: boxes overlap but the sprites don't.  Usually this is an okay trade-off
: for the speed advantages.

: A third way is to use bounding circles instead.  I have nevery actually
: tried this, but I suppose it could be implemented easily enough using good
: old Pythagorian Theorum, and just measure the DISTANCES between the two
: sprites.  If the result is smaller then a certain threshold, you have a
: collision.  This is a bit more accurate then bounding boxes, but it is
: somewhat slower because you have to compute square roots. 

The technique with circles is not necessarily more accurate; if the sprite
is in fact rectangular the bounding boxes are, of course, the most
accurate way. Note that in the circle system your metric would be
sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)), and you would test whether this is
less than the sum of the radii of the two circles; but this is equivalent
to testing that (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)<(r1+r2)*(r1+r2), which is
much faster since there are no square roots needed (TRUE => collision).

For bounding boxes, given the coordinates of the centre of the
box (xa,ya) and half the width and height (wa,ha) you test whether
abs(x1-x2)<(h1+h2) and abs(y1-y2)<(h1+h2) simultaneously.

In the rare case that your sprites are diamond shaped, try testing
abs(x1-x2)+abs(y1-y2)<(s1+s2) for diamonds whose extreme points are sa
units from the centre (xa,ya).

In short, you need to choose the system which is most suitable for
your needs, or invent one of your own (like the diamond one) if you think
of one which particularly suits your sprites.

One thing you might consider if you have very weird shaped sprites is to
define several areas of the sprite which need checking, and testing them
all. For example, if you have a large squarish C-shaped sprite and a
smaller circular one which fits inside the C, a bounding box would prevent
the smaller one from entering. But if you define three bounding boxes
around different parts of the C, so that their union covers the whole
drawn area of the sprite, the smaller one could get inside. I'm not
explaining this very well... maybe someone else can do it more clearly. 

If you also define a bounding box around the entire sprite, you only need
to bother checking all these smaller test areas if the sprits have
overlapping bounding boxes; this will speed up the routine a great deal.
You could also use this method if you're worried about circles taking too
long to test - do the bounding box check first, then the circle test if
the bounding box shows that they are overlapping. I'm not sure I'd be too
worried about the time taken to add and square three integers, add two of
the results together, subtract the third and test the sign.

-- 
George Foot <mert0407 AT sable DOT ox DOT ac DOT uk>
Merton College, Oxford