Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » Collision Detection with Diagonal Lines...

This thread is locked; no one can reply to it. rss feed Print
Collision Detection with Diagonal Lines...
Tron Boy
Member #2,294
May 2002
avatar

Here is a quote from a really old post about the merits of using vectors over angles...

Quote:

For anything even approaching an interesting level of complexity (ie. with more than one single force acting on objects, or with collision against diagonal lines, or in 3D), a vector approach will be most efficient

Did I read that right? Collision detection with diagonal lines instead of just horizontal and vertical lines? Would this only be lines at a 45 degree angle? (I can't quite recall the definition of diagonal). Does anyone know of any sample code? If this means what I think it does, I'll drop C for C++ tonight, so that I can take full andvantage of all this verctor business...

23yrold3yrold
Member #1,134
March 2001
avatar

Sure. You can do collision detection with rotated sprites, or pretty much any polygon (as long as the shape ain't terribly funky). There's a math formula for determining if two lines cross, and you can check if a point from one polygon falls inside the other. A math whiz will be by shortly to spell it out (I sure can't) ....

--
Software Development == Church Development
Step 1. Build it.
Step 2. Pray.

A NMC
Member #2,192
April 2002
avatar

i just want to know how to detect collision between two rotating 3d boxs.

if u can do that, a line can be treated as a thin long 3d box. a plane is just a flat 3d box^^

but i don't know how to do this...

gillius
Member #119
April 2000

I guess I could step in being a "math wiz"... err sorta. I could figure it out. Actually most math problems like that are easy to solve if you have the motivation and the time to just get your hands dirty on it.

I'm pretty sure I'm right here, but if you want to do collsion detection, of any sort, there is no "equation" or more precisely the relation you are looking for is =. Looking for > and < will collision detect as partitions.

As you all probably know, the equation for a line is y = mx + b where m is the slope and b is the offset on the y axis.

If you want to know where two lines meet, set them equal and solve the equation. If there is no solution, then the lines are parallel and not overlapping. If the solution is a simple identity ( 0=0 ) then the line collides at all points, and therefore it is the same line. If the lines are not parallel then there exists one solution to the problem.

Find this solution, and then check the solution to see if the point falls between the boundaries on both of your line segments. If and only if both line segments contain the point there is a collision with two arbirary line segments.

This same concepts applies to any linear function in any number of dimensions. Maybe I can come up with an example. How about a line segment from (1,1) to (2,2), and one from (3,0) to (0,3). The equations are:

y = 1*x + 0
y = -1*x + 3

Now to solve (by subsitution of y with x):

1*x + 0 = -1*x + 3
      x = -x + 3
     2x = 3
      x = 3/2 = 1.5

Now to solve for y, now that we know x:

y = 3/2
y = -3/2 + 3 = 3/2

If you notice you get the same y value for each. This should always be the case, or something went wrong. Now you know the point of intersection is (1.5, 1.5), which is the correct answer if you draw the segments and look at them.

Now all you have to do is test to see if (1.5, 1.5) is in your line segments which you can do with simple if tests ( is 1.5 < xmax and is 1.5 > xmin ) for both lines and also for y.

Wow that was fun. I wasn't expecting to go that far with it. And I do think I solved the problem adequately enough to prove my point.

I didn't cover how to make the equations for the lines, which is pretty easy. Also note you can easily find the angle (and a quick test for parallelism) by applying the dot product to the equivalent vectors, for which the angle may be useful in the physics of the collision (you should know the speeds from your engine already).

This is for line segment collision though. Note that checking for collisions of lines will NOT check for collision in bounding boxes, if one box is entirely inside the other (which is always possible unless all boxes are of the identical width and height).

Gillius
Gillius's Programming -- https://gillius.org/

A NMC
Member #2,192
April 2002
avatar

How about collision between two 3D boxs??

i know how the simple step:

1. any point of either boxs in another box.

How about their face intersect without point inside other box??

face intersect is so complex... and slow process.

LEDominant
Member #2,218
April 2002
avatar

Tron Boy: You don't need C++ (Makes it easier though). You need maths/physics vectors which means a measurement that defines both direction and magnitude.

eg.

typedef struct {
    float    x;
    float    y;
} vector_t;

or

typedef struct {
    float    angle;
    float    length;
} vector_t;

A C++ vector is just a self adapting array (I think).

What do you want to collide against the diagonal line? Circles and Spheres are easier, just check the distance to the line. If the circle is 4 units away and has a radius of 5 then it is intersecting.

Here is an unoptimised example from a Line class I made ages ago.

1float CLine::DistToPoint(float x, float y)
2{
3 float dx=x-x1;
4 float dy=y-y1;
5 float l=Length();
6 float lx=(x2-x1)/l;
7 float ly=(y2-y1)/l;
8 
9 float d=lx*dx+ly*dy;
10 if(d<0)
11 {
12 return sqrt(dx*dx+dy*dy);
13 }
14 if(d>l)
15 {
16 dx=x-x2;
17 dy=y-y2;
18 return sqrt(dx*dx+dy*dy);
19 }
20 dx-=lx*d;
21 dy-=ly*d;
22 return sqrt(dx*dx+dy*dy);
23}

--------------------------------------------------------
Life is a trip, watch your face when you hit the ground.

Tron Boy
Member #2,294
May 2002
avatar

Quote:

What do you want to collide against the diagonal line?

Amongst other things, I want to possibly have the player character in my game able to land on sloped surfaces, and be able to move along those surfaces. Think of how Mario could slide down slopes back in Super Mario Bros. 3 and you'll get the idea.

As far as C vs. C++, back in that old thread I mentioned, the posters really stressed how much C++ makes working with vectors easier than trying to do it in C. I really think I need to move on to C++ anyway. I just wish I could find a way to learn it that wasn't so boring...

But anyway, other than the sloped surfaces, I want some collion detection between boxes that are rotated at angles other than just horizontally and vertically.

spellcaster
Member #1,493
September 2001
avatar

If you want that suoer mario 3 effect, that's really easy.
What you do is soemthing like this:
You check if the player is on a slope (if the tile is a sloped tile). Then you adjust the y position of the sprite based on the offset inside the tile. Since you'll have 45 degree angles, that's pretty easy (the offset into the tile is also the offset in y direction),

Now adjust the speed of the sprite based on the slope (or simply adjust the position; this will be more easy but also less clean - but it'll work, so it's worth a try).

If you want to support slopes in a more general way, you can define offset arrays for your tiles which store the y-offset based on the x-offset into the tile. That way you can do curved tiles (like the hills in Ghost and Goblins).

--
There are no stupid questions, but there are a lot of inquisitive idiots.

gillius
Member #119
April 2000

Ahh yes that's a good idea Spellcaster.

Also if you do curved tiles, you can define it for every x, or you can create a formula. Either way you can use the derivative of the curve to find out the slope (and therefore how fast the object accelerates due to gravity). For functions it is trivial to do, and for free-defined curves you can just sample the points near the intersection to find an approximation to the derivative.

Gillius
Gillius's Programming -- https://gillius.org/

23yrold3yrold
Member #1,134
March 2001
avatar

I wish some one would spell out the math and such. I went with bitmasks for a reason; this stuff went over my head ...

--
Software Development == Church Development
Step 1. Build it.
Step 2. Pray.

Tron Boy
Member #2,294
May 2002
avatar

You should do what I (am trying to) do 23. Save all the good threads to your hard drive, then try to tackle one a day. It's kind of slow (and will probably take more than a day to figure out), but it's a good crash course to getting this stuff drilled into your head (at least the one that I did tackle in this manor).

Just pick the key words out of all that genius-speak, enter 'em into a google search, pick a site with a good lookin' url, and start reading 'til your eye's turn read and your brain hurts. You just might figure some of this stuff out... at least enough to put it in your game. I got vectors implemented into my game by that method...

Although the vectors does seem easy compared to what all they just said... But you gotta try if you want it in your game...

23yrold3yrold
Member #1,134
March 2001
avatar

I have tried it. And I keep all the articles I like on my hard drive and shortcuts to all the good threads.

Bitmasks are still easier :)

--
Software Development == Church Development
Step 1. Build it.
Step 2. Pray.

Go to: