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.

C/C++ > Serious issues with collision detection and classes...

#52803 - ChronicImpact - Sat Sep 03, 2005 11:45 am

Okay, I've just started work on my first serious game in C++ using classes, and I've hit a brick wall.

I figured that it would be easy enough to declare each object as a class, a class for the play, one for solids, etc.
The problem is checking for collisions.

I have an array of class CSolid for the solid objects, and a single class CPlayer, each with x and y values for their position. So if I want to check if the player has hit a solid... I have to check the x and y values of CPlayer against all the CSolids, upto about 500 per level... and to check the variables of 500 classes each vblank... gah, it's far too slow!

I've thought of plenty of ways to speed it up... only check the solids on screen, only check the ones in certian directions, blah blah... but all of it still requires checking the entire array of solids to see if they're on screen or in the right direction etc...

Keeping in mind that I'm not overly experienced with using classes, can any offer a few suggestions for a much neater way of doing this?

#52806 - Touchstone - Sat Sep 03, 2005 1:51 pm

What you probably want to do is some way of quickly finding which CSolids is on screen at the moment. For instance you could group all of your solids into columns that are, say, 2 screens wide. On top of that you could sort all your solids in each column based on their height position in the world.

That way you only need find the column in which the player currently is, find the first solid in that column that's close to the players height and check for collision with each solid until you've reached a solid that's to far away from the player.

Take a look at this image. [Images not permitted - Click here to view it] The red boxes are your CSolids and the arrows between them is how they are linked together in a linked list. Notice how one CSolid can be in two columns at once.

Since the player is probably more than one physics unit wide and it is in two columns at once you could either check the two columns or make the columns overlap by the width of the player.

As for moving CSolids, either you can dynamically link them into the correct location in each column, but that would require your linked list to be in RAM, or if you don't have to many moving solids just have a separate array for each column or even just one big array for the entire world.
_________________
You can't beat our meat

#52828 - sajiimori - Sat Sep 03, 2005 5:48 pm

Right, the problem is completely unrelated to the use of classes. It's all about sorting. The choice of sorting methods depends on the number of objects, their relative sizes and shapes, whether they move and how fast, how important it is for them to move when offscreen, the amount of memory you're willing to spend per unit of CPU savings, and any number of game-specific issues.