Want to move a circle from A to B but there's a big line in the way? Need to know where that circle makes contact and how to position the circle along that line? Then this snippet is for you!
This is what you might have heard as swept collision. From from A to B create a straight line. For instance, moving a ball around the screen, each frame it moves it has a start and end point. It might move in a circle, but each step is a straight line. If it moves too fast, it could appear to pass right through objects, thus you have to see if anything is in the way between A and B. For tiny bullets which move super fast (instantly), a simple intersection test between a line (AB) and an object is easy as the bullet has no real size. But what about a ball? The intersection point can place the ball in the middle of a wall, rather than putting its surface up against it.
The large commented section of code was my initial solution, which works just fine. However, someone pointed out I could just translate the wall (a line) by the radius of the ball. It's a much simpler solution. Translate the wall along it's normal towards A (the ball moving from A to B) then do the line-line intersection test. There, you now have the new position of your ball without going through the wall. If you want the point of contact, take the new ball position and add wall's normal to it with a magnitude equal to the radius of the ball. The result? Far shorter code and far less calculations.
setVirtualResolution(800,600)
Type Point2D
x as float
y as float
EndType
A as Point2D
B as Point2D
C as Point2D
D as Point2D
E as Point2D
F as Point2D
`A.x = 40
`A.y = 30
B.x = 400
B.y = 300
C.x = 350
C.y = 75
D.x = 150
D.y = 450
radius = 30
scale# = 1.0 / radius
do
A.x = getRawMouseX()
A.y = getRawMouseY()
`v# = sqrt((B.x-A.x)^2 + (B.y-A.y)^2)
drawCircle(A.x, A.y, radius,0,255,0)
drawCircle(B.x, B.y, radius,0,255,255)
drawLine(A.x, A.y, B.x, B.y, 200,200,200)
drawLine(C.x, C.y, D.x, D.y, 255,255,0)
// line normal
nx# = -(d.y-c.y)
ny# = (d.x-c.x)
s# = sqrt(nx#*nx# + ny#*ny#)
nx# = nx# / s#
ny# = ny# / s#
// rem show normal of line
drawLine(C.x, C.y, C.x+nx#*15, C.y+ny#*15, 255,255,0)
// translate line along it's normal by 'radius' amount
E.x = C.x + nx#*radius
E.y = C.y + ny#*radius
F.x = D.x + nx#*radius
F.y = D.y + ny#*radius
// get intersection of ball travel and translated line
t# = lineIntersection(A, B, E, F)
// Get intersection point along AB
ix# = A.x + (B.x-A.x)*t#
iy# = A.y + (B.y-A.y)*t#
tx# = ix# - nx#*radius
ty# = iy# - ny#*radius
drawCircle(ix#, iy#, radius,255,255,0)
drawCircle(tx#, ty#, 5,255,255,255)
print(t#)
remstart
`E.x = A.x * scale# : E.y = A.y * scale#
`F.x =
`G.x = C.x * scale# : G.y = C.y * scale#
`H.x = D.x * scale# : H.y = D.y * scale#
t# = lineIntersection(A, B, C, D)
// line normal
nx# = -(d.y-c.y)
ny# = (d.x-c.x)
s# = sqrt(nx#*nx# + ny#*ny#)
nx# = nx# / s#
ny# = ny# / s#
// direction normal
dx# = b.x - a.x
dy# = b.y - a.y
d# = sqrt(dx#^2 + dy#^2)
dx# = dx# / d#
dy# = dy# / d#
// line/wall
drawLine(c.x, c.y, c.x+nx#*20,c.y+ny#*20, 255,255,0)
// finds closet point on line to starting circle position
x = D.x - C.x
y = D.y - C.y
n# = ((A.x - C.x) * x) + ((A.y - C.y) * y)
d# = x^2 + y^2
u# = N# / d#
if u# >= 0 and u# <= 1
ix# = C.x + (D.x-C.x)*u#
iy# = C.y + (D.y-C.y)*u#
`k# = sqrt((ix#-A.x)^2 + (iy#-A.y)^2)
`drawCircle(ix#, iy#, 5, 0,255,0)
`e# = A.x - ix#
`f# = A.y - iy#
`dist# = sqrt(e#^2 + f#^2)
endif
`ix# = fx# - nx#*radius
`iy# = fy# - ny#*radius
Alen# = radius
Blen# = sqrt((C.x - zx#)^2 + (C.y-zy#)^2)
alphaX# = B.x - A.x
alphaY# = B.y - A.y
betaX# = -nx#*radius
betaY# = -ny#*radius
Alen# = sqrt((B.x - A.x)^2 + (B.y - A.y)^2)
Blen# = radius
dp# = alphaX#*betaX# + alphaY#*betaY#
a# = (dp# / (Alen#*Blen#))
h# = radius / (a#)
// intersection of two lines
zx# = A.x + (B.x-A.x)*t#
zy# = A.y + (B.y-A.y)*t#
drawCircle(zx#, zy#, 4, 255,0,0)
fx# = zx# - dx#*h#
fy# = zy# - dy#*h#
drawCircle(fx#, fy#, radius, 255,0,255)
ix# = fx# - nx#*radius
iy# = fy# - ny#*radius
drawCircle(ix#, iy#, 5, 0,255,0)
remend
if getRawKeyPressed(27) = 1 then end
Sync()
loop
function drawCircle(x, y, radius, r,g,b)
x1 = x+radius
y1 = y
for i = 0 to 360 step 10
x2 = x + cos(i)*radius
y2 = y + sin(i)*radius
drawLine(x1, y1, x2, y2, r,g,b)
x1 = x2
y1 = y2
next i
endfunction
rem Returns time value along line AB for intersection with line CD
function lineIntersection(A as Point2D, B as Point2D, C as Point2D, D as Point2D)
n# = ((D.x-C.x) * (A.y-C.y)) - ((D.y-C.y) * (A.x-C.x))
d# = ((D.y-C.y) * (B.x-A.x)) - ((D.x-C.x) * (B.y-A.y))
t# = n# / d#
endfunction t#
"I like offending people, because I think people who get offended should be offended." - Linus Torvalds
