Sprite collision for Genesis

Kaneda - Oct 04

If you try to learn how to create a game, a question will certainly come : How do I know if my sprites collide ?

When this question finally came, I launched Google and read all I can find about it.
It was hard because 3D is everywhere and I was looking for 2D sprites collision.
Here is an easy to read (I think) resume of what I learnt, how I ported it to Genesis and how I took advantage of Genesis features to optimize it.

► Method 0 : Let the Genesis works for you!

This method can only be used for VERY basic/limited game.
On screen, with have your sprite and the bad ones. Bad sprites can't collide themself because you make it this way.
The ONLY collision which can occurs is between you and a bad guy.
How to detect this ? You can use a software method that I'll explain later or you can simply ask the Genesis.

A bit of the Status Register will tell you if a sprite collision occurs or not.
0 means no collision, 1 means collision (you're dead).
But it's all! You know 2 sprites collides but not which and where.

Very limited no ? But with this, you can at least make something like AutoRace.

You understand why I call it Method 0 : you'll never use it!....not alone!
When the hardware isn't enought, use the software!

► Method 1 : Basis

First, what is Sprite collision ? It's when your shot kills an UFO or when Sonic die because of a stupid killer bee!
What define a sprite like a shot, an UFO, Sonic or a killer bee ? Its picture, its colors, its position, its size and any user defined data...
Its size and its position...so its rect (x, y, x+width, y+height).
Here we are : we need to check if a sprite rect intersect with others.
In which case a sprite rect intersect another one ? 4 cases :

• case 1 :
  ( sprite1.x < sprite2.x but sprite1.x2 > sprite2.x ) AND ( sprite1.y < sprite2.y but sprite1.y2 > sprite2.y )
• case 2:
  ( sprite1.x < sprite2.x but sprite1.x2 > sprite2.x ) AND ( sprite1.y< sprite2.y2 but sprite1.y2 > sprite2.y2 )
• case 3:
  ( sprite1.x < sprite2.x2 but sprite1.x2 > sprite2.x2 ) AND ( sprite1.y < sprite2.y2 but sprite1.y2 > sprite2.y2 )
• case 4:
  ( sprite1.x < sprite2.x2 but sprite1.x2 > sprite2.x ) AND ( sprite1.y < sprite2.y but sprite1.y2 > sprite2.y )

Of course, don't test case 3 if case 2 is successful. we have up to 4 cases of 4 tests to check.
The Genesis can handle up to 80 sprites (with some limits but forget it until needed) so our sprite collide test can be written like this

For each of the 80 sprites, check if it collides with the others

Good! Well....not really. Perhaps DirectX use this method but us, we need something optimized, who take the less resource as possible!
Here we make 80*(80-1)*4*4 calls...and often since there is more often NO collision (unless you are on an asteroids field!)
A good one if you're trying to understand what LAG is!

In a lot of case, you'll learn that it's more easy to find what you DON'T need that what you need. Let's try

In wich case a sprite rect NOT intersect with another one ? 4 cases :

• case 1 :
  ( sprite2.x > sprite1.x2 )
• case 2:
  ( sprite1.x > sprite2.x )
• case 3:
  ( sprite2.y > sprite1.y2 )
• case 4:
  ( sprite1.y > sprite2.y2 )

4 cases, like the previous method...Well not exactly the same ? 4 cases of 1, and only 1, test.
We now have 80*(80-1)*4*1, 4 times faster !

Now, try to optimize this slow loop. What does it do ?
Check sprite 1 with sprite 2
Check sprite 1 with sprite 3
Check sprite 1 with sprite 4
Check sprite 1 with sprite X
Check sprite 1 with sprite 80
Check sprite 2 with sprite 1       !!
Check sprite 2 with sprite 3
Check sprite 2 with sprite 4
Check sprite 2 with sprite X
Check sprite 2 with sprite 80
Check sprite 3 with sprite 1       !!
Check sprite 3 with sprite 2       !!
Check sprite 3 with sprite 4
Check sprite 3 with sprite X
Check sprite 3 with sprite 80

As you can see with the "!!", we check some collide several times. You can also notice these duplicate checks are with the previous sprite.
So we need to only check each sprite with the next ones .

For each sprite, check if it collides with the next one

We now have (79+78+77+...+2+1)*4*1, or ((79*80)/2)*4...yes, 2 times faster.
Even if we finally are 8 times faster than original method, it's still a heavy loop.
We must call it the less possible to avoid resource leak! Ask for the help of the Genesis and its Status Register!

If the Genesis detects a sprite collision
         For each sprite, check if it collides with the next one

Our loop is still heavy but, at least, we only call it when necessary!
Can we optimize it again ? In fact, yes, but with time, it's game specific.

► Method 2 : Game specific

This method is an optimized version of method 1. I don't merge them together because I think you can use method 1 only, since this method is game specific.
What do I mean by 'game specific' ? In some cases, you won't be able to use it, as I explain at the end.

What do we really want in most of the cases ? If our sprites collide with CPU ones.
But not if our sprites collide themself (your shot won't kill you!) nor CPU ones collide themself (why shot if UFO crash on other UFO ?).
We can also have art sprites we don't need to check (the animated moon on the background is just here to illustrate space!)
So we have the 'good' sprites which need to be checked with the 'bad' sprites
Two ways to handle this:

1. The first sprite on your sprite list are 'good' sprites, followed by the 'bad' sprites, themself followed by the 'art sprite'
2. A 'good' sprites list and a 'bad' sprites list

I use the first one because I only need one array of 80 sprites, no need to worry about the max number of 'good' sprites and of 'bad' sprites.

For each of the 'good' sprite, check if it collides with a 'bad' sprite

Now we have (number of 'good' sprites)*(number of 'bad' sprites)*4...so at max it's 40*40*4.
This is the method I personnaly use with success

Q."But in Pong, the ball isn't a 'good' nor a 'bad' sprite! I can't use this method"
A.Are you sure ? For me, the ball is 'good' THEN 'bad' :
When the ball come from the CPU, it's a 'bad' sprite. You check collide with it. If it collides, you change the direction and make it a 'good' sprite!
You check if it collides with the 'bad' CPU paddle. If it collides, you change the direction and make it a 'bad' sprite....and so on.
So, this method could be apply to Pong

Q."But in Mickey and Donald, I need to check if they collide ! I can't use this method"
A.You can't use ONLY this method.
You first need to check if Mickey collides Donald and handle it ( Mickey is on Donald or Mickey slaps Donald).
Then you can normaly use the method to check if any of them (the 'good' sprites) collide with a 'bad' sprite

Q."But in Puzzle Bobble, there isn't 'good' or 'bad' sprite! I can't use this method"
A.Unfortunatly yes, this method isn't for Puzzle Bobble, as for any game when you can't make 2 sprites categories : 'good' and 'bad' (yours and its)

► Method 3 : More limits but more speed

I recently found an other way to optimize. I call it the Fonzie Method because he found & used it before me :)
This method has some disadvantages : it can only be apply on games which was designed to use this method and, most of all, some collision tests could be missed.
Ok, what's the need for this method if what we need doesn't work 100% ? Because, as I said, this method will miss some sprites collide only if you design it well.

I was looking for a way to check collision between less sprites as possible and only when I need to.
The Status Register's bit again ? Sorry, not this time...because I need to know which sprites collide.
On the Genesis, we have 32 columns (or 40 if you want) of 8 pixel width. I worked on the idea that if you have 2 sprites on the same column then they perhaps collide.

First, draw the 'good' sprites and store their number on the 32width (for 32 columns) goodList. If you sprite is on column 11 and 12, write it at goodList[11] and goodList[12].
Second, do the same thing with the 'bad' sprites in the badList.
For each of the column, if there is something in the goodList AND the badList, then test collide between these 2 sprites! If collision, remove them for the lists to avoid unneeded others test in the following columns.

We now have (number of 'good' sprites) * 1 write + (number of 'bad' sprite)*1 write + 32*4 tests. Not so bad, no ?!
Sorry,but it's too good to be real! We have a BIG problem : How do we must act if we have more than 1 sprite on the same column ?!

the red is the good one so we have goodList = [1,1] badList = [0,?]

If I put the green bad sprite, I won't detect the collision with the yellow sprite.
If I put the yellow bad sprite, it's ok....in this case!

So this method is wrong...if you let it like that.
Another time, let's think again at what we're looking for.
For a lot of games (the others can't use this method), we want to check

   If our sprites collide CPU one
      OR
   If CPU sprites collide our sprites

The same thing ? Well, it seems yes if you say it...but if you code it, you'll understand what is the difference.
On the previous method, we used the first one so I'll test the second!

I also choose it because we often had less 'good' sprites than 'bad' sprites ( we only have one on a jump'n'run game and your shoot is limited on a shoot'em up) and because our sprites are better handled (to have a minimum time between each shoot for example).

First, draw all the 'good' sprites and update the goodList.
Second, for each sprite, check if there is something on the column and check it.If there is nothing, draw it else handle the collide!

Example 1:

[0,1,0,2,3,4,0,5]		[0,1,0,2,3,4,0,5]
	=>

Example 2:

[0,1,0,2,2,0,3,3]		[0,1,0,2,2,0,3,3]
	=>

Perhaps you didn't notice but there is a big difference with what we wrote before.
We was used to
     - Update all sprites
     - Check all sprites with next ones
Now we have
     - Update 'good' sprites
     - Update 'bad' sprites and check collide
     - Update 'art' sprites

Is it a good change ?
We had
     (number of 'good' sprites)*(number of 'bad' sprites)*4 test => max 40*40*4
We have
     (number of 'good' sprites)*1 write + (number of 'bad' sprites)*1 test + (number of 'bad' sprites)*4 tests

On the heaviest possibility for Method Two, we have 40 'good' sprites and 40 'bad' sprites, so 64000 operation.
With the same value, we have 240 operations. 266 times faster! The difference decreases upon 'good' or 'bad' sprites number.
You'll find 2 cases where Method Two is better than Method 3 : when there is only 1 'good' sprites and when there isn't a 'bad' sprite.

So, is it a good method ?
Well...it's up to you! But don't forget :

• avoid two 'good' sprites on the same column (control the speed of your sprite, the time between each movement, etc...)
• you have to handle a column list (a 32 width array)
• you have to test the collide while redrawing 'bad' sprites and not when you want.

► Final Words

To check collide, I use the sprite rect (8*x, 8*y, 8*x2, 8*y2). If you need a more accurate detection, you'll need to have a collide box per sprite and make all the checks between sprite's collide box.

This is not the ultimate method, it's a common method. Be free to create yours but I'm pretty sure it will be a based on Method 1 or 2.

If you don't understand something, let me know, I'll try to make it clear updating this doc.

The order in which you make your collide test is very important! On Method 3 for example, since you are pretty sure X pos is correct (because on the same column), test the Y first!