Circle-line collision

[Marcus]

I wrote a quick test for how collisions between moving objects (player and enemies) and the static walls should work in that 3d thing I'm working on. In the game/engine I will just check for collisions with walls close to the moving objects (a uniform grid will contain information about which walls passes through each cell). But maybe someone may still find this test useful for their own purposes:

Code:

set window "Collision", 640, 480
set redraw off

lines = []
randomize 11
for i = 1 to 8
    ln = [rnd(640), rnd(480), rnd(640), rnd(480)]
    dx = ln[2] - ln[0]; dy = ln[3] - ln[1]
    ln[6] = sqr(dx*dx + dy*dy)
    ln[4] = dx/ln[6]
    ln[5] = dy/ln[6]
    lines[sizeof(lines)] = ln
next

obj = Object(320, 240, 16)

while not keydown(KEY_ESCAPE, true)
    'obj.x = mousex(); obj.y = mousey()
    if keydown(KEY_LEFT)  obj.x = obj.x - 4
    if keydown(KEY_RIGHT)  obj.x = obj.x + 4
    if keydown(KEY_UP)  obj.y = obj.y - 4
    if keydown(KEY_DOWN)  obj.y = obj.y + 4   
    PushOut(obj, lines)
   
    set color 0, 0, 0
    cls
    set color 255, 255, 255
    DrawLines(lines)
    obj.Draw()
   
    set caret width(primary)/2, 0
    center "Use the arrow keys to move the circle around"
   
    redraw
    fwait 60
wend

function DrawLines(lines)
    foreach ln in lines  draw line ln[0], ln[1], ln[2], ln[3]
endfunc

function Object(x, y, r)
    return [x: x, y: y, r: r, rsqr: r*r,
            Draw: function(); draw ellipse .x, .y, .r, .r, false; endfunc]
endfunc

function PushOut(obj, lines)
    ' Let all lines push the object around a maximum of 10 times. This is not a recommended
    ' approach, just for testing.
    tests = 10
    for i = 1 to tests
        col = false
        foreach ln in lines
            dp = max(0, min(ln[6], (obj.x - ln[0])*ln[4] + (obj.y - ln[1])*ln[5]))
            px = ln[0] + dp*ln[4]; py = ln[1] + dp*ln[5]
            dx = obj.x - px; dy = obj.y - py
            d = dx*dx + dy*dy
            if d < obj.rsqr
                k = 1/sqr(d)
                obj.x = px + dx*k*obj.r
                obj.y = py + dy*k*obj.r
                col = true
            endif
        next
        if not col break
    next
endfunc

This is pretty much how I did it in the GLOOM library for n6 too, if my memory is correct (source code since long gone).

[kevin]

Very good, thank you. This seems to be very efficient - I was consistently getting over 900 fps on my very old laptop, with minimums still over 600. I will certainly be looking to find a use for this

[Marcus]

Very good, thank you. This seems to be very efficient - I was consistently getting over 900 fps on my very old laptop, with minimums still over 600. I will certainly be looking to find a use for this

As long as the speed doesn't get crazy, altering the lines shouldn't be a problem for the collision tests. But don't forget to recalculate the extra data for a line if you do:

Code:

    dx = ln[2] - ln[0]; dy = ln[3] - ln[1]
    ln[6] = sqr(dx*dx + dy*dy)
    ln[4] = dx/ln[6]
    ln[5] = dy/ln[6]

[johnno56]

I wrote a quick test for how collisions between moving objects (player and enemies) and the static walls should work in that 3d thing I'm working on. In the game/engine I will just check for collisions with walls close to the moving objects (a uniform grid will contain information about which walls passes through each cell). But maybe someone may still find this test useful for their own purposes:

Code:

set window "Collision", 640, 480
set redraw off

lines = []
randomize 11
for i = 1 to 8
    ln = [rnd(640), rnd(480), rnd(640), rnd(480)]
    dx = ln[2] - ln[0]; dy = ln[3] - ln[1]
    ln[6] = sqr(dx*dx + dy*dy)
    ln[4] = dx/ln[6]
    ln[5] = dy/ln[6]
    lines[sizeof(lines)] = ln
next

obj = Object(320, 240, 16)

while not keydown(KEY_ESCAPE, true)
    'obj.x = mousex(); obj.y = mousey()
    if keydown(KEY_LEFT)  obj.x = obj.x - 4
    if keydown(KEY_RIGHT)  obj.x = obj.x + 4
    if keydown(KEY_UP)  obj.y = obj.y - 4
    if keydown(KEY_DOWN)  obj.y = obj.y + 4   
    PushOut(obj, lines)
   
    set color 0, 0, 0
    cls
    set color 255, 255, 255
    DrawLines(lines)
    obj.Draw()
   
    set caret width(primary)/2, 0
    center "Use the arrow keys to move the circle around"
   
    redraw
    fwait 60
wend

function DrawLines(lines)
    foreach ln in lines  draw line ln[0], ln[1], ln[2], ln[3]
endfunc

function Object(x, y, r)
    return [x: x, y: y, r: r, rsqr: r*r,
            Draw: function(); draw ellipse .x, .y, .r, .r, false; endfunc]
endfunc

function PushOut(obj, lines)
    ' Let all lines push the object around a maximum of 10 times. This is not a recommended
    ' approach, just for testing.
    tests = 10
    for i = 1 to tests
        col = false
        foreach ln in lines
            dp = max(0, min(ln[6], (obj.x - ln[0])*ln[4] + (obj.y - ln[1])*ln[5]))
            px = ln[0] + dp*ln[4]; py = ln[1] + dp*ln[5]
            dx = obj.x - px; dy = obj.y - py
            d = dx*dx + dy*dy
            if d < obj.rsqr
                k = 1/sqr(d)
                obj.x = px + dx*k*obj.r
                obj.y = py + dy*k*obj.r
                col = true
            endif
        next
        if not col break
    next
endfunc

This is pretty much how I did it in the GLOOM library for n6 too, if my memory is correct (source code since long gone).

Your wish is my command....


  gloom.zip (Size: 27.34 KB / Downloads: 6)

I hope this helps...

J

[1micha.elok]

....
the GLOOM library for n6 ...

Your wish is my command....
[ File : gloom.zip ]
...

We have wolf3d, s3d ... and now gloom3d will be available in N7 

[johnno56]

Marcus wrote: This is pretty much how I did it in the GLOOM library for n6 too, if my memory is correct (source code since long gone).

Gloom.zip was provided so that Marcus could confirm his theory... I think it maybe a bit early to assume that the gloom.lib will work with N7... but, it would be cool if it did...

I do not have the original Gloom game, only some of the example files for N6, but I had played it some years ago. Very cool game! Here is a short video of Gloom. https://www.youtube.com/watch?v=lCVhPIu9rR0

[Marcus]

Marcus wrote: This is pretty much how I did it in the GLOOM library for n6 too, if my memory is correct (source code since long gone).

Gloom.zip was provided so that Marcus could confirm his theory... I think it maybe a bit early to assume that the gloom.lib will work with N7... but, it would be cool if it did...

I do not have the original Gloom game, only some of the example files for N6, but I had played it some years ago. Very cool game! Here is a short video of Gloom. https://www.youtube.com/watch?v=lCVhPIu9rR0

I have no plans to port the gloom thing (gloom was actually a doom clone for Amiga) to n7. The thing I'm working on can easily be used for gloom-style games but also for so much more.

Sadly, the important parts of the gloom extension were written in C, and that's the code that's gone, but it doesn't matter that much. Thanks anyway

[johnno56]

No problem... We will eagerly wait for, "the thing"... (insert dramatic music here...)

[Marcus]

Instead of working on the map editor for that "3d thing", I started playing around with the code I posted here.

If you think, rather than just write lines of code more or less by random (that's what I did), it's possible that you can make something interesting of this. I added lots of code to be able to add polygons that can be repositioned and rotated. The 'PushOut' function handles collision between an object (circle) and all the lines in the scene. It also sets a direction (obj.pdx and obj.pdy) which is the "average push out direction". With my random lines of code, I try to use that direction to determine when the object (player) is standing on something (then he can jump), when it hits something from below etc. And ... ugh ... never mind.

Code:

' Experiment.

set window "Collision", 640, 480
set redraw off

#win32

' List of lines that objects can collide with.
lines = []

' Add a square using Polygon and add its lines to lines.
square = Polygon([-50, -50, 50, -50, 50, 50, -50, 50], 320, 240, true)
square.AddTo(lines)
' Add a star using Polygon.
star = Polygon([0, -100, 25, -25, 100, 0, 25, 25, 0, 100, -25, 25, -100, 0, -25, -25], 425, 100, true)
star.AddTo(lines)
' Add another star ...
star2 = Polygon([0, -100, 25, -25, 100, 0, 25, 25, 0, 100, -25, 25, -100, 0, -25, -25], 175, 125, true)
star2.AddTo(lines)
' Add two static rectangle using rectangle.
tmp = Rectangle(64, 480 - 64, 640 - 128, 32)
tmp.AddTo(lines)
tmp = Rectangle(32, 32, 32, 200)
tmp.AddTo(lines)
' Add a rectangle that will spin.
rectangle = Rectangle(110, 300, 130, 32)
rectangle.AddTo(lines)
' Add some borders.
lines[sizeof(lines)] = Line(0, 0, 639, 0)
lines[sizeof(lines)] = Line(639, 0, 639, 479)
lines[sizeof(lines)] = Line(639, 479, 0, 479)
lines[sizeof(lines)] = Line(0, 479, 0, 0)

' Player.
obj = Object(100, 100, 16)
obj.dx = 0
obj.dy = 0

while not keydown(KEY_ESCAPE, true)
    ' Rotate obstacles.
    square.SetAngle(square.Angle() + rad(0.5))
    star.SetAngle(star.Angle() + rad(0.25))
    star2.SetAngle(star2.Angle() - rad(0.5))
    rectangle.SetAngle(rectangle.Angle() - rad(0.25))
   
    if keydown(KEY_LEFT) obj.dx = max(obj.dx - 0.5, -3)
    elseif keydown(KEY_RIGHT)  obj.dx = min(obj.dx + 0.5, 3)
    obj.x = obj.x + obj.dx
    obj.y = obj.y + obj.dy
    PushOut(obj, lines)
   
    ' obj.pdx and obj.pdy has now been set to the average "push direction" caused by all lines
    ' pushing the object around.
   
    ' Push direction y < 0 means the object is being pushed UP. In that case, set dy to 0.
    if obj.pdy < 0
        obj.dy = 0
        ' If push direction y < -0.25, let the player jump.
        if obj.pdy < -0.25 and keydown(KEY_UP, true)
            obj.dy = -5
        endif
    elseif obj.pdy > 0
        obj.dy = max(obj.dy, obj.pdy) 
    endif
    ' Apply gravity.
    obj.dy = min(obj.dy + 0.1, 6)
    ' So ... stuff to dx.
    obj.dx = obj.dx + obj.pdx*0.25 ' I have no idea
    obj.dx = obj.dx*0.95
     
    set color 0, 0, 0
    cls
    set color 255, 255, 255
    DrawLines(lines)
    obj.Draw()
 
    set caret width(primary)/2, 16
    center "Use the arrow keys to move left and right and jump"
 
    redraw
    fwait 60
wend

function DrawLines(lines)
    foreach ln in lines  draw line ln[0], ln[1], ln[2], ln[3]
endfunc


function Object(x, y, r)
    return [x: x, y: y, r: r, rsqr: r*r, pdx: 0, pdy: 0,
            Draw: function(); draw ellipse .x, .y, .r, .r, false; endfunc]
endfunc

' Pushout
' -------
function PushOut(obj, lines)
    tests = 4
    obj.pdx = 0
    obj.pdy = 0
    for i = 1 to tests
        col = false
        foreach ln in lines
            dp = max(0, min(ln[6], (obj.x - ln[0])*ln[4] + (obj.y - ln[1])*ln[5]))
            px = ln[0] + dp*ln[4]; py = ln[1] + dp*ln[5]
            dx = obj.x - px; dy = obj.y - py
            d = dx*dx + dy*dy
            if d < obj.rsqr
                k = 1/sqr(d)
                obj.x = px + dx*k*obj.r
                obj.y = py + dy*k*obj.r
                obj.pdx = obj.pdx + dx*k
                obj.pdy = obj.pdy + dy*k
                col = true
            endif
        next
        if not col break
    next
    if obj.pdx or obj.pdy
        k = 1/sqr(obj.pdx*obj.pdx + obj.pdy*obj.pdy)
        obj.pdx = obj.pdx*k
        obj.pdy = obj.pdy*k
    endif
endfunc

' Polygon
' -------
' Return polygon at position x, y.
function Polygon(points, x, y, closed)
    p = [trans: unset, org: [], x: x, y: y, a: 0, cx: 0, cy: 0]
    pcount = sizeof(points)/2
    centerX = 0
    centerY = 0
    if closed  n = pcount - 1
    else    n = pcount - 2
    for i = 0 to n
        j = (i + 1)%pcount
        p.org[sizeof(p.org)] = Line(
                points[i*2], points[i*2 + 1],
                points[j*2], points[j*2 + 1])
    next
    for i = 0 to pcount - 1
        p.cx = p.cx + points[i*2]; p.cy = p.cy + points[i*2 + 1]
    next

    p.cx = p.cx/pcount; p.cy = p.cy/pcount
    p.trans = copy(p.org)
   
    ' AddTo
    ' -----
    ' Add to list of lines.
    p.AddTo = function(lines)
        foreach ln in .trans  lines[sizeof(lines)] = ln
    endfunc

    ' X
    ' -
    ' Return x coordinate.
    p.X = function()
        return .x
    endfunc
   
    ' Y
    ' -
    ' Return y coordinate.
    p.Y = function()
        return .y
    endfunc
   
    ' Angle
    ' -----
    ' Return angle.
    p.Angle = function()
        return .a
    endfunc
   
    ' SetTransform
    ' ------------
    ' Set position and angle and apply.       
    p.SetTransform = function(x, y, angle)
        .x = x
        .y = y
        .a = angle
        .Transform()
    endfunc
   
    ' SetPosition
    ' -----------
    ' Set position and apply.
    p.SetPosition = function(x, y)
        .x = x
        .y = y
        .Transform()
    endfunc
   
    ' SetAngle
    ' --------
    ' Set angle and apply.
    p.SetAngle = function(angle)
        .a = angle
        .Transform()
    endfunc
   
    ' Transform
    ' ---------
    ' Update transformed polygon.
    p.Transform = function()
        RotateLines(.org, .trans, .cx, .cy, .a)
        foreach ln in .trans
            ln[0] = ln[0] + .x; ln[1] = ln[1] + .y
            ln[2] = ln[2] + .x; ln[3] = ln[3] + .y
            ln[4] = (ln[2] - ln[0])/ln[6]; ln[5] = (ln[3] - ln[1])/ln[6]
        next
    endfunc
   
    p.Transform()
   
    return p
   
    ' RotateLines
    ' -----------
    ' Helper.
    function RotateLines(srcLines, dstLines, aroundX, aroundY, angle)
        c = cos(angle); s = sin(angle)
        for i = 0 to sizeof(srcLines) - 1
            srcLn = srcLines[i]; dstLn = dstLines[i]
            x = srcLn[0] - aroundX; y = srcLn[1] - aroundY
            dstLn[0] = aroundX + x*c - y*s; dstLn[1] = aroundY + y*c + x*s
            x = srcLn[2] - aroundX; y = srcLn[3] - aroundY
            dstLn[2] = aroundX + x*c - y*s; dstLn[3] = aroundY + y*c + x*s
        next
    endfunc   
endfunc

' Rectangle
' ---------
function Rectangle(x, y, w, h)
    w = w - 1
    h = h - 1
    return Polygon([0, 0, w, 0, w, h, 0, h], x, y, true)
endfunc

' Line
' ----
' Return a new line.
function Line(x0, y0, x1, y1)
    ln = [x0, y0, x1, y1]
    dx = ln[2] - ln[0]; dy = ln[3] - ln[1]
    ln[6] = sqr(dx*dx + dy*dy)
    ln[4] = dx/ln[6]
    ln[5] = dy/ln[6]
    return ln
endfunc

[1micha.elok]

... it's possible that you can make something interesting of this. I added lots of code to be able to add polygons that can be repositioned and rotated. ... the object (player) is standing on something (then he can jump), when it hits something from below etc. ...

SIMPLE PHYSICS ENGINE 
   
click the image to zoom in

Your code caught my attention, particularly the ball that was going down from a rectangle above.
Did the gravity force pull the ball down ? 

What will happen next when the ball touch down the earth ? Will the ball bounce back ?
I believe a new born simple physics engine is here now