00:00
00:00

As: Line-line Collision

9,173 Views | 39 Replies
New Topic Respond to this Topic

As: Line-line Collision 2005-10-07 16:38:46


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

Response to As: Line-line Collision 2005-10-07 16:57:02


Really, really unnecessary stuff you have there.


Sup, bitches :)

BBS Signature

Response to As: Line-line Collision 2005-10-07 16:57:55


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


BBS Signature

Response to As: Line-line Collision 2005-10-07 17:06:30


glaiel you are one smart mother effer

Response to As: Line-line Collision 2005-10-07 17:08:04


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

why?

Response to As: Line-line Collision 2005-10-07 17:47:22


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

Response to As: Line-line Collision 2005-10-07 17:55:43


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.

Response to As: Line-line Collision 2005-10-07 18:04:09


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


This blog I made | This game sucks | I, twit

Just trying to get enough Twitter followers to quit Facebook forever

Response to As: Line-line Collision 2005-10-07 18:07:33


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

Response to As: Line-line Collision 2005-10-07 18:08:34


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


This blog I made | This game sucks | I, twit

Just trying to get enough Twitter followers to quit Facebook forever

Response to As: Line-line Collision 2005-10-07 19:02:25


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

Response to As: Line-line Collision 2005-10-07 22:55:50


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

Response to As: Line-line Collision 2005-10-07 23:00:21


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.

Response to As: Line-line Collision 2005-10-07 23:12:18


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

Response to As: Line-line Collision 2005-10-07 23:20:07


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.

Response to As: Line-line Collision 2005-10-08 04:10:44


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

Response to As: Line-line Collision 2005-10-08 07:36:57


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.

Response to As: Line-line Collision 2005-10-08 08:54:40


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)

Response to As: Line-line Collision 2005-10-08 15:25:25


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.

Response to As: Line-line Collision 2005-10-08 15:39:14


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

Response to As: Line-line Collision 2005-10-29 18:23:38


thats awsome =D thankyou for that

Response to As: Line-line Collision 2005-11-21 19:06:05


wtf putfile removed my example

Response to As: Line-line Collision 2005-11-21 19:45:45


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

Response to As: Line-line Collision 2005-11-21 19:55:30


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 :(

Response to As: Line-line Collision 2006-02-08 17:26:39


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.


This blog I made | This game sucks | I, twit

Just trying to get enough Twitter followers to quit Facebook forever

Response to As: Line-line Collision 2006-02-08 17:28:53


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

Response to As: Line-line Collision 2006-02-08 17:34:12


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


This blog I made | This game sucks | I, twit

Just trying to get enough Twitter followers to quit Facebook forever

Response to As: Line-line Collision 2006-02-08 17:35:10


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

Response to As: Line-line Collision 2006-02-08 17:57:37


tried it out, i see what you mean.


This blog I made | This game sucks | I, twit

Just trying to get enough Twitter followers to quit Facebook forever

Response to As: Line-line Collision 2006-02-08 18:11:47


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

QUITE useful Glaiel, thanks a lot!