Archived

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

Newbie

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Ok, im wanting to create a fairly simple collision detection system, if anyone has played crimsonland, that is hte perspective that the user is viewing from, its perfectly "top down" not isometric 1) are there any resources that cover this sort of thing? 2) how would you get the following effect? say someone heads at a wall at an angle, when they hit the wall, they dont stop completely, they slide along the wall at a slower speed, does anyone have some resources for THIS? cuz ive been working on it for a few hours (well just one during study hall :-D ) and i think im on the right track, but its just plain a lot of work, and ive had failed calculations before o / \ / \ / / / / / 3) and third, is it practical to create a two dee array with each cell corresponding to a area on the screen, and each cell contains a linked list of every "ENTITY" within that area, and that way i could save some ticks on collision detection by colliding each object with [ ][ ][ ][ ][ ] [ ][C][C][C][ ] [ ][C][O][C][ ] [ ][C][C][C][ ] [ ][ ][ ][ ][ ] o being the object and c being the cells that the object is colliding within, AND if this is not good practice, what WOULD be good? Whew, that was a lot, thanx all -Dan Yes I realize im a n00b...

Share this post


Link to post
Share on other sites
quote:
Original post by Ademan555
Ok, im wanting to create a fairly simple collision detection system, if anyone has played crimsonland, that is hte perspective that the user is viewing from, its perfectly "top down" not isometric
1) are there any resources that cover this sort of thing?
2) how would you get the following effect?

say someone heads at a wall at an angle, when they hit the wall, they dont stop completely, they slide along the wall at a slower speed, does anyone have some resources for THIS? cuz ive been working on it for a few hours (well just one during study hall :-D ) and i think im on the right track, but its just plain a lot of work, and ive had failed calculations before

o /
\ /
\ /
/
/
/
/

3) and third, is it practical to create a two dee array with each cell corresponding to a area on the screen, and each cell contains a linked list of every "ENTITY" within that area, and that way i could save some ticks on collision detection by colliding each object with

[ ][ ][ ][ ][ ]
[ ][C][C][C][ ]
[ ][C][O][C][ ]
[ ][C][C][C][ ]
[ ][ ][ ][ ][ ]

o being the object and c being the cells that the object is colliding within, AND if this is not good practice, what WOULD be good? Whew, that was a lot, thanx all

-Dan

Yes I realize im a n00b...


There is nothing simple with collision detection

for the sliding stuff, it's simple, if you know the displacement of the vehicle (velocity vector, or the difference between position previous frame and position next frame), it'simply

Ship.Velocity -= N * (Ship.Velocity.Dot(N) / N.Dot(N));

or

Ship.Displacement -= N * (Ship.Displacement.Dot(N) / N.Dot(N));

Now, that's all vector maths, which makes things simple. With angle, it's a little bit different. To make the ship slide, all you need is make the ship angle equal to the segment angle.

But I'd really advise to use vectors.


the normal of collision, given a segment you collide with is

E = (Segment.P2 - Segment.P1);
N = Vector2(-E.y, E.x);

or in angle terms

E = (Segment.P2 - Segment.P1);
segment_angle = atan2(E.y, E.x) * 180.0f / Pi; // in degrees

then you reduce the speed by x amount.

if you collide with a vertex, say the corner connecting two segments,

N = (Ship.Position - Vertex);

in angle terms, if you really want to stick to angles

E = Vector2(N.y, -N.x);
angle = atan2(E.y, E.x) * 180.0f / Pi;

you maybe also want to use the angle + 180.0f for your new ship angle, depending which of the two is the closest to the current ship angle.

beside being more 'solid', (with angles you can run in some nasty situations of you collide with two segments at once) the advantage with vectors, is that you can do some more proper physics. You can make the ship bounce back a little.

V = Ship.Velocity;

Vn = N * (V.Dot(N) / (N.Dot(N)); // the velocity along the normal
Vt = V - Vn; // the velocity along the plane of collision

Vn *= -(CoR); // coefficient of restitution, or 'bounce factor'
Vt *= (1.0f - CoF); // coefficient of friction

V = Vn + Vt; // the resulting velocity of the ship.

Ship.Velocity = V; // the resulting velocity of the ship

this a simple velocity reflexion model. Simple and really all you need for a 2D shoot'em up.



The problem with the grid-based scheme is that you have to be careful not to duplicate collision tests, because objects will be reference in several cells of the grid.

I used a similar system to store static objects, but I think it's not suited for dynamic entites, because of that problem. And there are better schemes to store statics anyway. Like a quad trees.


I used another technique to store dynamic objects, which involves sorting object's bounding boxes along both the X and Y axis.

You build list of pairs of objects whose span intersect on the X axis, and Y axis. The lists are sorted (by a hash value which is the concatenation of the objects indices).

Then you trasverse the two lists of pairs of objects, and pairs of objects that are present on both lists have to be tested for collision.



//--------------------------------------------

// the min and max extents of an object along an axis

// (X or Z).

//--------------------------------------------

struct CSpan
{
float min, max;
unsigned short iObj;

CSpan(float min0, float max0, int i)
{
min = min0;
max = max0;
iObj = i;
}

//--------------------------------------------

// tests if two spans overlap

//--------------------------------------------

bool Disjoint(const CSpan& Span) const
{
return (min > Span.max || max < Span.min);
}

//--------------------------------------------

// function that dictates the sorting of the spans

// in a list (see qsort() in the standard library)

//--------------------------------------------

static bool GreaterFunc(const CSpan* pSpan0, const CSpan* pSpan1)
{
return (pSpan0->min > pSpan1->min);
}
};

//--------------------------------------------

// pair of indices to objects.

//--------------------------------------------

struct CTestPair
{
unsigned int iTest;

//--------------------------------------------

// the object indices are sorted, because the pair

// will be added to a list.

//--------------------------------------------

CTestPair(unsigned short A, unsigned short B)
{
if (A > B) Swap(A, B);
iTest = B | (A << 16);
}

//--------------------------------------------

// function that dictates the ordering in a list

//--------------------------------------------

static bool GreaterFunc(const CTestPair* pTest0, const CTestPair* pTest1)
{
return (pTest0->iTest > pTest1->iTest);
}

unsigned short GetObjA() const { return iTest & ((1 << 16)-1); }
unsigned short GetObjB() const { return (iTest >> 16) & ((1 << 16)-1); }

};

//---------------------------------------------------

// list of spans, on X and Y axes, or bounding box extents

// along X and Y.

//---------------------------------------------------

CList<CTestPair> XSpanList(CSpan::GreaterFunc);
CList<CTestPair> YSpanList(CSpan::GreaterFunc);

//---------------------------------------------------

// list of pairs of overlapping spans, on X anf Y axes

//---------------------------------------------------

CList<CTestPair> XTestList(CTestPair::GreaterFunc);
CList<CTestPair> YTestList(CTestPair::GreaterFunc);

//---------------------------------------------------

// list of pairs of objects that have spans that overlaps

// on X *AND* Y (the AND is very important).

//---------------------------------------------------

CList<CTestPair> Tests(CTestPair::GreaterFunc);

void FindAllCollisions()
{
//---------------------------------------------------

// tidy up

//---------------------------------------------------

XSpanList.Clear();
YSpanList.Clear();
XTestList.Clear();
YTestList.Clear();
Tests.Clear();

//---------------------------------------------------

// insert spans of objects in the lists

//---------------------------------------------------

for(int i = 0; i < NumObjects; i ++)
{
CSpan Xspan(Obj[i].Rectangle.MinX, Obj[i].Rectangle.MaxX, i);
CSpan Yspan(Obj[i].Rectangle.MinY, Obj[i].Rectangle.MaxY, i);

XSpanList.Insert(Xspan);
YSpanList.Insert(Yspan);
}

//---------------------------------------------------

// find spans that overlap on the X axis.

// if two spans stop overlapping, because the spans are sorted,

// it means that spans further in the list won't overlap either,

// so we can stop the search for the current object.

//---------------------------------------------------

for(int i = 0; i < XSpanList.GetNumElements(); i ++)
{
//---------------------------------------------------

// look for objects that overlap that span

//---------------------------------------------------

for(int j = i+1; j < XSpanList.GetNumElements(); j ++)
{
//---------------------------------------------------

// spans stop overlapping, stop the search

//---------------------------------------------------

if (XspanList[i].Disjoint(XSpanList[j]))
break;

//---------------------------------------------------

// else, add the pair to the list

//---------------------------------------------------

CTestPair Test(XSpanList[i].iObj, XSpanList[j].iObj);
XTestList.Insert(Test);
}
}

//---------------------------------------------------

// find spans that overlap on the Y axis.

// if two spans stop overlapping, because the spans are sorted,

// it means that spans further in the list won't overlap either,

// so we can stop the search for the current object.

//---------------------------------------------------

for(int i = 0; i < YSpanList.GetNumElements(); i ++)
{
//---------------------------------------------------

// look for objects that overlap that span

//---------------------------------------------------

for(int j = i+1; j < YSpanList.GetNumElements(); j ++)
{
//---------------------------------------------------

// spans stop overlapping, stop the search

//---------------------------------------------------

if (YSpanList[i].Disjoint(YSpanList[j]))
break;

//---------------------------------------------------

// else, add the pair to the list

//---------------------------------------------------

CTestPair Test(YSpanList[i].iObj, YSpanList[j].iObj);
YTestList.Insert(Test);
}
}

//---------------------------------------------------

// now, merge the two into one list. Only keep pairs

// of objects that overlap on the X axis AND the Y axis.

// if a pair of object indices only appear on one list,

// do NOT add it to the global list of tests to perform.

//---------------------------------------------------

Tests.Combine(XTestList, YTestList);

//---------------------------------------------------

// now we have every posible collisions that can happen,

// test them

//---------------------------------------------------

for(int i = 0; i < Tests.GetNumElements(); i ++)
{
int iObjA = Tests[i].GetObjA();
int iObjB = Tests[i].GetObjB();

Obj[iObjA].TestCollision(Obj[iObjB]);
}
}



When an object moves, instead of removing it in the list of spans and reinsert it, you can just move it up and down the list depending which way it is moving.

[edited by - oliii on December 12, 2003 8:41:37 PM]

Share this post


Link to post
Share on other sites