# Collision detection algorithm suggestions

This topic is 5464 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hey all, I'm making a very simple game library, designed to make games like the ZX Spectrum ones Jet Set Willy, Manic Miner, Jetpac, etc. The way it works is similar to the D3DX Framework. The user links with my .lib and derives from CApplication. For sprites, they derive from CSprite and set the sprites size, position and velocity. The base application processes all sprites every frame, updates their position, and checks for collisions. I've never needed to do collision detection before, and I'm a bit stuck for ideas how to go about it. A sprite could be stationary (for triggers and things), it could move at a reasonable speed (the player), or it could move across the entire screen in one frame (bullets, etc). There could be any number of sprites on screen at once, but anything over 500 or so will be way too many. I'd expect an average of 50 sprites on screen at once. Here's what I have at the moment (just for testing really). It only matches collisions if they happen during that frame (not between frames), and it doesn't adjust the sprites position so it doesn't intersect the object:
for(DWORD i=0; i<m_vSprites.size(); ++i)
{
// Update position //
m_vSprites->m_vPos += (m_vSprites->m_vVelocity*(float)(dTime/1000.0));

// Call update tick //
m_vSprites->Tick(dTime);

// Render textured sprites //
if(m_vSprites->m_pTexture)
{
D3DXVECTOR3 vPos(m_vSprites->m_vPos.x,m_vSprites->m_vPos.y,0.0f);
D3D_CHECK(m_pSprite->Draw(m_vSprites->m_pTexture->GetTexture(),
&m_vSprites->m_rcTexture,NULL,&vPos,0xffffffff));
}

// Check for collisions //
for(DWORD j=0; j<i; ++j)
{
SpectrumRect rcFirst(m_vSprites->m_vPos.x,m_vSprites->m_vPos.y,m_vSprites->m_vSize.x,m_vSprites->m_vSize.y);
SpectrumRect rcSecond(m_vSprites[j]->m_vPos.x,m_vSprites[j]->m_vPos.y,m_vSprites[j]->m_vSize.x,m_vSprites[j]->m_vSize.y);
if(CheckCollision(rcFirst,rcSecond))
{
m_vSprites->OnCollision(m_vSprites[j]);
m_vSprites[j]->OnCollision(m_vSprites);
}
}
}


CheckCollision() is very hacky and converts the 2 parameters to RECT structures, and then checks for collisions with IntersectRect(). So, does anyone have any suggestions how I should do collision detection? I need to loop through all the sprites, and check for collisions with other sprites. But I need to see if the sprite collided with several other sprites in the frame (a bullet may pass through several sprites), and process the collisions in order. I don't really know how to go about checking for collisions between frames. I supppose I could form a rectangle of possible collisions like this, where p1 is the initial position, p2 is the end position, and a, b and c are objects in the colision rectangle:
+--+--------------+
|p1|            a |
+--+              |
|         b       |
|              +--+
| c            |p2|
+--------------+--+
But then, I'm a stuck on how to check for collisions in that ractangle. Thanks in advance, Steve

##### Share on other sites
Lets check if the point (x,y) is in the rectangle (xa1, ya1, xb1, yb1). It is if x in [xa1 xb1] and y in [ya1 yb1].
Now your rectangle moves, let's say according to a starting position and a speed (xa1(t) = xa1(0) + xv*t, same for other coordinates). You now want to check if it exists one time t so that x in [xa1 xb1] and y in [ya1 yb1]
x >= xa1(0) + xv*t => t <= (x-xa1(0))/xv
x <= xa2(0) + xv*t => t >= (x-xa2(0))/xv (same with y).

Like that, you determine the interval of time during wich the point will be inside the rectangle. If you want to check the collision of two rectangles, you can say that they interact iif one of both points of the second one collide with the first rectangle.
If both rectangles are moving, you can rewrite the equations and see that it is like if only one of them was moving, with a speed equal to the sum of the two speeds.

##### Share on other sites
I see. I think :P The main problem I'm having is that I have to assume that all the sprites are moving.
I'll try and get this working on paper, thanks a lot.

##### Share on other sites
There's an article on gamasutra (which I believe is linked to from the articles section here) which describes a number of collision tests. One of them is a swept-AABB test, which with the z component removed might be very handy for you. You would send it the bounding rects and velocities of each sprite, and get back a time of first collision (if any).

I'm not positive but I imagine objects such as bullets could be treated as AABBs with zero-length extents. This way you could handle all objects in the same way.

There are certainly ways you could reduce the number of collision tests, such as by using a quadtree or even just a regular grid. But, even with the brute-force approach, keep in mind that once you've tested object A against object B, you needn't then test B against A. This can be accomplished by starting the inner loop from the outer loop counter (+ 1).

Here's some pseudocode for the brute-force method.

// Assume we've already updated all the objects' positionsvoid CheckCollisions(){    for (int i = 0; i < object.size() - 1; i++)    {        for (int j = i + 1; j < objects.size(); j++)        {            float time = SweepTest(objects.bbox,                objects[j].bbox, objects.vel, objects[j].vel);            if (time < 1.0f)            {               objects.pos = objects.oldpos + objects.vel * time;               objects[j].pos = objects[j].oldpos + objects[j].vel * time;             }        }    }}

Note that here vel is the displacement from the last time step, not the 'per second' velocity.

Anyway, that's just off the top of my head so I may have overlooked something. But maybe it will be of some help.

##### Share on other sites
Cool, that looks perfect for my needs, thanks! I was already doing the loop for the collision test as you said (loop up to the current object-1).
Rating++

##### Share on other sites
Quote:
 Original post by VincentLascauxLets check if the point (x,y) is in the rectangle (xa1, ya1, xb1, yb1). It is if x in [xa1 xb1] and y in [ya1 yb1].Now your rectangle moves, let's say according to a starting position and a speed (xa1(t) = xa1(0) + xv*t, same for other coordinates). You now want to check if it exists one time t so that x in [xa1 xb1] and y in [ya1 yb1]x >= xa1(0) + xv*t => t <= (x-xa1(0))/xvx <= xa2(0) + xv*t => t >= (x-xa2(0))/xv (same with y).Like that, you determine the interval of time during wich the point will be inside the rectangle. If you want to check the collision of two rectangles, you can say that they interact iif one of both points of the second one collide with the first rectangle.If both rectangles are moving, you can rewrite the equations and see that it is like if only one of them was moving, with a speed equal to the sum of the two speeds.

That's what we use for our game, along with x-sorting to reduce the amount of tests.

Here's an interesting snippet that implements this algorithm without using any divisions. It took some time to get this thing working properly ;)
struct object {	float xmin, ymin;	float xmax, ymax;	float xvel, yvel;};bool collision(const object &p1, const object &p2) {	// calculate relative position and velocity	object o;	o.xmin = p1.xmin - p2.xmax;	o.ymin = p1.ymin - p2.ymax;	o.xmax = p1.xmax - p2.xmin;	o.ymax = p1.ymax - p2.ymax;	o.xvel = p1.xvel + p2.xvel;	o.yvel = p1.yvel + p2.yvel;	// translate negative velocities into positive ones	float swap;	if(o.xvel < 0) {		o.xvel = -o.xvel;		swap = o.xmin;		o.xmin = -o.xmax;		o.xmax = -swap;	}	if(o.yvel < 0) {		o.yvel = -o.yvel;				swap = o.ymin;		o.ymin = -o.ymax;		o.ymax = -swap;	}	// check for collision independently in each axis	if(o.xmin >= o.xvel || o.xmax <= 0) return false;	if(o.ymin >= o.yvel || o.ymax <= 0) return false;	// no movement in one axis so it doesn't matter when the collision	// occurs in the other axis (removes a "division" by zero)	if(!o.xvel || !o.yvel) return true;	// verify that the two collision periods overlap	// (xmin/xvel < ymax/yvel && xmax/xvel > ymin/yvel)	if(o.xmin * o.yvel >= o.ymax * o.xvel) return false;	if(o.xmax * o.yvel <= o.ymin * o.xvel) return false;	return true;}

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 11
• 10
• 9
• 15
• 22