Sign in to follow this  
krej

What's a good way to go about checking for collisions with many different objects?

Recommended Posts

I'm trying to create a clone of the flash game Avalanche: http://www.addictinggames.com/action-games/avalanche.jsp

In the game, there are many blocks that fall from the top of the screen and then land on the ground or another block. Once they are on the ground they don't move ever again, but other blocks need to still test against them to see if they landed on top of it. The player(which is a rectangle) also needs to perform collision tests against all of the blocks so he doesn't run through any of them.

How should I go about implementing this? Right now I have a basic prototype of my original thoughts on it, but it is very inefficient and lags when I run the game on my android phone after more than 10-20 blocks appear on the screen.

The logic behind my code is, I have two ArrayLists that contain all of the blocks, one for blocks that are falling(the "Falling Block" list) and one for blocks that have landed on the ground or another block(the "Sitting Block" list). I have one block spawn every few seconds at the top of the screen, and it is placed in the "Falling Blocks" ArrayList. Every frame I check to see if that block has either hit the ground, and if not then I go through every block in the "Sitting Block" list and check to see if the current falling block has collided with any of the sitting blocks. If the current falling block has collided with either the ground or any of the "Sitting Blocks", then I move that block from the Falling Blocks list over to the Sitting Blocks.

This works decently on my desktop and I can run it fine at a constant 60 FPS. However, I'm creating this game for Android and when I try to run it on my phone, it starts to lag after I get about 15 or so blocks on the screen. The point of the game is to try to climb up on the blocks and get as high as you can, and I have it so that blocks so far beneath you that you'll never see again get deleted, and this keeps the game from ever getting below 35 FPS, but I'd still like to learn the proper way to perform collision detection with a bunch of objects like this so I can hopefully keep my frame rate at 60.

Share this post


Link to post
Share on other sites
You want some sort of spatial partitioning to cut down on the number of tests you need to do. For example, you might just divide the space up into a grid and then test only objects in the same grid cell for collision. (Actually, slightly more complex, since an object may straddle several grid cells if it's at the edge or larger than your grid size - but you get the idea.) Another simple data structure you can use is a quadtree.

Share this post


Link to post
Share on other sites
Do you know of any good articles about Quadtrees? I have a vague idea on how they work, but implementing them seems like it is on a whole new level.

I get the basic idea, how each node has 4 children, and the 4 children are just 4 quads inside the parent quad. Then once you have all of your quads and objects in them, I can see how it cuts down on what you need to test against, but what I don't get is how it works in a realtime game. What I mainly don't get is how you easily move a moving object from one quad to another on the fly. And again, actually implementing all of this in a game is confusing to me.

Share this post


Link to post
Share on other sites
For this particular case, there is actually a much easier solution than using any kind of "real" collision system. Since you want the blocks to stop when they hit the top of another block, and once stopped, blocks cannot do anything strange like roll sideways, you actually don't care about checking individual blocks at all. The only thing you need to know is, what is the height of the top of the highest block in this column (if you notice avalanche breaks the playing field up into distinct columns that the blocks line up with)?

So keep two things: A list of all blocks that are falling, a list of blocks that are still above the rising water level but have stopped moving, and an array of the height of each column

For example, lets say you have the following grid of blocks (it's 10 columns wide):
[font="Lucida Console"]
x[/font]
[font="Lucida Console"]xx xx
xx xx
xx xx
xx x xx x[/font]

Then your array of highest points array would look like this: columnHeight = { 4, 5, 0, 1, 0, 4, 4, 2, 0, 1 }

Now for each falling block you only need to check if the bottom of the block has touched the top of any of the columns. So if you are dropping a block like this:

[font="Lucida Console"] xx
xx <-- our new block

[/font][font="Lucida Console"] x
[/font][font="Lucida Console"]xx xx
xx xx
xx xx
xx x xx x[/font]

You need to check if it has touched the top of column 1 or 2, and none of the others. That's two simple < comparisons, and rocket fast. Once it does touch either of those columns, to stop it from moving you add it to the list of blocks still above the water (just so you can continue to draw it, there will be no other tests done against it), and then you update the heights of columns 1 and 2 to be 7 and 7, respectively, so you now have this:

[font="Lucida Console"] xx
xx
[/font][font="Lucida Console"] x
[/font][font="Lucida Console"]xx xx
xx xx
xx xx
xx x xx x[/font]

columnHeight = { 4, 7, 7, 1, 0, 4, 4, 2, 0, 1 }.

And then rinse and repeat for each falling block until they also hit the top of the columns.

Share this post


Link to post
Share on other sites
I'm not sure how your game is built up, but another way to go would be to turn all blocks that have stopped into one single hitbox.
So instead of having separate blocks to check collisions with you instead have one combination of blocks that you check collision against.
Again it all depends on how you do collision checks as it is a lot more difficult to do collision testing against something with all kinds of crevices and stuff in it.
This would however greatly reduce the lag as all falling blocks would merge together into one once they land.

Share this post


Link to post
Share on other sites
I appreciate your ideas you gave me, however I think I want to go with using quadtrees or something similar. Your way with keeping the heights of each column and just comparing that does seem like the easiest way to go, however I've created games that work like that before and now I want to try something new with this game(especially because it seems like learning how to use quadtrees could help me down the line when I need to do collision detection against things that aren't falling blocks). Also, quadtrees seem more badass and I'll be able to feel more proud of myself after I successfully learn how to use and implement them.

Thanks for your input though!

Share this post


Link to post
Share on other sites
I think you're going to have much better success if you use a 2d physics library. You'd be able to do something like that game really easy. Those libraries handle collisions for you, and they can handle many many particles.

Personally, I use chipmunk-physics, but others use Box2d (google both of those).

Good Luck.

Share this post


Link to post
Share on other sites
I tried using Box2d but I found it too be too realistic and too complicated. Once my blocks land, I don't want them doing anything else, just sitting there. With a physics engine, they'll always fall off if they land on the edge of another box. Also I wasn't able to think of a way to do things like make the player be able to stick to the sides of boxes, since that doesn't really obey the laws of physics.

Is it possible to do things like that? I haven't looked into it much before I just gave up with it.

Share this post


Link to post
Share on other sites
[quote name='krej' timestamp='1319077748' post='4874532']
I tried using Box2d but I found it too be too realistic and too complicated. Once my blocks land, I don't want them doing anything else, just sitting there. With a physics engine, they'll always fall off if they land on the edge of another box. Also I wasn't able to think of a way to do things like make the player be able to stick to the sides of boxes, since that doesn't really obey the laws of physics.

Is it possible to do things like that? I haven't looked into it much before I just gave up with it.
[/quote]

You should be able to make the friction between two objects massive, so they will "stick" together once they touch another.

As for the man jumping, there should be a way to do that as well, using friction, and knowing he's still in contact with the box. You'll have to do a little more research into it, or go to the forums and ask for help.

I know the chipmunk physics guy is always helpful with these sorts of things.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this