Sign in to follow this  
hspirdal

Sprite collision at higher movement rates

Recommended Posts

Hey guys, I'm currently developing a pong clone in C++ with SDL, but I'm having some problems with collisions at higher velocity levels. When looking for collisions, I check the current sprite's new position against all other sprites' positions and if their positions are within each other, I restore the old position and call a function that handles collision cases. While this method works superb with lower velocity levels, it doesn't work that well when a sprite moves at a higher rate because it can "jump past" another sprite and avoid collision. I've tried to sketch some scenarios to make it a little clearer. My highly theoretical "solution" is to simulate the new movement position into small bits and if neither of these collide, I'll assume the sprite's new position won't overstep another. Horrible example code to explain my thoughs:
//Our new sprite pos is [23,7] relative to our last pos ([x,y])
//Roughly 3 times x for each y

for(int i = 0; i < 7; i++)
{
	theSprite->MoveRelativePos(3, 1);
	for(int j = 0; j < game->sprites->size(); j++)
	{
		// Check if the sprite's new relative position collides with any other sprite, don't check against itself
		if(theSprite != sprites[j] && theSprite->CheckCollision(sprites[j]))
			return true; // Collision detected
	}
}
return false; // No collision detected




I think this method would be a really ugly and a tremdeous slow way of checking collisions. I could probably get away with it in Pong, but I can only imagine the horror of 30+ sprites... Does any of you have a better way of doing this? Edit: I'm also wondering if 35-40 miliseconds on average for a gamecycle is much in a game like pong? It sounds like a lot..

Share this post


Link to post
Share on other sites
The problem you describe is called 'tunneling'. The solution you propose is often referred to as 'subdivision'. This solution can be viable under certain circumstances, but it does have a number of drawbacks.

A superior solution is continuous collision detection (also referred to as swept or dynamic intersection testing). Fortunately, the swept test for AABBs is pretty straightforward; in fact, I think you can find an example implementation in the articles archive here on GDNet.

The test is simple and efficient, and so you should be able to get away with brute force (that is, test every unique pair of objects for intersection every frame) unless your object count gets out of hand. If you have a lot of objects (and 30 may be pushing it), you may need to add broad phase culling (which is a different topic).

Share this post


Link to post
Share on other sites
Thank you for your input, jyk. I found a lot of articles explaining the problem/solution, I haven't had the time to look more closely on it yet, though.
I'll check back later to give an update..

Share this post


Link to post
Share on other sites
Quote:
Original post by Andorien
Basically, instead of
ObjectPosition += MovementAmount;
CheckCollisions();
you have something more like
for(int i = 0; i < MovementAmount; i++)
{
ObjectPosition++;
CheckCollisions();
}
It looks like you're suggesting the incremental/subdivision method that the OP was referring to in his original post.

Again, I would recommend using a swept test instead - it'll be both more efficient and more accurate than what you propose.

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