Be a Supporter!

As: Line-line Collision

  • 6,952 Views
  • 39 Replies
New Topic Respond to this Topic
Glaiel-Gamer
Glaiel-Gamer
  • Member since: Dec. 28, 2004
  • Offline.
Forum Stats
Member
Level 28
Game Developer
As: Line-line Collision Oct. 7th, 2005 @ 04:38 PM Reply

AS: Line to Line Collision
by Glaiel Gamer
AS: MAIN

----------------INTRODUCTION--------------
Collision detection, we all need to use it in a game, right? Our first impression would be to instantly use versions of hitTest, shapeflag, and the Pythagorean Theorem. Well, I was fooling around today, and I was REALLY bored in Algebra 2 cause It was all review so I was thinking. I doodled equations. And after school, I came up with this neat line to line collision detection function, which could essentially be used for polygons also.

STUFF TO KNOW:
y = mx+b
y-y1 = m(x-x1)

How to use substitution to solve systems of equations.

------------THE CODE, BROKEN DOWN AND COMMENTED---------

createEmptyMovieClip("d", 1);
createEmptyMovieClip("s1", 2);
s1.lineStyle(2, 0xFF0000, 95);
s1.moveTo(-5, -5);
s1.beginFill(0xFF0000, 20);
s1.lineTo(-5, 5);
s1.lineTo(5, 5);
s1.lineTo(5, -5);
s1.lineTo(-5, -5);
s1.endFill();
col = "0xFF0000";
duplicateMovieClip(s1, "s2", 3);
duplicateMovieClip(s1, "s3", 4);
duplicateMovieClip(s1, "s4", 5);
duplicateMovieClip(s1, "s5", 6);
s1._x = 100;
s1._y = 100;
s2._x = 200;
s2._y = 100;
s3._x = 300;
s3._y = 300;
s4._x = 400;
s4._y = 300;

// This first block of code is a little bit of API, just to draw the squares and create the MC where we print the line in

s1.onPress = s2.onPress=s3.onPress=s4.onPress=function () {
startDrag(this);
};
s1.onMouseUp = s2.onMouseUp=s3.onMouseUp=s4.onMouseUp=fun
ction () {
stopDrag();
};

//Just a simple dragging code

_root.onEnterFrame = function() {
d.clear();
d.lineStyle(3, col, 100);
d.moveTo(s1._x, s1._y);
d.lineTo(s2._x, s2._y);
d.moveTo(s3._x, s3._y);
d.lineTo(s4._x, s4._y);

// Draws the line between the points

line1 = new Object();

//here's where the good stuff starts. My function was written to input 2 line objects (my custom line objects) so we make an object for line 1

line1.x1 = s1._x;
line1.y1 = s1._y;
line1.x2 = s2._x;
line1.y2 = s2._y;

// these are the 2 endpoints points of the line, pretty self explanitory

line1.m = (line1.y1-line1.y2)/(line1.x1-line1.x2);

// m=slope. Slope will come in handy. Just a flash translation of the slope forumla

if (line1.x1-line1.x2 == 0) {
line1.m = 99999999;
}

// We don't want a vertical slope, so if the denominator is 0 we make slope a really high number

line1.b = (-1)*(line1.m*line1.x1-line1.y1);

// The y-intercept. I used y-y1 = m(x-x1) and translated it down to solve for b. I got it into y=mx+b format, and b turned out to be mx1-y1. Then I multiplied by -1 because flash has an inverted y axis.

line2 = new Object();
line2.x1 = s3._x;
line2.y1 = s3._y;
line2.x2 = s4._x;
line2.y2 = s4._y;
line2.m = (line2.y1-line2.y2)/(line2.x1-line2.x2);
if (line2.x1-line2.x2 == 0) {
line2.m = 99999999;
}
line2.b = (-1)*(line2.m*line2.x1-line2.y1);

// We do the same for our other line

poi = new Object();

// Poi stands for point of intersection.

poi = systemEQ(line1, line2);

// systemEQ is the function I wrote that solves systems of equations, or in other words, finds the point where the 2 lines intersect. poi now has 2 values, xi (x intersect) and yi (y intersect)

if (linetoline(line1, line2, poi)) {
col = "0xFF0000";
} else {
col = "0x000000";
}

//linetoline will be explained in detail later, but it is in essence a version of a line hittest that needs 2 lines and the point of intersection.

s5._x = poi.xi;
s5._y = poi.yi;

// Places a square on poi

};
function systemEQ(line1, line2) {
var rf = new Object();
rf.xi = (line1.b-line2.b)/(line2.m-line1.m);
rf.yi = line1.m*rf.xi+line1.b;
return (rf);

// I'm gonna explain this in one large chunk. y=mx+b for line 1 and y=mx+b for line 2. Using the substitution method, m1x+b1 = m2x+b2. Now I isolated x (x=(b1-b2)/(m2-m1)), and since all the other values are given in the line object, x is now a number. I plug it into y=mx+b to find the y intersect coordinate. Now the function returns the point of intersection. This was the hardest part, writing a function to parse algebraic problems.

}
function linetoline(line1, line2, poi) {
if(line1.x1 == line1.x2){
line1.x1 += .00001
}
if(line1.y1 == line1.y2){
line1.y1 += .00001
}

//I found out that vertical lines don't parse well here.

if ((((poi.xi>line1.x1 && poi.xi<line1.x2) || (poi.xi<line1.x1 && poi.xi>line1.x2)) && ((poi.xi>line2.x1 && poi.xi<line2.x2) || (poi.xi<line2.x1 && poi.xi>line2.x2))) || (((poi.yi>line1.y1 && poi.yi<line1.y2) || (poi.yi<line1.y1 && poi.yi>line1.y2)) && ((poi.yi>line2.y1 && poi.yi<line2.y2) || (poi.yi<line2.y1 && poi.yi>line2.y2)))) {

return (true);
} else {
return (false);
}

//Here's the bulk of this function. NG will probably break the if statement into like 10 lines, it's a long line of code. Basically, it tests if the point of intersection is between the endpoints of the line. It really is a simple line of code, the reason why it is so long is because it is so repetitive.

}

-----------CONCLUSION------------

USEFULNESS?
Of course it's useful. It could be used to provide a quick method of gunfire in a game like hollow point if you can do line-line rather than a thick line and shapeflag. There's many other uses too, but that's for you to figure out.

LINKS:
Example: http://media.putfile.com/line-line

AS Collision Threads:
http://www.newground../topic.php?id=293660

http://www.newground../topic.php?id=296755

And A really helpful thread:
http://www.newground../topic.php?id=354500

~ Glaiel Gamer

liam
liam
  • Member since: Dec. 11, 2004
  • Offline.
Forum Stats
Member
Level 22
Blank Slate
Response to As: Line-line Collision Oct. 7th, 2005 @ 04:57 PM Reply

Really, really unnecessary stuff you have there.


Sup, bitches :)

BBS Signature
authorblues
authorblues
  • Member since: Jun. 21, 2005
  • Offline.
Forum Stats
Member
Level 12
Blank Slate
Response to As: Line-line Collision Oct. 7th, 2005 @ 04:57 PM Reply

great work... i can use this for my API game. sure beats the hell out of executing 49 hittests per frame...


BBS Signature
Vortex
Vortex
  • Member since: Aug. 27, 2005
  • Offline.
Forum Stats
Member
Level 09
Blank Slate
Response to As: Line-line Collision Oct. 7th, 2005 @ 05:06 PM Reply

glaiel you are one smart mother effer

Glaiel-Gamer
Glaiel-Gamer
  • Member since: Dec. 28, 2004
  • Offline.
Forum Stats
Member
Level 28
Game Developer
Response to As: Line-line Collision Oct. 7th, 2005 @ 05:08 PM Reply

At 10/7/05 04:57 PM, -liam- wrote: Really, really unnecessary stuff you have there.

why?

fwe
fwe
  • Member since: Jul. 24, 2003
  • Offline.
Forum Stats
Member
Level 08
Blank Slate
Response to As: Line-line Collision Oct. 7th, 2005 @ 05:47 PM Reply

I don't think it's unnessesary, liam. It is sort of what N uses for their collision detection. It can be very useful for ragdolls and matrices or point based games. Not to sound faggish, good job


wtfbbqhax

Teee-Haych
Teee-Haych
  • Member since: Sep. 18, 2005
  • Offline.
Forum Stats
Member
Level 02
Blank Slate
Response to As: Line-line Collision Oct. 7th, 2005 @ 05:55 PM Reply

I like the sound of american schools. We've only just learnt equations of straight lines, and standard y = mx + c notation recently. Though we learnt calculus integration/differentiation last year. Stupid order.

Nice tut, I've had similar thoughts myself in class but could never think of any possible application, still can't lol.

dammit I really need to stop posting on this alt.
GeoKureli
GeoKureli
  • Member since: Apr. 1, 2003
  • Offline.
Forum Stats
Supporter
Level 19
Game Developer
Response to As: Line-line Collision Oct. 7th, 2005 @ 06:04 PM Reply

i totally fell asleep on the day my teacher taught the substitution method, i know elimination and cramers law (and no, not jerry's food = cramer's food). i wish i payed attention because ive been wanting to find out how to find where 2 slopes meet without using loops, infact today i was wondering this too and i was gonna try using 1 of the other 2 methods

Rantzien
Rantzien
  • Member since: Jan. 27, 2005
  • Offline.
Forum Stats
Member
Level 15
Blank Slate
Response to As: Line-line Collision Oct. 7th, 2005 @ 06:07 PM Reply

At 10/7/05 05:55 PM, Teee-Haych wrote:
dammit I really need to stop posting on this alt.

Yeah, you have, like, 19 posts on it =D


BBS Signature
GeoKureli
GeoKureli
  • Member since: Apr. 1, 2003
  • Offline.
Forum Stats
Supporter
Level 19
Game Developer
Response to As: Line-line Collision Oct. 7th, 2005 @ 06:08 PM Reply

At 10/7/05 06:07 PM, Rantzien wrote:
At 10/7/05 05:55 PM, Teee-Haych wrote:
dammit I really need to stop posting on this alt.
Yeah, you have, like, 19 posts on it =D

anywhere over 20 makes you legally gay so watch out

Glaiel-Gamer
Glaiel-Gamer
  • Member since: Dec. 28, 2004
  • Offline.
Forum Stats
Member
Level 28
Game Developer
Response to As: Line-line Collision Oct. 7th, 2005 @ 07:02 PM Reply

At 10/7/05 06:04 PM, ImpotentBoy2 wrote: i totally fell asleep on the day my teacher taught the substitution method, i know elimination and cramers law (and no, not jerry's food = cramer's food). i wish i payed attention because ive been wanting to find out how to find where 2 slopes meet without using loops, infact today i was wondering this too and i was gonna try using 1 of the other 2 methods

well, I havent used substitution since algebra 1, but I couldn't think of a rational way to parse it through flash with elimination

dieEVILsanta
dieEVILsanta
  • Member since: May. 26, 2005
  • Offline.
Forum Stats
Member
Level 09
Blank Slate
Response to As: Line-line Collision Oct. 7th, 2005 @ 10:55 PM Reply

i just figured this out recently as well, yaaaaaay. tho i think your's is better.

FrostedMuffins
FrostedMuffins
  • Member since: Nov. 3, 2004
  • Offline.
Forum Stats
Supporter
Level 29
Programmer
Response to As: Line-line Collision Oct. 7th, 2005 @ 11:00 PM Reply

At 10/7/05 04:57 PM, -liam- wrote: Really, really unnecessary stuff you have there.

Liam, do you have a gruge against Glaiel or something? It seems like everything he posts, you have something bad to say about it.

dieEVILsanta
dieEVILsanta
  • Member since: May. 26, 2005
  • Offline.
Forum Stats
Member
Level 09
Blank Slate
Response to As: Line-line Collision Oct. 7th, 2005 @ 11:12 PM Reply

that is awesome, now that i actually have read it. i've always wondered why the y axis is inverted. does anyone know?

BleeBlap
BleeBlap
  • Member since: Mar. 8, 2005
  • Offline.
Forum Stats
Member
Level 24
Blank Slate
Response to As: Line-line Collision Oct. 7th, 2005 @ 11:20 PM Reply

The inverted y-axis is actually fairly standard in the programming world. JOptionPane (aka Java) uses an inverted y axis as well. I'm not positive but I would imagine it stems from the fact that it takes less memory to store an interger which can't be negative than storing other data types which take more memory (well this assumption is based in Java's data types (byte short int long float double) but I'm pretty sure it works the same way in other programming languages too.) So back in the day when every bit of memory was important (not that optimzation isn't still important) it was more efficient and it actually still is more efficient than using negative numbers. Again, I don't know this all for fact but it is all based in fact and I'm relatively confident that I'm at least partially correct.

liam
liam
  • Member since: Dec. 11, 2004
  • Offline.
Forum Stats
Member
Level 22
Blank Slate
Response to As: Line-line Collision Oct. 8th, 2005 @ 04:10 AM Reply

At 10/7/05 05:08 PM, Glaiel_Gamer wrote: why?

Because, it's so long and complicated just when a few simple hitTests would suffice..

At 10/7/05 11:00 PM, frostedmuffins wrote: Liam, do you have a gruge against Glaiel or something? It seems like everything he posts, you have something bad to say about it.

No, I actually think this is quite cool. Just because I don't like your gears thing doesn't mean I have a grudge against Glaiel, the gears thing is just so.. meh.. yet you guys try and make it sound like it's totally unbelievable excellent hardcore AS genius.


Sup, bitches :)

BBS Signature
Glaiel-Gamer
Glaiel-Gamer
  • Member since: Dec. 28, 2004
  • Offline.
Forum Stats
Member
Level 28
Game Developer
Response to As: Line-line Collision Oct. 8th, 2005 @ 07:36 AM Reply

At 10/8/05 04:10 AM, -liam- wrote:
At 10/7/05 05:08 PM, Glaiel_Gamer wrote: why?
Because, it's so long and complicated just when a few simple hitTests would suffice..

It's actually not that long and complicated. I just added a bit of fluff into it to make it readable. Plus, i think this is faster than hittests.

Glaiel-Gamer
Glaiel-Gamer
  • Member since: Dec. 28, 2004
  • Offline.
Forum Stats
Member
Level 28
Game Developer
Response to As: Line-line Collision Oct. 8th, 2005 @ 08:54 AM Reply

function lineHitTest(p1x, p1y, p2x, p2y, p3x, p3y, p4x, p4y) {
var line1 = new Object();
line1.x1 = p1x;
line1.y1 = p1y;
line1.x2 = p2x;
line1.y2 = p2y;
line1.m = (line1.y1-line1.y2)/(line1.x1-line1.x2);
if (line1.x1-line1.x2 == 0) {
line1.m = 99999999;
}
line1.b = (-1)*(line1.m*line1.x1-line1.y1);
var line2 = new Object();
line2.x1 = p3x;
line2.y1 = p3y;
line2.x2 = p4x;
line2.y2 = p4y;
line2.m = (line2.y1-line2.y2)/(line2.x1-line2.x2);
if (line2.x1-line2.x2 == 0) {
line2.m = 99999999;
}
line2.b = (-1)*(line2.m*line2.x1-line2.y1);
var poi = new Object();
var rf = new Object();
rf.xi = (line1.b-line2.b)/(line2.m-line1.m);
rf.yi = line1.m*rf.xi+line1.b;
poi = rf;
if (line1.x1 == line1.x2) {
line1.x1 += .00001;
}
if (line1.y1 == line1.y2) {
line1.y1 += .00001;
}
if ((((poi.xi>line1.x1 && poi.xi<line1.x2) || (poi.xi<line1.x1 && poi.xi>line1.x2)) && ((poi.xi>line2.x1 && poi.xi<line2.x2) || (poi.xi<line2.x1 && poi.xi>line2.x2))) || (((poi.yi>line1.y1 && poi.yi<line1.y2) || (poi.yi<line1.y1 && poi.yi>line1.y2)) && ((poi.yi>line2.y1 && poi.yi<line2.y2) || (poi.yi<line2.y1 && poi.yi>line2.y2)))) {
return (true);
} else {
return (false);
}
}

There's the flattened function. Paste that in your root timeline. Then, whenever you need to do a collision, just do

if(_root.lineHitTest(1,2,3,4,5,6,7,8)){
//actions
}

1,2 is the x,y of the first point, 2,3 is the x,y of the second point (line 1)
5,6 is the x,y of the 3rd point, 7,8 is the x,y of the 4th point (line 2)

Begoner
Begoner
  • Member since: Oct. 10, 2004
  • Offline.
Forum Stats
Member
Level 10
Blank Slate
Response to As: Line-line Collision Oct. 8th, 2005 @ 03:25 PM Reply

Liam, it's useful because it's faster than hitTests. If you don't like how long it is, it can be shortened:

function lH(l1X1, l1Y1, l1X2, l1Y2, l2X1, l2Y1, l2X2, l2Y2)
{
return ([ ((l2Y1 - ((l2Y2 - l2Y1) / (l2X2 - l2X1)) * l2X1) - (l1Y1 - ((l1Y2 - l1Y1) / (l1X2 - l1X1)) * l1X1)) / (((l1Y2 - l1Y1) / (l1X2 - l1X1)) - ((l2Y2 - l2Y1) / (l2X2 - l2X1))), ((l1Y2 - l1Y1) / (l1X2 - l1X1)) * iX + (l1Y1 - ((l1Y2 - l1Y1) / (l1X2 - l1X1)) * l1X1)]);
}

This is the same thing as Glaiel's script (minus error-checking -- it will only find intersections that work), shortened down to a couple of lines. For the sake of clarity, however, Glaiel's script was longer so as to be comprehensible, while being just as fast.

liam
liam
  • Member since: Dec. 11, 2004
  • Offline.
Forum Stats
Member
Level 22
Blank Slate
Response to As: Line-line Collision Oct. 8th, 2005 @ 03:39 PM Reply

At 10/8/05 03:25 PM, Begoner wrote: stuff

I didn't like it because of how complicated it was, that was all.


Sup, bitches :)

BBS Signature
shazwoogle
shazwoogle
  • Member since: Sep. 27, 2004
  • Offline.
Forum Stats
Member
Level 11
Blank Slate
Response to As: Line-line Collision Oct. 29th, 2005 @ 06:23 PM Reply

thats awsome =D thankyou for that

Glaiel-Gamer
Glaiel-Gamer
  • Member since: Dec. 28, 2004
  • Offline.
Forum Stats
Member
Level 28
Game Developer
Response to As: Line-line Collision Nov. 21st, 2005 @ 07:06 PM Reply

wtf putfile removed my example

Rantzien
Rantzien
  • Member since: Jan. 27, 2005
  • Offline.
Forum Stats
Member
Level 15
Blank Slate
Response to As: Line-line Collision Nov. 21st, 2005 @ 07:45 PM Reply

At 11/21/05 07:06 PM, Glaiel_Gamer wrote: wtf putfile removed my example

Yep. "Copyrighted, pornographic, vulgar or illegal files is not allowed."

Shame on you, Glaiel, with your dirty line-on-line hot sex action.


BBS Signature
Glaiel-Gamer
Glaiel-Gamer
  • Member since: Dec. 28, 2004
  • Offline.
Forum Stats
Member
Level 28
Game Developer
Response to As: Line-line Collision Nov. 21st, 2005 @ 07:55 PM Reply

At 11/21/05 07:45 PM, Rantzien wrote: Shame on you, Glaiel, with your dirty line-on-line hot sex action.

I'm sorry :(

GeoKureli
GeoKureli
  • Member since: Apr. 1, 2003
  • Offline.
Forum Stats
Supporter
Level 19
Game Developer
Response to As: Line-line Collision Feb. 8th, 2006 @ 05:26 PM Reply

for your long if at the end. cant you just check if the y Interception is between the y of both lines?

if (poi.yi > Math.min(line1.y1, line1.y2) &&
poi.yi < Math.max(line1.y1, line1.y2) &&
poi.yi > Math.min(line1.y1, line1.y2) &&
poi.yi < Math.max(line1.y1, line1.y2)) {
}

i havent checked this, but i dont think its possible for the y intercept to be between the 4 points without the x intercept between them. please try this out.

Glaiel-Gamer
Glaiel-Gamer
  • Member since: Dec. 28, 2004
  • Offline.
Forum Stats
Member
Level 28
Game Developer
Response to As: Line-line Collision Feb. 8th, 2006 @ 05:28 PM Reply

At 2/8/06 05:26 PM, FlaccidLad wrote: for your long if at the end. cant you just check if the y Interception is between the y of both lines?

i havent checked this, but i dont think its possible for the y intercept to be between the 4 points without the x intercept between them. please try this out.

yes it's what I had originally but it posed issues with horizontal/vertival lines

GeoKureli
GeoKureli
  • Member since: Apr. 1, 2003
  • Offline.
Forum Stats
Supporter
Level 19
Game Developer
Response to As: Line-line Collision Feb. 8th, 2006 @ 05:34 PM Reply

wouldn't using >= and <= fix that up. it seems too obvious for you to overlook, so im guessing it doesnt work?

Glaiel-Gamer
Glaiel-Gamer
  • Member since: Dec. 28, 2004
  • Offline.
Forum Stats
Member
Level 28
Game Developer
Response to As: Line-line Collision Feb. 8th, 2006 @ 05:35 PM Reply

At 2/8/06 05:34 PM, FlaccidLad wrote: wouldn't using >= and <= fix that up. it seems too obvious for you to overlook, so im guessing it doesnt work?

nope

GeoKureli
GeoKureli
  • Member since: Apr. 1, 2003
  • Offline.
Forum Stats
Supporter
Level 19
Game Developer
Response to As: Line-line Collision Feb. 8th, 2006 @ 05:57 PM Reply

tried it out, i see what you mean.

Blaze
Blaze
  • Member since: Aug. 4, 2005
  • Offline.
Forum Stats
Member
Level 22
Programmer
Response to As: Line-line Collision Feb. 8th, 2006 @ 06:11 PM Reply

Man, and i JUST saw that y = mx+b ecuation today for the first time in my life.

QUITE useful Glaiel, thanks a lot!