Calculating intersecting lines

Games
#1

I’m working on a space game and am trying to implement an efficient way of predicting whether two ships will move within a specific distance of each other over time. Can anyone recommend a more efficient way of doing this? My vector math is a bit rusty. I could probably make the loop more efficient by not checking every frame over four seconds.

[lua] function ship.intersection(target)
local sx, sy, svx, svy, frames
local tx, ty, tvx, tvy, dx, dy
local hitFrame, hitX, hitY

sx = ship.x
sy = ship.y
svx = ship.vx – x velocity
svy = ship.vy – y velocity
frames = 120
tx = target.x
ty = target.y
tvx = target.vx – x velocity
tvy = target.vy – y velocity

for i = 1, frames do
sx = sx + svx – calculate future positions
sy = sy + svy
tx = tx + tvx
ty = ty + tvy
dx = sx - tx – x distance between ship and target
dy = sy - ty – y distance between ship and target

local d = math.sqrt(dx * dx + dy * dy)

if d < 40 then
hitFrame = i
hitX = tx
hitY = ty

break
end
end

return hitFrame, hitX, hitY

end[/lua] [import]uid: 1560 topic_id: 31761 reply_id: 331761[/import]

#2

@Dotnaught

Hi. This is a pseudo answer and an attempt to get more info on your situation.

  1. To be clear, are you trying to determine if two velocity vectors (points moving over time) will intersect, and not wheter two non-point bodies may collide?

If so, horacebury has an excellent mathlib here: http://developer.coronalabs.com/code/line-intersection that solves whether two lines will intersect.

  1. If you’re actually trying to see if two non-point (i.e. multi-pixel) bodies will collide, how soon do you need to know? Immediately or just before the collision? If it is just before, you can use the built-in preCollision() callback to get this notification.

If I totally missed the point of your question, please reply and try to clarify. Thanks.

-edo out! [import]uid: 110228 topic_id: 31761 reply_id: 126794[/import]

#3

@Dotnaught,

Your post is really making me think. I would have known the answer to this problem right away about 15 years ago, but its been so long since I had to actually calculate something like this, I’m a bit rusty.

I’ve re-read your question and I think it can be simplified to this question,

“How does one predict if, when, and where a moving point will intersect a moving circle?”

Unless my brain is completely mushy today (completely possible) the radius of the moving circle encapsulates the ‘distance between two points’ part of your problem.

Having said all of this, I don’t yet have an answer, but I have a starting point. I’m reading this article now: http://seb.ly/2010/01/predicting-circle-line-collisions/ and will have a go at providing a working solution to your problem using Corona.

For now, thank you for holding… your question is interesting to me… thank you for holding…

-edo out! [import]uid: 110228 topic_id: 31761 reply_id: 126801[/import]

#4

Hi Edo,

Thanks for the suggestions. I think that math library you posted will prove helpful. The code I posted works but I know it’s unnecessarily calculation-intensive. I’m using the code to predict where two moving ships will be at a future point, assuming their trajectories don’t change. So it’s a vector intersection problem.

Tom
[import]uid: 1560 topic_id: 31761 reply_id: 126805[/import]

#5

@Dotnaught,

The code you’re looking for can be derived from this article’s solution: http://twobitcoder.blogspot.com/2010/04/circle-collision-detection.html

Simply treat one of the points as a circle of zero-radius and the other point as a circle with radius D where D is the distance at which you wish to detect ‘near-collsion’.

Once you have used the equation from the article to find a t, simply plug it back into the A(t) and B(t) equations to get the point at which ship A and B will be D distance apart.

I’m still working on a visual solution to this to test everything out. I’ll let you know when it’s ready.

Cheers,

edo out [import]uid: 110228 topic_id: 31761 reply_id: 126848[/import]

#6

@Dotnaught,

This should be my last post to this thread for a while.

1. I tested the math found in the article @ http://twobitcoder.blogspot.com/2010/04/circle-collision-detection.html

Results: It works for almost all cases, except these special cases:
a. Case where point starts out inside radius of circle and never hits edge of circle. No intersection will be detected.

b. Case where discriminant == 0 and 2a == 0. This results in divide by zero and is a false positive. No intersection actually occurs, but you need to write your code to catch this case or it will behave badly.
2. I used SSK for Corona (AKA SSKCorona, AKA Corona SSK… Yes, I need to work out the naming convetion for my kit) to provide a demo of this in action.

Here is a video link: http://www.youtube.com/watch?v=u2iZhklBzBc

Note: In the video, pps is pixels-per-second and is my ‘velocity’ if it isn’t clear.

You can get SSK here: https://github.com/roaminggamer/SSKCorona

Beware! SSK should be considered very earlyl beta and the example (at SSKCorona\sampler\ssk_sampler\forumhelp\121008_calculating_intersecting_lines.lua) is a bit messy.
[import]uid: 110228 topic_id: 31761 reply_id: 126941[/import]

#7

Hey Edo,

That’s awesome, thanks. [import]uid: 1560 topic_id: 31761 reply_id: 126955[/import]

#8

@Dotnaught

Hi. This is a pseudo answer and an attempt to get more info on your situation.

  1. To be clear, are you trying to determine if two velocity vectors (points moving over time) will intersect, and not wheter two non-point bodies may collide?

If so, horacebury has an excellent mathlib here: http://developer.coronalabs.com/code/line-intersection that solves whether two lines will intersect.

  1. If you’re actually trying to see if two non-point (i.e. multi-pixel) bodies will collide, how soon do you need to know? Immediately or just before the collision? If it is just before, you can use the built-in preCollision() callback to get this notification.

If I totally missed the point of your question, please reply and try to clarify. Thanks.

-edo out! [import]uid: 110228 topic_id: 31761 reply_id: 126794[/import]

#9

@Dotnaught,

Your post is really making me think. I would have known the answer to this problem right away about 15 years ago, but its been so long since I had to actually calculate something like this, I’m a bit rusty.

I’ve re-read your question and I think it can be simplified to this question,

“How does one predict if, when, and where a moving point will intersect a moving circle?”

Unless my brain is completely mushy today (completely possible) the radius of the moving circle encapsulates the ‘distance between two points’ part of your problem.

Having said all of this, I don’t yet have an answer, but I have a starting point. I’m reading this article now: http://seb.ly/2010/01/predicting-circle-line-collisions/ and will have a go at providing a working solution to your problem using Corona.

For now, thank you for holding… your question is interesting to me… thank you for holding…

-edo out! [import]uid: 110228 topic_id: 31761 reply_id: 126801[/import]

#10

Hi Edo,

Thanks for the suggestions. I think that math library you posted will prove helpful. The code I posted works but I know it’s unnecessarily calculation-intensive. I’m using the code to predict where two moving ships will be at a future point, assuming their trajectories don’t change. So it’s a vector intersection problem.

Tom
[import]uid: 1560 topic_id: 31761 reply_id: 126805[/import]

#11

@Dotnaught,

The code you’re looking for can be derived from this article’s solution: http://twobitcoder.blogspot.com/2010/04/circle-collision-detection.html

Simply treat one of the points as a circle of zero-radius and the other point as a circle with radius D where D is the distance at which you wish to detect ‘near-collsion’.

Once you have used the equation from the article to find a t, simply plug it back into the A(t) and B(t) equations to get the point at which ship A and B will be D distance apart.

I’m still working on a visual solution to this to test everything out. I’ll let you know when it’s ready.

Cheers,

edo out [import]uid: 110228 topic_id: 31761 reply_id: 126848[/import]

#12

@Dotnaught,

This should be my last post to this thread for a while.

1. I tested the math found in the article @ http://twobitcoder.blogspot.com/2010/04/circle-collision-detection.html

Results: It works for almost all cases, except these special cases:
a. Case where point starts out inside radius of circle and never hits edge of circle. No intersection will be detected.

b. Case where discriminant == 0 and 2a == 0. This results in divide by zero and is a false positive. No intersection actually occurs, but you need to write your code to catch this case or it will behave badly.
2. I used SSK for Corona (AKA SSKCorona, AKA Corona SSK… Yes, I need to work out the naming convetion for my kit) to provide a demo of this in action.

Here is a video link: http://www.youtube.com/watch?v=u2iZhklBzBc

Note: In the video, pps is pixels-per-second and is my ‘velocity’ if it isn’t clear.

You can get SSK here: https://github.com/roaminggamer/SSKCorona

Beware! SSK should be considered very earlyl beta and the example (at SSKCorona\sampler\ssk_sampler\forumhelp\121008_calculating_intersecting_lines.lua) is a bit messy.
[import]uid: 110228 topic_id: 31761 reply_id: 126941[/import]

#13

Hey Edo,

That’s awesome, thanks. [import]uid: 1560 topic_id: 31761 reply_id: 126955[/import]