Jump to content
  • Advertisement
Sign in to follow this  
Jinroh

Collision Detection Against Lines

This topic is 3720 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

Hello all, I've got a bit of a conundrum here. I have a scene with lines:
****************
*               *
 *       px/py   *
  *               *
   *               *
    *****************

Just a Room like this, for example with the player in there at point (px, py). I have a list of walls I loop through and I want to be able to hit the player against them. I move the player by doing a nice
rotX = -distToMove * (sin(pAngle));
rotY = distToMove * (cos(pAngle));

pX = pX + rotX;
pY = pY + rotY;

Something like that. So I'm trying to figure out how to collide the player against these wall lines. I tried by casting a ray from the player and getting the distance, but that didn't work out quite right so if anybody has a suggestion that would be great. Thanks in advance.

Share this post


Link to post
Share on other sites
Advertisement
You could do this by defining your lines as planes (with z always equal to 0, since, it's 2D). To define a plane you just need a point and a normal: the point is easy (you have those already), to get a normal you can just take a cross product of a line vector with <0,0,1>. You get this line vector by going around your parallelogram (or whatever polygon you have) in clockwise order. Once you have your plane, it's very simple to tell whether a point is on the right side of it. A tutorial like this one explains the math.

As an example, let's pretend your walls have the following corners (starting in the lower left and going clockwise): <1,0>, <0,5>, <4,5>, <5,0>. Now let's say you have the point <3,3>...which should be within all the walls. To test whether it's inside the rightmost wall we start by finding a vector going from the upper-right corner to the lower-right:


v1 = <5,0,0> - <4,5,0> = <1,-5,0>


Now to find the normal vector of the line we do a cross-product of v1 with <0,0,1>:


n = |<1,-5,0> (cross) <0,0,1>| = |<-5,-1,0>| = <-0.98,-0.196>


To make a plane, we use the equation Ax + By + Cz + D = 0 where...
A = n.x
B = n.y
C = n.z
D = -n (dot) p0 (p0 is the first point in the line, so the upper right corner <4,5,0>)


A = -0.98
B = -0.196
C = 0
D = -<-0.98,-0.196,0> (dot) <4,5,0> = 3.92 + 0.98 = 4.9


Okay now that we have the equation for any plane, we can do the test for distance from a point (r) to a plane. The equation for that is


distance = (n (dot) r + D)


The nice thing about this is that the sign of the distance tells us which side of the plane the point is on: positive means it's on the "right" side, negative means it's on the other side, 0 means it's on the plane.


distance = <-0.98,-0.196,0> (dot) <3,3,0> + 5 = -2.94 + -0.588 + 5 = 1.472


In this case we've determined that <3,3> is indeed on the correct side of wall. Repeating this for the other 3 walls should yield the same results.


Share this post


Link to post
Share on other sites
All right, I understand.

So if I calculate my distance from me to the plane if I'm on the posative side and I fall within a certain distance I should block the user from moving.

So say...

if(distToPlane < 4 && distToPlane > 0)
blockPlayer
else
pX = pX + rotX;
pY = pY + rotY;

Something like that in a nutshell.

Thanks MJP I appreciate the lesson.

EDIT:
Just as an aside here I want to make sure I'm right in my thinking.


****************
* *
* *
* *
p->* *
*****************

//If I'm looking in the direction of the arrow the wall the arrow is pointing at will be positive correct?

****************
* *
* *
* *
* <---p *
*****************

//Additionally If I'm on the inside and looking here it will be postive as well.







****************
* *
* *
* *
* <-------------*------ P
*****************

//However if looking from the outside this wall would be negative correct? Like a Backface.






Just wanted to get that straight, thanks. If so my brain is cooking on all sorts of things.

[Edited by - Jinroh on June 4, 2008 3:23:53 PM]

Share this post


Link to post
Share on other sites
If all your side walls are at the same angle, you might not need to go to the trouble of writing a real plane/line based system and dealing with all the numerical accuracy pains that come with it. Instead, skew the player's position and velocity to where the walls can be treated as vertical, and then skew back after colliding. Might make creating the collision maps easier too.

Share this post


Link to post
Share on other sites
another example, just using a circle / segment collision check.



#include <windows.h>
#include <winuser.h>
#include <gl\glut.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

int sgn(double a) { return (a>0); }
double clamp(double x, double min, double max) { return (x < min)? min : (x > max)? max : x; }
double frand(double x) { return (rand() / (double) RAND_MAX) * x; }
double Pi() { static const double _Pi = atan(1.0) * 4.0; return _Pi; }

struct Vector
{
double x, y;

Vector()
{}

Vector(double _x, double _y)
: x(_x)
, y(_y)
{}

Vector& operator +=(const Vector& V) { x += V.x; y += V.y; return *this; }
Vector& operator -=(const Vector& V) { x -= V.x; y -= V.y; return *this; }
Vector& operator *=(double k) { x *= k ; y *= k ; return *this; }
Vector& operator /=(double k) { x /= k ; y /= k ; return *this; }

Vector operator + (const Vector& V) const { return Vector(x + V.x, y + V.y); }
Vector operator - (const Vector& V) const { return Vector(x - V.x, y - V.y); }
Vector operator * (double k) const { return Vector(x * k, y * k); }
Vector operator / (double k) const { return Vector(x / k, y / k); }

double operator * (const Vector& V) const { return x * V.x + y * V.y; }
double operator ^ (const Vector& V) const { return x * V.y - y * V.x; }

double Length() const { return sqrt(x*x + y*y); }
double Normalise() { double l = Length(); x /= l; y /= l; return l; }

Vector Scale (const Vector& xScale) const { return Vector(x * xScale.x, y * xScale.y); }
Vector InvScale(const Vector& xScale) const { return Vector(x / xScale.x, y / xScale.y); }

Vector Rotate(const Vector& C, double a) const
{
double px = (x - C.x) * cos(a) - (y - C.y) * sin(a) + C.x;
double py = (x - C.x) * sin(a) + (y - C.y) * cos(a) + C.y;

return Vector(px, py);
}

Vector& Randomise(const Vector& Min, const Vector& Max)
{
x = Min.x + frand(Max.x - Min.x);
y = Min.y + frand(Max.y - Min.y);
return *this;
}
};

struct CColour
{
double r;
double g;
double b;
double a;

CColour(double R, double G, double B, double A)
{
r = R;
g = G;
b = B;
a = A;
}
void Render() const
{
glColor4f(r, g, b, a);
}
};


void RenderPoint(const Vector& P, CColour col, double radius)
{
col.Render();
glBegin(GL_POINTS);
glPointSize(radius);
glVertex2f(P.x, P.y);
glEnd();
}

void RenderSegment(const Vector& P, const Vector& Q, CColour col, double radius)
{
col.Render();
glBegin(GL_LINES);
glLineWidth(radius);
glVertex2f(P.x, P.y);
glVertex2f(Q.x, Q.y);
glEnd();
}

void RenderArrow(const Vector& P, const Vector& D, CColour col, double radius)
{
col.Render();
glLineWidth(radius);

float angle = atan2(D.y, D.x);
glPushMatrix();
glTranslatef(P.x, P.y, 0.0f);
glScalef(D.Length(), D.Length(), 1.0f);
glRotatef(angle * 180.0f / Pi(), 0, 0, 1);

glBegin(GL_LINES);
glVertex2f(0, 0);
glVertex2f(1, 0);
glVertex2f(1, 0);
glVertex2f(0.9, -0.05);
glVertex2f(1, 0);
glVertex2f(0.9, +0.05);
glEnd();
glPopMatrix();

}


void RenderCircle(const Vector& P, float r, CColour col, double radius)
{
col.Render();
glLineWidth(radius);

glBegin(GL_LINE_LOOP);

int steps = 16;
double angle = 0.0;
for(int i = 0; i < steps; i ++, angle += (2.0 * Pi()) / (double) steps)
{
Vector D(cos(angle) * r, sin(angle) * r);
glVertex2f(P.x + D.x, P.y + D.y);
}
glVertex2f(P.x + r, P.y);

glEnd();
}

bool CircleSegmentCollide(Vector& P, float r, const Vector& A, const Vector& B, Vector& collVector)
{
Vector AP = P - A; // distance vector
Vector AB = B - A; // segment vector

// compute closest point on line (A, B) to P
double u = (AP * AB) / (AB * AB);

// clamp to segment [A, B] range
u = (u < 0.0f)? 0.0f : (u > 1.0f)? 1.0f : u;

// closest point on segment [A, B] to P
Vector C = A + AB * u;

// cehck if point inside circle
Vector CP = P - C;
double l2 = CP * CP;

// nope, no collision
if (l2 > r * r)
return false;

// compute penetration vector
double l = sqrt(l2);
collVector = CP * (r - l) / l;

return true;
}

int screen_width = 640;
int screen_height = 480;

// the player
Vector P;
float r;
Vector MousePos(-1, -1);

// the segments
enum { MAX_SEGMENTS = 1000 };
int segmentCount = 0;
Vector segments[MAX_SEGMENTS][2];

//-------------------------------------------------------------------------------------------------
//
// OPENGL Functions
//
//-------------------------------------------------------------------------------------------------
void init()
{
// randomise player pos.
r = frand(10) + 10;
P.Randomise(Vector(0, 0), Vector(screen_width, screen_height));

// add screen boundaries
segmentCount = 0;
segments[0][0] = Vector(0, 0);
segments[0][1] = Vector(screen_width, 0);
segments[1][0] = Vector(screen_width, 0);
segments[1][1] = Vector(screen_width, screen_height);
segments[2][0] = Vector(screen_width, screen_height);
segments[2][1] = Vector(0, screen_height);
segments[3][0] = Vector(0, screen_height);
segments[3][1] = Vector(0, 0);
segmentCount = 4;

// add random segments
segmentCount += rand() % 20;
for(int i = 0; i < segmentCount; i ++)
{
Vector C;
Vector D;
C.Randomise(Vector(0, 0), Vector(screen_width, screen_height));
D.Randomise(Vector(-100, -100), Vector(100, 100));
segments[0] = C;
segments[1] = C + D;
}
}

void display(void)
{
glClear(GL_COLOR_BUFFER_BIT|GL_DEPTH_BUFFER_BIT);

glViewport( 0, 0, screen_width, screen_height);

glMatrixMode(GL_PROJECTION);
glLoadIdentity();
gluOrtho2D(0, screen_width, screen_height, 0);

glMatrixMode(GL_MODELVIEW);
glLoadIdentity();

Vector Displacement = MousePos - P;
double d = Displacement.Length();
if(d > 3.0)
Displacement *= 3.0f / d;

P += Displacement;

for(int i = 0; i < segmentCount; i ++)
{
Vector Coll;
if(CircleSegmentCollide(P, r, segments[0], segments[1], Coll))
{
P += Coll;
}
}

for(int i = 0; i < segmentCount; i ++)
{
RenderPoint(segments[0], CColour(1, 0, 0, 1), 5);
RenderPoint(segments[1], CColour(1, 0, 0, 1), 5);
RenderSegment(segments[0], segments[1], CColour(1, 1.0, 0.5, 1), 3);
}

RenderPoint(P, CColour(1, 0, 0, 1), 5);
RenderPoint(MousePos, CColour(1, 0, 0, 1), 5);
RenderCircle(P, r, CColour(1, 1.0, 1.0, 1), 2);
RenderArrow(P, MousePos-P, CColour(1, 0.2, 0.2, 1), 1);

glutSwapBuffers();
}

void reshape(int w,int h)
{
screen_width = w;
screen_height = h;
}

void ticker(int i)
{
display();
glutTimerFunc(4, ticker, 0);
}

void keyboard(unsigned char key, int x, int y)
{
if(key == 27)
{
exit(0);
}
if(key == ' ')
{
init();
}
}

void mouse(int x, int y)
{
MousePos.x = x;
MousePos.y = y;
}

int main(int argc,char **argv)
{
glutInit(&argc,argv);
glutInitDisplayMode(GLUT_DOUBLE|GLUT_RGBA|GLUT_DEPTH);
glutInitWindowSize(screen_width, screen_height);
glutInitWindowPosition(100,100);
glutCreateWindow("verlet");
glutDisplayFunc(display);
glutReshapeFunc(reshape);
glutPassiveMotionFunc(mouse);
glutKeyboardFunc(keyboard);
glutTimerFunc(33, ticker, 0);

glClearColor(0.0f,0.0f,0.3f,0.1f);
glPointSize(8);
glEnable(GL_POINT_SMOOTH);

glEnable(GL_LINE_SMOOTH);

glBlendFunc(GL_SRC_ALPHA,GL_ONE_MINUS_SRC_ALPHA);
glEnable(GL_BLEND);

init();
glutMainLoop();

return 0;
}


Share this post


Link to post
Share on other sites
Quote:
another example, just using a circle / segment collision check.


I was actually thinking this after spending some time thinking about it. Because the number of lines I have to check is dependant on how many are in th current sector I am in so it should just be quicker since I'll really only be checking rather small amount ~50-100 each frame.

Share this post


Link to post
Share on other sites
If the number of tests becomes a problem, then usually, the level is compartimented using a BVH or some scenegraph. Like you say, if you have a quick way of finding out which sectors should be tested for collision, then the number of tests should be kept low.

One problem with the algo I have there, is that you can have the player sinking through walls, through a 'wedge' if it is very accute. There are ways around that, either by performing a more accurate swept test, or preventing the player moving towards walls he already collided during that frame.

but this is a 10 lines-of-code algo, so you cant expect it to be perfect. This also works the same way in 3D, which is quite cool.

Share this post


Link to post
Share on other sites
Yeah, the number of collisions should not be a problem.

However, I was pretty sure that bounding circle/sphere collision would be best for object to object so maybe I'll use it for that and another method for colliding with walls. Perhaps a hybrid algorithm or distance to plane equation.

Thanks again,
Jinroh.

Share this post


Link to post
Share on other sites
that's the algo above does. It computes the sphere-segment distance.

The intresting thing is that you can also apply the same method for sphere-sphere collision. It's all distance based, so easy. Sphere-sphere is easy enough for object collision.

Share this post


Link to post
Share on other sites
Yes that's true a sphere wouldn't be much different. Just in 3 Dimensions instead of 2.

Yeah, I think I'll use the sphere/sphere collision for my objects then and use the Distance to Plane for my Player/Object wall collision. I think that would be best. I'll try both though for the wall collision and see what I like best. :D

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!