#### Archived

This topic is now archived and is closed to further replies.

# 2d collsion problem...kindly help

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

## Recommended Posts

Hello, I am making a 2d scrolling game like super mario bros. And having trouble with the collision detection. Well its easy to find out when the objects collide using the normal Rectangle collsion method. But thing is i need to do vector based collsion so that my collsions are perfect or nearly perfect....right now they are not good. Collision is ok sometimes but the when game runs on slower frame rate everything is messed up. Kindly help ... i cant figure out how to do this using vector collision or line intersection thingy.....also one more thing ....when i collide with another rect i need some additional info..i-e i have collide with sides,bottom or top??. Right now i am stuck so please help..........Thanks a lot Omar Alvi

##### Share on other sites
If you''re using bounding boxes, then you should know where the boxes cross each other. This will tell you if the collision is from above or from the sides.

As for a perfect collision detection, you can do a two-phase check. The first check would be a bounding-boxes one; if the bounding boxes are not colliding, there certainly is no collision. If they are colliding, then you should check the two object more thoroughly. If your object are convexes, then you might just draw an imaginary line from center to center, go along that line and check the actual pixels along the way, to see if they collide.

##### Share on other sites
Ammm, but i want a vector based collsion detection. There are no convexes as such ....the thing is that when my hero moves fast it passes through some objects and this specially happens when i am running the game on a bit low frame rate....so i guess vector based solution for collsion is required here...

##### Share on other sites
have a look at this tutorial, it may be of some use:
http://www.flipcode.com/tpractice/issue01-pf.shtml

##### Share on other sites
you can use a combination of swept tests, and overlap tests as fallback solutions when objects interpenetrate.

swept tests should be easy. box, spheres, triangles, ...

for convex polygon-based collisions (rectangles, triangles, hexagons, ect...), it should just fall down to doing vertex-segment collisions.

for a 2D side scroller, if you won''t use any collision response (like objects stop at each collisions, without bouncing off), then it''s quite easy.

anyway, I can put down a framework to do collision tests on general convex polygons. I''ll just go along, coz I want to code something like that myself in the future, as a tutorial or something.

first, the polygon structure.

struct CPolygon
{
Vector *m_axVertices;
int m_iNumVertices;
};

then the moving body

struct CBody
{
CPolygon* m_pxPolygon;
Vector m_xPosition;
Vector m_xDisplacement;
};

then the methods

bool CPolygon::Overlap(const CPolygon& xPoly, const Vector& xRelPos, Vector& xMTD) const;
bool CPolygon::Collide(const CPolygon& xPoly, const Vector& xRelPos, const Vector& xRelDisp, float& t) const;

bool CBody::Update(dt);
bool CBody::CalculateDisplacement(dt);
bool CBody::Collide(CBodies* axBodies, int iNumBodies);
bool CBody::Collide(CBody& xBody);
bool CBody::ProcessCollision(CBody& xCollidingBody, float t);
bool CBody::ProcessOverlap(CBody& xOverlappingBody, const Vector& MTD);

I will need a trace function, which will detect if a moving particle intersects a segment.

bool Trace(const Vector& xParticlePos, const Vector& xParticleDisp, const Vector& S0, const Vector& S1, float& t);

t is a fraction of the displacement, when the particle collide.

once we found a collision, the displacement of the body is clamped to ''t''.

for overlaps, when two body are found to be overlapping, the Minimum Translation Distance (MTD) is return, which is basically a ''Push'' vector, to push the bodies away so they stop intersecting.

the algo will work like this

bool CBody::Collide(CBody& xBody)
{
Vector xMTD;
float t;
Vector xRelPos = m_xPosition - xBody.m_xPosition;
Vector xRelDis = m_xDisplacement - xBody.m_xDisplacement;

if (m_pxPolygon->Overlap(*(xBody.m_pxPolygon), xRelPos, MTD))
{
ProcessOverlap(xBody, MTD); // overlap found. no need to test for swept collisions

return true;
}

if (m_pxPolygon->Collide(*(xBody.m_pxPolygon), xRelPos, xRelDis, t))
{
ProcessCollision(xBody, t);
}
}

// detect is a moving particle intercept a segment.

bool Trace(const Vector& xParticlePos, const Vector& xParticleDisp, const Vector& S0, const Vector& S1, float& t)
{
Vector S = S1 - S0;
Vector N(-S.y, S.x); // ''normal'' plane of the segment

float d = S * N; // distance of plane to origin

// calculate time of intercept to the line passing through the segment.

// it''s a standard ray-plane intersection test

float numer = N * xParticleDisp;
float denom = d - (xParticlePos * N);

if (fabs(numer) < 1.0fE-8)
return false;

ttrace = denom / numer;

// time of collision negative, or too late

if (ttrace < 0.0f || ttrace > t)
return false;

// chek if the particle hits in the boundaries of the segment.

Vector P = xParticlePos + xParticleDisp * t;
Vector D = P - S0;
float ds = D * S;
float s2 = S * S;
float u = ds / s2;

if (u < 0.0f || u > 1.0f)
return false;

t = ttrace;
return true;
}

// trace each vertex of a poly against the edge of another poly

bool CPolygon::Trace(const CPolygon& xPoly, const Vector& xRelPos, const Vector& xRelDisp, float& t) const
{
bool bCollided = false;

for(int i = 0; i < m_iNumVertices; i ++)
{
Vector xParticlePos = GetVertex(i) + xRelPos;
for(int j = 0; j < xPoly.m_iNumVertices; j ++)
{
Vector xS0 = xPoly.GetVertex(j);
Vector xS1 = xPoly.GetVertex(j+1);
bCollided |= Trace(xParticlePos, xRelDisp, xS0, xS1, t);
}
}
return bCollided;
}

// trace of both poly against the other poly''s edge. take the earliest as the collision time

bool CPolygon::Collide(const CPolygon& xPoly, const Vector& xRelPos, const Vector& xRelDisp, float& t) const
{
t = 1.0f;
bool bCollided = false;
bCollided |= Trace(xPoly, xRelPos, xRelDisp, t);
bCollided |= xPoly.Trace(*this,-xRelPos,-xRelDisp, t);

return bCollided;
}

// two objects collided at time t. stop them at that time

void CBody::ProcessCollision(CBody& xBody, float t)
{
m_xDisplacement *= t;
xBody.m_xDisplacement *= t;
}

// two objects overlapped. push them away from each other

void CBody::ProcessOverlap(CBody& xBody, const Vector& xMTD)
{
m_xPosition += xMTD * 0.5f;
xBody.m_xPosition -= xMTD * 0.5f;
}

the overlap detection is trickier. It''s based on the separation axis method, and it is used to return the MTD between the two polygons.

// calculate the projection range of a polygon along an axis

void CPolygon::GetInterval(const Vector& xAxis, const Vector& xOffset, float& min, float& max) const
{
float h = xOffset * Axis;
min = max = (GetVertex(0) * xAxis) + h;

for(int i = 1; i < m_iNumVertices; i ++)
{
float d = (GetVertex(i) * xAxis) + h;

if (d < min) min = d; else if (d > max) max = d;
}
}

// check if two projection range of polygons overlap along an axis

// if so, calculate the amount of overlap

bool CPolygon::IntervalIntersect(const Vector& xAxis, const CPolygon& xPolygon, const Vector& xOffset, float& depth) const
{
float min0, max0;
float min1, max1;

GetInterval(xAxis, xOffset, min0, max0);
xBox.GetInterval(xAxis, Vector(0, 0), min1, max1);

if (min0 > max1 || min1 > max0) return false;

float d0 = max1 - min0;
float d1 = max0 - min1;

if (d0 < d1)
depth = d0;
else
depth = d1;

return true;
}

// check if two polygons overlap, using the separation axis method.

// if they overlap, use the axis with the minimum of overlap as the MTD vector

bool CPolygon::Overlap(const CPolygon& xPoly, const Vector& xOffset, Vector& MTD) const
{
Vector xAxis [64]; // note : a maximum of 32 vertices per poly is supported

float fDepth[64];
int iNumAxes=0;

for(int i = 0; i < m_iNumVertices; i ++)
{
Vector E0 = GetVertex(i);
Vector E1 = GetVertex(i+1);
Vector E = E1 - E0;
Vector N(-E.y, E.x);

xAxis[iNumAxes] = N;

if (!IntervalIntersect(xAxis[iNumAxes], xPoly, xOffset, fDepth[iNumAxes]))
return false;
iNumAxes++;
}

for(int i = 0; i < xPoly.m_iNumVertices; i ++)
{
Vector E0 = xPoly.GetVertex(i);
Vector E1 = xPoly.GetVertex(i+1);
Vector E = E1 - E0;
Vector N(-E.y, E.x);

xAxis[iNumAxes] = N;

if (!IntervalIntersect(xAxis[iNumAxes], xPoly, xOffset, fDepth[iNumAxes]))
return false;
iNumAxes++;
}

if (!FindMTD(xAxis, fDepth, iNumAxes, MTD))
return false;

// make sure the polygons gets pushed away from each other.

if (MTD * xOffset < 0.0f)
MTD = -MTD;

return true;
}

// find the axis with minimum overlap.

// axis need to be normalised, so we can compare their overlap depth.

// take the axis with minimum overlap as the minimum translation vector.

// the objects wil get push along that vector until they stop overlapping

bool FindMTD(const Vector* xAxes, float* d, int iNumAxes, Vector& MTD)
{
MTD = Vector(0, 0);

float dmin = 1000000.0f;
int imin = -1;

for(int i = 0; i < iNumAxes; i ++)
{
float a = xAxes[i].Length();

if (a < 0.000001f)
continue;

float depth = d[i] / a;

if (depth < dmin)
{
dmin = depth;
imin = i;
MTD = (xAxes[i] / a) * depth;
}
}
return (imin != -1);
}

as I said, I''ll work on that as soon as I have time. In the meanwhile, this is the pseudo code. I''ll put a tutorial-demo later on.

for the extra info, like top/bottom, you can return the normal of collision as well as the time of collision, and the MTD in the overlap case is the normal of collision. so given which way the normal is pointing, you can detect a top-bottom-right-left collision.

##### Share on other sites

http://uk.geocities.com/olivier_rebellion/Polycolly.zip

or

http://uk.geocities.com/olivier_rebellion/
"2D swept+overlap polygonal collision and response"

I''ll put that in some sort of step-by-step tutorial-doc form when I can be arsed

##### Share on other sites
Hmmm thanks a lot oliii for helping me out, i will check it. Hey did u check your mail, i sent it to you yesterday..

Omar Alvi

##### Share on other sites
I''ll check my mails

I''ve cleaned the code, and merged the two methods (overlap and swept test), into one algorithm (using an extended version of the separating axis test). Much better, and more efficient.

I''ve decided to write a tutorial, since it''s working solid, and is efficient, stand alone, and quite simple to explain. It''s also easily extendable to support rotations. Kind of a generic way of doing solid collision detections in polygonal 2D games.

there is also the matter of the collision response, which is another matter all together, but not too hard to explain.

##### Share on other sites
Ohh i just checked it, its awesome man. Infact all of the demos
are pretty cool. Hmm i havent read the code yet. You seem to have a very good understanding of physics. Amm can u tell me how did u start on these tutorials. I mean where to learn the stuff necessary to make demos like the ones u have made. Yeah and one more thing, u didnt reply to my mail i have sent another one.
Hope to hear from you now.

Omar Alvi

##### Share on other sites
I''ve completed the demo, also with a doc, describing the algo.

the algo is an extended version of the separation axis algorithm, that detects both overlap and dynamic collisions, all in one felt swoop.

get it at
http://uk.geocities.com/olivier_rebellion/Polycolly.zip
or
http://uk.geocities.com/olivier_rebellion/
"2D swept+overlap polygonal collision and response"

1. 1
2. 2
Rutin
19
3. 3
khawk
15
4. 4
5. 5

• 13
• 26
• 10
• 11
• 44
• ### Forum Statistics

• Total Topics
633743
• Total Posts
3013644
×