I am not happy with the way i''m checking the objects in my game for collisions. I am writing a simple breakout clone and at the moment I have a loop that gets processed in every game frame that basically iterates through each brick in the game to check if (A) it is alive (hasn''t been destroyed yet), and then (B) if it''s alive, has it been hit by the ball. I''m pretty sure that processing this loop in every game frame isn''t doing my games performance any favours and this is just a simple game with relatively few objects, surely if a game has a lot more objects this would start to get ridiculus! How should I be doing this? - Hodglim Homepage

Simple way: Subdivide the bricks into a grid such that each brick only occupies one cell. Each frame, check which cells the ball intersects, and determine if it hits any bricks.

MSN

quote: Original post by msn12b

Simple way: Subdivide the bricks into a grid such that each brick only occupies one cell. Each frame, check which cells the ball intersects, and determine if it hits any bricks.

MSN

Sounds like that would be a good solution to the Breakout clone I am writing, thanks for the suggestion!, but how about a more generic solution, say for example the game was a Space Invaders clone, checking every single alien each frame to see if it has been hit by the players missile seems like major overkill.

How does everyone else do their collision detection?




- Hodglim
Homepage

Making your simple collision detecting fast is something I''m grappling with also.

Currently in my game all actors are contained in a couple of linked lists, one for each side. Ships on each side cannot collide with each other, so that cuts the # of comparisons in half.

That still leaves checking each ship on one side against all the others. One optimization is that you only need to check it one way -- so in total I''m checking 1/4 of the total # of ships (assuming an even distribution)

Bounding box checks are fast, so unless you have a lot of objects, this is good enough. If you do, however, have hundreds or more of objects, you may want to look into a sector or quadtree approach, where you split up your map into sectors, and keep track of which ships are in which sectors. Then, you only check collisions with ships inside the same sector, which can really help out speedwise. There are some gotchas here though, like checking ships that overlap two sectors, making sure they don''t get checked twice, etc.



- Remnant
- (Steve Schmitt)