gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

Coding > Fast Collision detection in Shoot 'em ups

#7477 - GBA Coda - Wed Jun 18, 2003 3:07 pm

Hi Guys,

Anyone here know any fast ways of doing collision detection in shoot 'em ups?

kinda experiencing slowdown in my demo...

currently i have the player shooting 12 shots at a time, But when i get about 20 enemies on screen -*the game dies*-

help!

GBA Coda ( kinda )
_________________
Expression has no effect in function Main()!

#7496 - tepples - Wed Jun 18, 2003 6:30 pm

You're running into the O(n^2) comparisons of collision detection. Guess what else has O(n^2) comparisons? I'm guessing that the structure of your current comparison loop looks like that of a bubble sort. Collision detection is a type of search, and in general, sorting the data allows for more powerful search methods. Thus, game engine developers have improvised uses of sorting to speed things up.

Step 1: 1D sorting. Before doing collision detection, do a Shell sort[1] on the sprites, keyed by the top edge of the sprite's bounding box. Compare each sprite only to the following sprites whose top is above the current sprite's bottom. The speedup comes from the fact that in a top-to-bottom scan, once you've seen one sprite that's too far away to overlap, you've seen all the sprites that could potentially overlap.

Step 2: 2D sorting, or the sector method. This is much more complicated but can pay off when you have a LOT of larger sprites. Look it up on Google if collision detection turns out to be too slow even after adding sorting.

[1] Shell sort is better than quicksort for some applications such as collision detection. From frame to frame, the sprites will usually be nearly sorted. Shell sort is based on the insertion sort, which has better performance on nearly-sorted data than most quicksort variations.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

#7505 - Daniel Andersen - Wed Jun 18, 2003 9:16 pm

If you want to do pixel-based collision detection, i.e. for overlapping rectangles, save with each sprite-frame a table with a word (32bit) for each row in that frame; each word then contains the whole row interpreted as bits instead of bytes, that is, each non-zero pixel n has its corresponding n'th bit set.

In this way collision detection is easy; on each row, first do a logical shift on a row of one of the tables to make the X-coordinates match, then do a AND on the resulting words (e.g. the two rows from the tables). If the result is non-zero a collision has occured, if it is zero no collision has occured. And there you have it! This pixelwise collision detection algorithm is linear, O(n) that is!

Needless to say you also have to compare the right table rows if the two sprites' Y-coordinates do not match.

I have implemented this algorithm in my Basic + Golden Environment called GNES (which is to come soon). It is very powerfull.

#7529 - GBA Coda - Thu Jun 19, 2003 11:44 am

Thanks a lot Guys!

i'm gonna try that stuff :)
_________________
Expression has no effect in function Main()!

#13159 - shunyata - Sat Dec 06, 2003 5:51 pm

i cant help but wonder if insertionsort (shellsort with only the 1- increment) would be slightly faster on such small sets of nearly sorted data...?