The best way to do sprite collision detection

[bod/STAX]

As the title of this thread says I'm looking for the best way to do sprite collision detection (and fastest).

The sprite collision detection routines that I currently have in my game are functional rather than fast
and this is a major factor in speeding up my game.

Take for example enemy bullets against background tiles (although these aren't sprites the principle is
the same) I read the four co-ords for the first bullet (x1,y1 (top left) x2,y2 (bottom right)) I then go through
all the on-screen tiles reading x1,y1 (top left) x2,y2 (bottom right) and checking for a collision and if one
occours kill the bullet, read the next bullet and repeat. If no collision occours after reading through all
the tiles move onto the next bullet and so on until all bullets have been checked for.

As you can see using this method for all collision detections this extremely slow. Is there a real fast way
to do this and if so does anyone have some example code in 68000. In an ideal world one pass would be
the fastest to check all bullets against all tiles instead of the multipass method above.

I've been putting this off for so long now it's about time I tackled the issue. I have googled this subject
but all I seem to find is stuff in Java or C and mostly using 3D environments.

[SteveBagley]

How are you storing the background map, and does it change at all? I'm going to assume for this that your tiles are 16x16px and the bullets are the same size (although the same principle will hold regardless of the sizes) and that your background is stored as an array of indexes to tiles.

Your speed problem comes from the fact that you are comparing every bullet against every tile when in fact a bullet is only ever going to be interacting with four tiles (in the case I've outlined), so ideally you want to rewrite your code/data so that you only need to test a bullet with those four tiles. The way to do this is to convert your x,y coords for the bullet into indexes that look into your background map. In this case, you could simply divide the x,y pixel coord of the bullet by 16 and this would give you the x,y index into the background map. You can then use the four tiles around that one to see if the bullet has collided or not with the background.

Steve

[Nyh]

First take a step back.

You start with bullets and try to detect collision with sprites.

Is the other way around faster? Start with sprites and try to detect a collision with a bullet.

Which method is fastest cannot be said beforehand.

Note:

Code: Select all

* a0=pointer to sprite data
* a1=pointer to sprite on screen
   moveq  #0,d0
   add.l  (a0)+,d0
   sub.l  (a1)+,d0
   addx.l (a0)+,d0
   subx.l (a1)+,d0
   addx.l (a0)+,d0
   subx.l (a1)+,d0
   addx.l (a0)+,d0
   subx.l (a1)+,d0
   addx.l (a0)+,d0
   subx.l (a1)+,d0

Should result in d0=0 if the sprite was not touched by a bullet.

Hans Wessels

[bod/STAX]

Although the background tiles are stored as four 16x16 tiles as far as the co-ords are concerned the four
tiles are treated as one 64x16 tile.

The map data doesn't change at all and the map data is stored as a series of columns.

Each map tile has a data structure constructed thus:

Code: Select all

; all values are 2 bytes (1 word in size)
tile_num  equ 0
tile_flag equ 2
tile_x1   equ 4
tile_y1   equ 6
tile x2   equ 8
tile_y2   equ 10


tile_num is the offset value into the tile gfx data, tile_flag is a value multiplied by four (the
table for the code is made of two longword lookups) so if the value is 0 then the collision
detection code is unused (blank tile) or a value if 4 telling the code the do collision detection
for that tile (filled tile). The remaining are obviously the x1,y1,x2 and y2 for that tile.

[SteveBagley]

Why do you need to store the tile's position? You should be able to calculate it from the column its in…

Steve

[bod/STAX]

OK I think I should explain a bit how I've done the tiles in my game.

I think I can see what you're getting at. You can take the original level data and work out a what pixel point each tile is on-screen using that data and
then work along it as you go, altering the level data coordinates to represent exactly where they are on-screen right?

I've done it a little different.

As you know to get an endless scrolling landscape using hardware scrolling you build a copy of what your doing behind and when you've got a screen full
of tiles you jump back to the beginning of the screen data and repeat the process, overwriting the tiles you previously drew.

Well, I use exactly the same method with the tiles data structures in a buffer updating the coordinates in a window to match exactly where they are on
screen. When I put a new column of tiles on the screen off the far right I copy the data structure information for that tile into the said buffers far right
position and set the x1 coord to 320 and x2 coord to 384 the y1 and y2 coords are already set up during the map data conversion as these are never changed.

[bod/STAX]

First take a step back.

You start with bullets and try to detect collision with sprites.

Is the other way around faster? Start with sprites and try to detect a collision with a bullet.

Which method is fastest cannot be said beforehand.

Note:

Code: Select all

* a0=pointer to sprite data
* a1=pointer to sprite on screen
   moveq  #0,d0
   add.l  (a0)+,d0
   sub.l  (a1)+,d0
   addx.l (a0)+,d0
   subx.l (a1)+,d0
   addx.l (a0)+,d0
   subx.l (a1)+,d0
   addx.l (a0)+,d0
   subx.l (a1)+,d0
   addx.l (a0)+,d0
   subx.l (a1)+,d0

Should result in d0=0 if the sprite was not touched by a bullet.

Hans Wessels

I'm intrigued with this idea. But I am unsure exactly how it works.

For example is this how it works: a0=players sprite data, a1=enemy bullet sprite data.

Code: Select all

moveq #0,d0
add.l (a0)+,d0 ; add players x1,y1
sub.l (a1)+,d0 ; subtract bullets x1,y1
add.l (a0)+,d0 ; add players x2,y2
sub.l (a1)+,d0 ; subtract bullets x2,y2
; if d0=0 no hit


Therefore this is quicker than movem.w's and cmp.w's for hit checking?

[LaceySnr]

I'm intrigued with this idea. But I am unsure exactly how it works.

For example is this how it works: a0=players sprite data, a1=enemy bullet sprite data.

I believe what he's actually doing (I've not even considered this before and it's a neat idea) is actually comparing the sprite image data with what's in the screen buffer where the sprite is drawn. So if you're using a palette and your sprite's first four bytes are FF, F0, F0, FA, and the same four bytes appear in the screen buffer, the result of adding the value of each byte from the sprite data, and subtracting the value of each byte from the screen data should be zero:

Set D0 to zero
Add FF (from Sprite) to D0
Sub FF (from Screen) from D0
Add F0 (from Sprite) to D0
Sub F0 (from Screen) from D0
etc.

If the total sum is not 0 then you know something else has been drawn on top of the sprite. I guess this would have issues with areas of the sprite that should be masked off so you might need to combine that in to ignore pixels which should be transparent (which would be showing the background and hence not match the sprite's data).

[bod/STAX]

Yes I see. Really neat idea.

I'll give it a go later on.

I was thinking last night in bed that my original interpretation wouldn't work.

Thinking about it all you would have to do is keep checking the players sprite to see if it's exactly the same as the original data
if anything has caused a change then you've died. This would cover everything from hitting enemy bullets, enemies and background
tiles removing all of those checks.

[Nyh]

So if you're using a palette and your sprite's first four bytes are FF, F0, F0, FA, and the same four bytes appear in the screen buffer, the result of adding the value of each byte from the sprite data, and subtracting the value of each byte from the screen data should be zero:

Set D0 to zero
Add FF (from Sprite) to D0
Sub FF (from Screen) from D0
Add F0 (from Sprite) to D0
Sub F0 (from Screen) from D0
etc.

If the total sum is not 0 then you know something else has been drawn on top of the sprite. I guess this would have issues with areas of the sprite that should be masked off so you might need to combine that in to ignore pixels which should be transparent (which would be showing the background and hence not match the sprite's data).

Indeed.
Instead of add and sub you can use XOR. But especially on symmetrical objects changes are high data of several lines cancel out. ADD and SUB are better but you can loose data at edges. By using ADDX end SUBX you prevent data getting lost in carry bits.

When the sprite has an irregular shape you can use and AND to mask out unwanted data (the same AND mask used to draw the sprite can be used.

Usually looking for changes in one cleverly chosen bit plane is enough to detect a collision reducing the amount of data to process.

Hans Wessels

[bod/STAX]

There is a bit of a problem.

This method surely is only for pre-shifted sprites whereas my game uses blitted sprites. If this is case I would
have to copy an image of the sprite from the screen to a buffer for checking.

Also DevPac developer returns an 'addressing mode not allowed' error for addx.l (a0)+,d0 and subx.l (a0)+,d0
on a 68000 and I've never had cause to use these instructions before.

[bod/STAX]

OK after a bit of a coding session last night I finally implimented this technique into my game and it works!!!

I had to do a bit of re-jigging of the order of how things are draw into the following (BTW no sprites are masked):

1. Draw the players sprite
2. Draw anything that doesn't kill the player (player bullets, force pod, background stars etc.)
3. Take a copy of the players sprite for comparison
4. Draw anything that can kill the player

On the surface it does seem to make the game marginally faster however what I may have gained I may loose
as using this method does bring up a bit of a problem that I hadn't originally thought of.

When a baddie is killed it is still active on-screen it's just going through the explosion sequence before being
removed. Using my old method a check is done when the player moves over an enemy to turn off the collision
detection for a particular baddie if it's going through the explosion sequence so you can move over it. Using
this technique the baddie is still deemed active and you die if you hit an explosion.

One solution is to call the baddie draw routine twice both before and after the players sprite's copy is taken
only drawing the baddie before if it's going through the explosion and only drawing the baddie after if it's
not going through the explosion sequence.

On my previous post I stated that DevPac doesn't allow you to use addx.l (a0)+,do and subx.l (a0)+,d0 so this
is how I got it working:

Code: Select all

* a0=pointer to sprite data
* a1=pointer to sprite on screen
   moveq  #0,d0
   move.l (a0)+,d1
   addx.l d1,d0
   move.l (a1)+,d1
   subx.l d1,d0
   move.l (a0)+,d1
   addx.l d1,d0
   move.l (a1)+,d1
   subx.l d1,d0

   move.l (a0)+,d1
   addx.l d1,d0
   move.l (a1)+,d1
   subx.l d1,d0
   move.l (a0)+,d1
   addx.l d1,d0
   move.l (a1)+,d1
   subx.l d1,d0

   move.l (a0)+,d1
   addx.l d1,d0
   move.l (a1)+,d1
   subx.l d1,d0
   move.l (a0)+,d1
   addx.l d1,d0
   move.l (a1)+,d1
   subx.l d1,d0


I tried to impliment the above with movem.l like this:

Code: Select all

* a0=pointer to sprite data
* a1=pointer to sprite on screen
   moveq #0,d0
   movem.l (a0)+,d1-d6
   addx.l d1,d0
   addx.l d2,d0
   addx.l d3,d0
   addx.l d4,d0
   addx.l d5,d0
   addx.l d6,d0
   movem.l (a1)+,d1-d6
   subx.l d1,d0
   subx.l d2,d0
   subx.l d3,d0
   subx.l d4,d0
   subx.l d5,d0
   subx.l d6,d0


However it doesn't work. Is this something to do with how addx and subx works?

*** EDIT ***

I am going to keep this technique in the game as it fixes something that has been on my mind for quite some time:

How to do all the collision detection for the green dots that are left behind by the baddies on stage four!

This will out-do the Amiga version as they had to plot groups of four dots at once. Using this idea I can plot and check
individual dots just like in the arcade original!

[bod/STAX]

All is working great now using this method. I've also manage to optimise the collision code
and it now works with movem. The explosions are working as they should too.

It seems I was a bit hasty in thinking this would sort out those level 4 dots. If I can get this
method to work as to check for collisions with the background tiles then this would sort out
the level 4 dot collisions as the dot trails would become a part of the background. Oh well
something else to think about and work on over this bank holiday weekend.

[LaceySnr]

Sounds like you're motoring along now Going to give this same technique a crack too once I've gotten as far as needing collision detection... still working out issues in my sprite routines a the moment.

You have any builds available to play around with?

[Nyh]

Remember the first ADD or SUB should be a normal ADD or SUB because you don't want to use the x-bit the first time.

It it possible to precalc the sums?

If you first draw an empty sprite (all zero bits) the sum is known and should be 0. At the last stage you can OR in the sprite because the masking is already done.

Hans Wessels

[bod/STAX]

Got this trick working detecting background tiles now. Unfortunately it requires a seperate check, though.

[Codetapper]

May I ask what kind of game is this? As depending on the game, you might be able to optimise even further. For example, if it's a horizontally scrolling (only) game, then any tile that's above or below the bullet will never hit it (assuming the tiles don't move), so there's no need to check those tiles. Ditto for a vertical scroller, any tiles to the side of the bullet wouldn't hit it.

By losing some memory, you could store the tiles into lists of the X or Y block, and just test the strip the bullet is in (or possibly 2 strips if the bullet is directly between 2 strips of tiles).

The coder of SWIV also sorted bullets into a particular order such that once a bullet had gone past a certain point, he wouldn't need to check further bullets for collision with that object. More here in John Croudy's interview (in the St Dragon section).

[bod/STAX]

Thank's I'll check the interview later on.

Earlier on in this project I had thought that some sort of sorted sprite routine would be quite fast but I am
unsure about the quickest was to do the sorting (I only know how to do bubble sorting).

As for the game - It's a remake of R-Type for the Atari STE. I released a demo-version on X-Mas day last
year and someone uploaded a video of it to YouTube. Here's the link:

https://www.youtube.com/watch?v=PBFfK_v_co0

[Codetapper]

For player collisions: If each bullet knows who fired it (the player or an enemy) you can test all enemy bullets against the player position, and with a single compare (testing if the bullet is too far right of the player to start with) you will probably be able to skip checking the remaining points about 80% of the time. When you also compare the Y co-ordinates, that'll eliminate even more too. After all, the player being hit should be rare, so don't assume that will take place and waste time doing pixel collision.

I would also think at that stage that you check for a collision against the bolt-on weapon (whatever it's called) that can attach to your ship and the circling dome weapon thing that sits above you. If it hits those other objects, then presumably the bullet gets destroyed. And assuming you cannot move your ship faster than a bullet, once a bullet has passed your ship, it should never be able to hit you. So you could flag that bullet as not needing to be checked again. (For simple cases like a bullet travelling in a mostly horizontal or vertical trajectory).

For enemy collisions: This would be a little trickier, as there's so many weapons. For horizontal player bullets, you could store them in lists indexed by their Y coordinate (rounded to the nearest block of 16 for example), and then an enemy that's say 56 pixels down the screen would only need to check against bullets in the 56/16 = 3.5 = 3rd row (counting from 0). There might be 20 bullets on-screen but only a couple in that row. That'd save a lot of compares. You might need to check a couple of rows if the bullet is between 2 rows.

The bullets that follow the landscape would be effectively moving between the lists as they alter their Y-co-ordinate, but the same system should work for those.

The blue laser lines would cause more of a problem, from a brief look at the game I guess they're an 8x8 pixel block that acts as a diagonal bullet that follows the landscape but leaves a trail of "static" bullets that survive only for a few frames? Is that how they work? If so, I guess the system I suggested above would still work, just moving the front bullet between lists as required. The trail is really just a very short lived static "mine" that disappears after a few frames.

In the (Amiga) horizontally scrolling game I'm making, all the objects (which are enemies, bullets and collectables) have their own update routine, and they check for whatever is sensible. For collectables, they check if the player has hit them and add points to the score then remove themselves from the list. For enemies, they see if they have touched the player (with simple rectangle compares) etc.

Because the objects stay on the screen, I keep a sorted list of the objects (in ascending Y order) and do a bubble sort over it. Because the lists remains for the next frame, it's already sorted most of the time so the bubble sort is very fast. Generally the sorting only has to switch one or two items around when they move, as most moving objects only move a few pixels each frame. If I add a new object to the list (and it doesn't happen very often), it will have to bubble it into position once, and if an object is destroyed, I just copy the rest of the list up one position to overwrite the gap. So bubble sorts are not always completely useless!

Good luck, hopefully you can get the frame rate up a bit!

[bod/STAX]

What you've described above is pretty much how everything works ATM.

Apart from any kind of sorting for objects.

[Codetapper]

In that case, is it the collision detection that's slowing the game down when there's a lot happening, or plotting all the objects?

[bod/STAX]

It's both really. I decided to make all the sprites unmasked as an obvious speed up but when I decided to remove any collision detection code
that isn't required during demo-mode I saw that where there was usually some slowdown it didn't seem as severe.

When it comes to blitter sprite plotting I am still using the old restore old background/store new background/plot sprite method. I am taking
sprite depth into consideration in that a three plane sprite will only have the three planes updated. Small sprites are done via pre-shifted
software sprites and are either two-plane or four plane so I can use movem.l addressing.

A further obvious speed-up is to have a background screen so I just have to restore the background and only restore the biplanes changed
instead of all four planes due to OR'ed sprites. I made a half-assed attempt at this a couple of months ago but couldn't the restoration to
work quite right. I'll have another go over the weekend.

A more obvious solution as I've mentioned in other posts is to drop the frame rate down to 12.5 instead of 25fps. Whilst this does pretty much
fix any obvious slowdown the sprite animations just look terrible. It may just be the case if after every optimisation I can think of has been
done I'll just release it and people will just have to put up with it and from a speed point of view it will be like Super R-Type on the SNES.

[mc6809e]

A more obvious solution as I've mentioned in other posts is to drop the frame rate down to 12.5 instead of 25fps. Whilst this does pretty much
fix any obvious slowdown the sprite animations just look terrible. It may just be the case if after every optimisation I can think of has been
done I'll just release it and people will just have to put up with it and from a speed point of view it will be like Super R-Type on the SNES.

Yeah, 12.5 fps looks rough.

I wonder if black frame insertion would help. Black frame insertion greatly improves the appearance of animations at 25 fps on a 50Hz display. One visible frame 12.5 times per second might be too low, though.