I wonder what is the best way to do a fast collision detection for a line and circles.
I want to create some kind of laser weapon which should detect enemy collisions by looking for the laser (which can be directed in all angles) hitting the enemies (circles).
Can anyone help me with this?
Are you seeing problems with the code you have now? If you could post a snippet it would help identify a potential solution.
I had problems getting the end of a line correctly and the angle was messed up.
I tried something else: Instead of a line I now use a group where I put the line in. And additionally I place an endpoint at the end of the line, so I don’t have to calculate this end position anymore. Now I can get the steps between the start and endpoint on the line, which I then check for collisions with the enemy objects. For now it is working. I have to do some performance checks… but it looks good in the simulator for now.
Thx!
In case you still want it, here’s a description of some of the math for it.
A circle consists of all points a certain distance (the radius, r) from a center (c): (x - cx)2 + (y - cy)2 = r2
A line can be represented as an interpolation between two points, say p and q. Then at a given “time” t we would have
x = px + t * (qx - px), or equivalently x = (1 - t) * px + t * qx. Ditto for y.
Most of these values you will know, or can figure out. What you want is to find t. Once you have that you can plug it back in for x and y to find the final positions.
Notice that you can substitute the line equation in for x (and likewise another for y) in the circle equation above.
After doing that, and boiling everything down some, you’ll get something in the form a * t2 + b * t + c = 0. This can
be solved by the quadratic equation.
This will give you zero, one, or two times. Zero means you didn’t even have a collision: you missed, or gave it a “line”
that was really just a point (p = q). One means you grazed the circle’s edge. Finally, two means you went in one side
and out the other.
The other thing you’ll need to check is the value of t. A t < 0 means the collision was behind you, whereas > 1 means
it was in front of your second point. Whether you want these is up to you.
In code, finding the times might go something like this (untested):
function FindIntersections (px, py, qx, qy, cx, cy, r) -- (p + t \* w - C) . (p + t \* w - C) = r^2 local dx, dy = px - cx, py - cy local wx, wy = qx - px, qy - py local a = wx \* wx + wy \* wy if a \< 1e-10 then -- a near 0 means p = q, or close enough return 0 else local b = 2 \* (dx \* wx + dy \* wy) -- note that we can cancel this 2 out, but -- must adjust some of the terms that follow local c = dx^2 + dy^2 - r^2 -- A discriminant \< 0 means we missed... local disc = b^2 - 4 \* a \* c if disc \< 0 then return 0 -- ...whereas when nearly 0 means one collision... elseif disc \< 1e-10 then return 1, -b / (2 \* a) -- ...otherwise we have 2 collisions. else disc = math.sqrt(disc) return 2, (-b - disc) / (2 \* a), (-b + disc) / (2 \* a) -- note: times are in order end end end
To filter out times outside the [0, 1] range, something like this (again untested) might do:
function FixTimes (n, t1, t2) if n == 1 then if t1 \>= 0 and t1 \<= 1 then return 1, t1 end elseif n == 2 then if t1 \>= 0 then -- assumes t1 \< t2 if t2 \<= 1 then return 2, t1, t2 elseif t1 \<= 1 then return 1, t1 end elseif t2 \>= 0 and t2 \<= 1 then return 1, t2 end end return 0 endWow! Thank you for the detailed code!!!
Are you seeing problems with the code you have now? If you could post a snippet it would help identify a potential solution.
I had problems getting the end of a line correctly and the angle was messed up.
I tried something else: Instead of a line I now use a group where I put the line in. And additionally I place an endpoint at the end of the line, so I don’t have to calculate this end position anymore. Now I can get the steps between the start and endpoint on the line, which I then check for collisions with the enemy objects. For now it is working. I have to do some performance checks… but it looks good in the simulator for now.
Thx!
In case you still want it, here’s a description of some of the math for it.
A circle consists of all points a certain distance (the radius, r) from a center (c): (x - cx)2 + (y - cy)2 = r2
A line can be represented as an interpolation between two points, say p and q. Then at a given “time” t we would have
x = px + t * (qx - px), or equivalently x = (1 - t) * px + t * qx. Ditto for y.
Most of these values you will know, or can figure out. What you want is to find t. Once you have that you can plug it back in for x and y to find the final positions.
Notice that you can substitute the line equation in for x (and likewise another for y) in the circle equation above.
After doing that, and boiling everything down some, you’ll get something in the form a * t2 + b * t + c = 0. This can
be solved by the quadratic equation.
This will give you zero, one, or two times. Zero means you didn’t even have a collision: you missed, or gave it a “line”
that was really just a point (p = q). One means you grazed the circle’s edge. Finally, two means you went in one side
and out the other.
The other thing you’ll need to check is the value of t. A t < 0 means the collision was behind you, whereas > 1 means
it was in front of your second point. Whether you want these is up to you.
In code, finding the times might go something like this (untested):
function FindIntersections (px, py, qx, qy, cx, cy, r) -- (p + t \* w - C) . (p + t \* w - C) = r^2 local dx, dy = px - cx, py - cy local wx, wy = qx - px, qy - py local a = wx \* wx + wy \* wy if a \< 1e-10 then -- a near 0 means p = q, or close enough return 0 else local b = 2 \* (dx \* wx + dy \* wy) -- note that we can cancel this 2 out, but -- must adjust some of the terms that follow local c = dx^2 + dy^2 - r^2 -- A discriminant \< 0 means we missed... local disc = b^2 - 4 \* a \* c if disc \< 0 then return 0 -- ...whereas when nearly 0 means one collision... elseif disc \< 1e-10 then return 1, -b / (2 \* a) -- ...otherwise we have 2 collisions. else disc = math.sqrt(disc) return 2, (-b - disc) / (2 \* a), (-b + disc) / (2 \* a) -- note: times are in order end end end
To filter out times outside the [0, 1] range, something like this (again untested) might do:
function FixTimes (n, t1, t2) if n == 1 then if t1 \>= 0 and t1 \<= 1 then return 1, t1 end elseif n == 2 then if t1 \>= 0 then -- assumes t1 \< t2 if t2 \<= 1 then return 2, t1, t2 elseif t1 \<= 1 then return 1, t1 end elseif t2 \>= 0 and t2 \<= 1 then return 1, t2 end end return 0 endWow! Thank you for the detailed code!!!