A Pixel-Precision Method For Detecting Sprite Collision
v 1.0
by Mark Mackey
---
Introduction
----
A common query on the USENET newsgroup rec.games.programmer over the
years has been how to do fast pixel-precision collision detection. A
number of people have presented some excellent algorithms for extending
and speeding up bounding-box collision detection between large numbers of
objects (for instance, dividing the play area into subfields and sorting
the sprites into these subfields, thus greatly reducing the number of
sprite-sprite collisions that have to be checked in the first place).
However, there have been little information available on how to detect
collisions efficiently at the pixel level. I thus present here some code
from my game XQuest (blatant plug) which checks for collisions at the
pixel level. The routine assumes that the bounding boxes for the two
sprites overlap, and hence should be relatively easy to add to an
existing bounding-box collision detection routine. This code is fast,
relatively efficient in terms of space (requiring 4 bytes per row of each
sprite), and even works! The one limitation is that sprites are assumed
to be 32 pixels or less in width. For larger sprites, you could either
treat them as 2 or more 32-pixel wide objects, or with a bit of creative
thought this routine could be rewritten to allow for 64-pixel wide
objects on the 386 (left as an exercise for the reader :).
The code in the enclosed file COLLIDE.PAS is organised as a Turbo Pascal
unit, but all of the essential code is in assembly language and could be
easily ported to work under C or in a pure asm program. If any of the
Pascalisations confuse you just let me know and I'll explain :). Also, if
you need a version of this code to work on a 286 then let me know and
I'll send it to you (but be warned: it's not nearly as nice :).
---
The Algorithm
---
The first step is to create a 'transparency' mask for each sprite. The
mask consists of a dword for each row of the sprite, with each bit being
a 0 if the corresponding pixel is 'empty', and a 1 otherwise. For
example, if a row of your sprite looked like (colour indexes, 0 being
transparent)
0 0 0 1 23 42 0 1 56 0 0 0 0 0
the the corresponging mask bytes would be
00011101 10000000 00000000 00000000 = 1D 80 00 00
The MakeMask procedure given will produce such a mask from a sprite
supplied in the XLib linear bitmap format (with pixels of colour zero
being transparent), and is easily adaptable to your own sprite format.
OK, now the hard part. We have found in our general-purpose bounding-box
collision detection routine that two sprites' bounding boxes have
collided (ie their masks overlap).
Let the leftmost sprite have (x1,y1) as the coords of its top left
corner, and the rightmost one (x2,y2). Take the mask entry for row
|y2-y1| of the topmost sprite and shift it left by the difference in the
x-coordinates (x2-x1). AND this value with the 1st mask entry of the
lower sprite. If the result is non-zero then a collision occurred on this
row. If not, then shift row |y2-y1+1| and compare it to row 2 of the
lower sprite, and so on, until you reach the bottom of one of the
sprites. If no collision has been detected by this time, then the sprites
didn't collide. Simple, eh?
This routine is quite fast, requiring only a MOV, a SHL and an AND for
each row checked, and only checking those rows that overlap.
---
The Legal Bit
---
This software is (C) Copyright 1995 Mark Mackey. Permission is given to
distribute this code freely, or to distribute modified forms of this
software provided that the author is acknowledged and this copyright
notice retained. Permission is also given to utilise this code in
original or modified form in any software provided that the author is
acknowledged.
I can be contacted by
Email: mdm1004@cus.cam.ac.uk
WWW: http://www.ch.cam.ac.uk/MMRG/mdm.html
Snail: c/o Trinity Hall,
Cambridge CB2 1TJ
UK
These addresses will be in use until at least October 1996. Please let me
know if you found this code helpful/useful/rubbish/whatever or if you
improve it :)
(
geocities.com/timessquare/2795) (
geocities.com/timessquare)