Hi, I posted here a while ago asking about physics for 2D lines. I got some ideas given to me, but nothing I could really use so I went and produced something that though whilst not a true simulation, looks pretty good I think, and is more than enough for what I need it for. Take a look tell me what you think: FILES WERE VIRUSED. Thanks for informing me Miles Second... Intersection of lines. I've looked about all over the place, and I see now there's even a post just below this one now which is about it, but still all Im seeing is weird formulas with unnammed variables in them that I'm probrably supposed to know. PLEASE does someone have a small piece of code to test if one line intersects another, and at which point. If you really cant give me any code, can someone at least explain the forumla to me properly, I've never really done much on that type of thing, but I'll understand with a bit of help I expect. Thank you Ashley EDIT: Fixed downloads, managed to spell Allegro correctly EDIT(2): OK, this time I really did fix the downloads EDIT(3): Then took them away because they are infected

---

Warning in life.cpp (8): const Happiness is declared but never used.

---

[edited by - allsorts46 on February 16, 2003 5:55:06 PM] [edited by - allsorts46 on February 16, 2003 6:02:17 PM] [edited by - allsorts46 on February 18, 2003 4:39:34 PM]

k... I posted the weird formulas with un explained variables... so i''ll try to explain em... any 2d line can be expressed in the general for of y=mx+b, where x and y are the coordinates, m is the slope and b is the y intercept (ie. where the line crosses the y axis. since if two lines intersect we know that the x and y values will be equal at the point of intersection we can say that they intersect at the point that the formulas describing the lines have the same value, hence the m1x+b1=m2x+b2m then I just did some rearanging to get the final result. hope that helps with that. I''ll try to write some code and post it tonight.

Hello,

Sorry, I don''t have anything to say about your problem as such, but I thought I ought to point out that Norton Antivirus informs me that FallingLines.exe has a W32.Cabanas virus with it. I haven''t read all about it, but it doesn''t look too bad.

Miles

Ok, say we have two lines represented by y=mx + c & y=nx + d, then we want to find a point (x,y) that satisfies both equations. Now if m=n and c=d then the lines are the same, so all points on either line are an intersection. If m=n ( they have the same gradient ) but c!=d then there is no intersection since the lines are parallel. If m!=n the we have a non-trivial case which is easy to solve, subtract one equation from the other to get y-y= (m-n)x + (c-d) -> x = ( d-c )/(m-n ) then plug this into either equation to give y= m (( d-c )/(m-n )) + c , these valuse of x & y will be the point (x,y) of intersection required.

Thanks people, I will try and work it out again when I''m a little less depressed, hopefully might be more successful this time.

---

Warning in life.cpp (8): const Happiness is declared but never used.

---

Well now since the search is working again, I found some code here:




This works fine most of the time, but it doesnt seem to work when the slopes of the lines are the same (thats what it looks like from my simulation). I thought that should be easy to solve: I calculated the slopes of both lines, checked if they were equal, and if they were then alter one line slightly so that they are equal no longer. That didnt work. I took out the condition, and made it check every collision twice; once normally, and once with altered lines. This worked slightly better, but I still have lines ''falling through''. Varying the lines more seemed to help, but the more variation I apply to them the worse the simulation looks. Any ideas why this is happening? I don''t pretend to understand the detection code, I havent really been able to understand the maths at the moment, but I thought the things I tried would have fixed my problems... but they didnt.

---

Warning in life.cpp (8): const Happiness is declared but never used.

---

Ok, jako is checking if dya/dxa=dyb/dxb. The test should not stop there. You have to also check whether either the line from (xa1,ya1) to (xb1,yb1) and (xa2,ya2) to (xb1,yb1) is parallel to the original line. One caveat though is that either of these new lines could have a length of zero. The easiest solution to that is to add into the earlier test a check whether either end point of one line is the same point as either end point of the other line. If they are then you have an intersection and can return immediately. That will guarantee that the new lines don't degenerate into a point so if one is parallel you don't have to check the other.

You may still well get lines passing through one another even with these additions. That is because this is an intersection test, not a collision test. Collision tests involve moving objects. Intersection tests involve static objects. If at time zero line A is x=0 and line B is x=1 then at time one line A is x=1 and line B is x=0 then the two lines passed through one another, but at neither time is there an intersection. Assuming both are both at the same speed then at time 0.5 and only at that time there was an intersection. Line segments that pass through one another and are not parallel do so over some time interval rather than a point in time assuming it is not just one end point of each passing through each other in which case it is still just a point in time. I would assume that is what is causing your problem and parallel/near parallel lines just makes it more likely for you to miss the collision.

I'm not sure how well this routine will adapt to collision detection. It is doing fairly well as it is so it seems some slight modification might make it do well enough. Assuming your lines have no rotational velocity or are rotating slowly relative to a frame interval you can draw a parallagram using the line segment at the start and end of the frame along with connecting the end points at those times. If those parallagrams overlap then you most likely collided. That makes 16 intersection tests. There are scenerios where that would miss some and falsely detect others, but with small intervals it may be well in excess of what you need for reasonable results. I would first just try checking the lines connecting the before/after endpoints against the other line. If that doesn't work well enough try switching whether you use the before or after position of the other line or do both.

As far as testing you could try drawing the parallagrams and single stepping through the frames. Set your frame time to whatever you think the worse possible is since that will be where your missed/false collisions will be at their worse. Single stepping through the whole thing would be a pain so give yourself a key to toggle between free running and single stepping. Just remember it is a game so the goal isn't to be exactly right, but simply right enough that the player will ignore it.

[edited by - LilBudyWizer on February 22, 2003 1:00:16 PM]

Ah I see what you mean... you've given me an idea with the parrelelagrams. My lines do have rotation, but still rather than checking the lines themselves in their new positions, which as you mentioned could mean I miss the collision, I could test for intersection two lines - one for each endpoint - which is between the old and new positions. This way I have a line of the path which the line will take during that time step, and if at any point during the step it hits a line, this should tell me. I see that's basically what you were saying, hopefully it will work well enough. Will try that shortly. Thanks for a bit of inspiration lol.

EDIT: Also considered leaving it as it is, as with my attempt at implementing code to subdivide the timesteps, I started to get only the small lines which are a result of big lines snapping falling through, and this actually looked like a good effect of little splinters of lines flying off the level in all directions. Interesting, but I'd still like to try and get it right rather than 'accepting' the bug. Though knowing me I'll do something stupid like fix it, then try to reimplement it later. Oh well

---

Warning in life.cpp (8): const Happiness is declared but never used.

---

[edited by - allsorts46 on February 23, 2003 10:45:33 AM]

Well um... it sort of worked. The lines dont fall through any more, but there's another strangen side effect instead: when the lines hit a wall they sort of stick to it and go sliding around them, ie the speed calculations are still happening fine and the lines are moving, but they are unable to get free of the walls. When I placed walls in a box shape round the lines and then simulated them, the lines fall normally, hit the bottom line then proceed to slide round the box several times before coming to rest. Strange. I'll go play with it a bit more see what I can do to it.

EDIT: 3 hours later. Well fixed that other problem, now the lines are shattering themselves into billions of zero-sized peices when it hits a wall in a certain way. Not sure about this

---

Warning in life.cpp (8): const Happiness is declared but never used.

---

[edited by - allsorts46 on February 23, 2003 4:50:04 PM]