Path: chuka.playstation.co.uk!news
From: James Russell <James_Russell@scee.sony.co.uk>
Newsgroups: scee.yaroze.beginners
Subject: Re: Collision Detection!.....(Joy)
Date: Fri, 02 Jul 1999 19:42:49 +0100
Organization: Sony Computer Entertainment Europe
Lines: 64
Message-ID: <377D0829.BA46A529@scee.sony.co.uk>
References: <7kdntq$4fj13@chuka.playstation.co.uk> <7kdqqp$4fj15@chuka.playstation.co.uk> <7ker42$4fj17@chuka.playstation.co.uk> <7kikb8$33u8@chuka.playstation.co.uk>
NNTP-Posting-Host: mailgate.scee.sony.co.uk
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Mailer: Mozilla 4.51 [en] (Win95; I)
X-Accept-Language: en

Hi guys,

I was out of the country for a little while so I didn't see this until just now.

Scott, I mistyped 2-bit for 1-bit. I basically meant an image of your sprite where a 1 means "this
pixel should be used in collision detection" and 0 means "ignore this pixel, it's transparent".

As for the shifting, that's necessary if you're storing 8 pixels per byte for the mask.

Here's a concrete example:

Say you've got a sprite 12 pixels wide and 3 pixels high. The mask of it might look like this:

001111111111
110010011111
001111111111

I dunno what that is, maybe it's a bullet or something. Anyway, I've put a 1 where there is colour,
and a 0 where there is no colour.

Now say I want to detect whether this hit another sprite. For simplicity, let's say we're checking
against two identical sprites.

Firstly, I check the bounding boxes - if the leftmost edge of sprite 1 is further right than the
rightmost edge of sprite 2, then there's no collision, etc...

If the two boxes intersect anywhere, then I have to go to the pixel level.

This is where it gets slightly tricky. The pseudocode is this:

For each line in Sprite 1 {
	Check to see whether Sprite 2 overlaps this line at all. If so {
		Check the bit patterns for the current line in Sprite 1 with the bit pattern
		for the overlapping line in Sprite 2.
	}
}

The middle bit is the tricky part. You can find out which line in Sprite 2 you have to check by
doing some simple arithmetic based on the relative position of the two sprites. Now say you have the
two lines in an array, 8 bits per byte, so that's 16 bits wide for our sprite above (it's only 12
wide, so we pad it out to 16 with 0s (Pad them with 0s on the LEFT)). 

Say the X of sprite 1 is S1X and the X positions of Sprite 2 is S2X, and S1X >= S2X. Then they are
S2X - S1X pixels different in position. Call this value DX.

For each byte (I) in Sprite 1's line starting at the rightmost byte:
	Sprite2 byte offset = DX / 8
	Sprite2 shift offset = DX % 8
	S1P = Sprite 1 byte (I)
	S2P = Sprite 2 byte (Sprite2 byte offset + I)
	S2P <<= Sprite2 shift offset
	if S2P AND S1P != 0 then there is a collision.
do this until either Sprite2 byte offset + I > width of the thinnest sprite being tested
	
Erm... I just figured this out my head, but it should work. (Cough)

James


-- 
== James_Russell@scee.sony.co.uk        ph: +44 (171) 447-1626  -  fax: 390 4324
== Tools and Middleware Licensing Manager  -  Sony Computer Entertainment Europe

90% of all statistics are made up.