Author Topic: My take on sliding non tile based rectangle collision  (Read 1944 times)

Offline nabz32

  • Community Developer
  • Dr. Type
  • ******
  • Posts: 305
    • View Profile
Hello,

I am currently writing an algorythm for sliding non tile based collision for unrotated rectangles.

Here is my testing code:

Code: GLBasic [Select]
CONSTANT maxBox = 5

TYPE coord
        x AS float
        y AS float
        z AS float
ENDTYPE


TYPE cBox
        xl AS int // smaller
        xr AS int // greater
        yd AS int // lower
        yu AS int // higher
        zf AS int // more near
        zb AS int // more far
        frict AS float
        exist AS int
ENDTYPE

GLOBAL box[] AS cBox

drawSimulation()

FUNCTION drawSimulation:
        LOCAL mx% , my% , b1% , b2%
        LOCAL l1S AS coord , l1E AS coord , get AS coord
        DIM box[10]
        FOR i = 0 TO maxBox - 2 // fill Boxes ( 2D only for simulation )
                box[i].xl = 50 * i
                box[i].xr = 50 + 50 * i
                box[i].yd = -50
                box[i].yu = 50
                box[i].zf = 50
                box[i].zb = 125
                box[i].exist = 1
                sortCube( i )
        NEXT
        box[4].xl = 125
        box[4].xr = 175
        box[4].yd = -50
        box[4].yu = 50
        box[4].zf = 125
        box[4].zb = 175
        box[4].exist = 1
        X_MAKE2D
        WHILE TRUE
                FOR i = 0 TO maxBox - 1
                        DrawCube(i)
                NEXT
                MOUSESTATE mx , my , b1 , b2
                l1S.x = mx ; l1S.z = my
                l1E.x = mx - 10 ; l1E.z = my - 10
                l1E.y = 0 ; l1S.y = 0
                DRAWLINE l1S.x , l1S.z , l1E.x , l1E.z , RGB( 122 , 122 , 122 )
                get = checkinters( l1S , l1E )
                SHOWSCREEN
        WEND
ENDFUNCTION

FUNCTION checkinters AS coord: l1S AS coord , l1E AS coord
        LOCAL cPnt AS coord , temp AS coord , tempE AS coord , cpNear AS coord , smDist# AS float , iSm AS int , l1EO AS coord , l1SO AS coord
        l1SO = l1S
        l1EO = l1E
        FOR iG = 0 TO 1 // goes through two times, to make shure that all collisions apply correctly after the collision vector has been altered
                FOR i = 0 TO maxBox - 1
                        iSm = -1 ; smDist = 50000.0
                        l1S = l1SO
                        IF box[i].exist = 1
                                FOR i2 = 0 TO 3
                                        IF i2 = 0
                                                temp.x = box[i].xl ; temp.z = box[i].zf ; tempE.x = box[i].xr ; tempE.z = box[i].zf // face along zfront ( 0 )
                                        ENDIF
                                        IF i2 = 1
                                                temp.x = box[i].xl ; temp.z = box[i].zf ; tempE.x = box[i].xl ; tempE.z = box[i].zb // face along xl     ( 1 )
                                        ENDIF
                                        IF i2 = 2
                                                temp.x = box[i].xr ; temp.z = box[i].zb ; tempE.x = box[i].xl ; tempE.z = box[i].zb // face along zb     ( 2 )
                                        ENDIF
                                        IF i2 = 3
                                                temp.x = box[i].xr ; temp.z = box[i].zb ; tempE.x = box[i].xr ; tempE.z = box[i].zf // face along xr     ( 3 )
                                        ENDIF
                                        cPnt = intersection( l1S , l1E , temp , tempE )
                                        IF cPnt.x > -1
                                                IF SQR( ( cPnt.x - l1SO.x ) * ( cPnt.x - l1SO.x ) + ( cPnt.z - l1SO.z ) * ( cPnt.z - l1SO.z ) ) < smDist
                                                        // also check if cut point is not between two near faces of different boxes
                                                        IF pointbetweenFaces( cPnt , i2 , i ) = 0
                                                                smDist = SQR( ( cPnt.x - l1SO.x ) * ( cPnt.x - l1SO.x ) + ( cPnt.z - l1SO.z ) * ( cPnt.z - l1SO.z ) ) ; cpNear = cPnt ; iSm = i2
                                                        ENDIF
                                                ENDIF
                                        ENDIF
                                NEXT
                                IF iSm = 0 OR iSm = 2 // here transformation of movement has to be calculated and applyed for line inters checking with the next rectangle ( by using the collision point with the smallest distance TO players old position )
                                        l1E.z = cpNear.z // block z ( sides 0 and 2 )
                                ENDIF
                                IF iSm = 1 OR iSm = 3
                                        l1E.x = cpNear.x // block x ( sides 1 and 3 )
                                ENDIF
                        ENDIF
                NEXT
        NEXT
        DRAWLINE l1S.x , l1S.z , l1E.x , l1E.z , RGB(255 , 0 , 0 )
        l1E.x = l1E.x - l1EO.x
        l1E.z = l1E.z - l1EO.z
        RETURN l1E
ENDFUNCTION

FUNCTION pointbetweenFaces: point AS coord , side AS int , boxCh // checks if the point is in a space which adjacts with another cubes face.
        LOCAL fChS AS coord , fChE AS coord , fTChS AS coord , fTChE AS coord
        IF side = 0
                fTChS.z = box[boxCh].zf
        ENDIF
        IF side = 1
                fTChS.x = box[boxCh].xl
        ENDIF
        IF side = 2
                fTChS.z = box[boxCh].zb
        ENDIF
        IF side = 3
                fTChS.x = box[boxCh].xr
        ENDIF
        FOR i = 0 TO maxBox - 1
                IF i <> boxCh AND box[i].exist = 1
                        IF side = 0 // get opposite face of another object to the checked faces direction
                                fChS.x = box[i].xl ; fChS.y = box[i].yd ; fChS.z = box[i].zb
                                fChE.x = box[i].xr ; fChE.y = box[i].yu ; fChE.z = box[i].zb
                                IF ABS( fChS.z - fTChS.z ) <= 25
                                        IF point.x > fChS.x AND point.x < fChE.x AND point.y >= fChS.y AND point.y <= fChE.y
                                                RETURN 1
                                        ENDIF
                                ENDIF
                        ENDIF
                        IF side = 1
                                fChS.x = box[i].xr ; fChS.y = box[i].yd ; fChS.z = box[i].zf
                                fChE.x = box[i].xr ; fChE.y = box[i].yu ; fChE.z = box[i].zb
                                IF ABS( fChS.x - fTChS.x ) <= 25
                                        IF point.z > fChS.z AND point.z < fChE.z AND point.y >= fChS.y AND point.y <= fChE.y
                                                RETURN 1
                                        ENDIF
                                ENDIF
                        ENDIF
                        IF side = 2
                                fChS.x = box[i].xl ; fChS.y = box[i].yd ; fChS.z = box[i].zf
                                fChE.x = box[i].xr ; fChE.y = box[i].yu ; fChE.z = box[i].zf
                                IF ABS( fChS.z - fTChS.z ) <= 25
                                        IF point.x > fChS.x AND point.x < fChE.x AND point.y >= fChS.y AND point.y <= fChE.y
                                                RETURN 1
                                        ENDIF
                                ENDIF
                        ENDIF
                        IF side = 3
                                fChS.x = box[i].xl ; fChS.y = box[i].yd ; fChS.z = box[i].zf
                                fChE.x = box[i].xl ; fChE.y = box[i].yu ; fChE.z = box[i].zb
                                IF ABS( fChS.x - fTChS.x ) <= 25
                                        IF point.z > fChS.z AND point.z < fChE.z AND point.y >= fChS.y AND point.y <= fChE.y
                                                RETURN 1
                                        ENDIF
                                ENDIF
                        ENDIF
                ENDIF
        NEXT
        RETURN 0
ENDFUNCTION


FUNCTION intersection AS coord: l1S AS coord , l1E AS coord , l2S AS coord , l2E AS coord // standart line line intersection point function
        LOCAL x1 AS float , y1 AS float , x2 AS float , y2 AS float , x3 AS float , y3 AS float , x4 AS float , y4 AS float  , d AS float , pre AS float
        LOCAL post AS float , x AS float , y AS float
        LOCAL fail AS coord , ret AS coord
        fail.x = -1 ; fail.z = -1 ; fail.y = -1 // assumes that coordinates are always positive values!
        x1 = l1S.x ; x2 = l1E.x ; x3 = l2S.x ; x4 = l2E.x
        y1 = l1S.z ; y2 = l1E.z ; y3 = l2S.z ; y4 = l2E.z // I will use z for y in the later game, y collision is a whole other story.
        d = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4)
        IF d = 0 THEN RETURN fail
        pre = (x1*y2 - y1*x2) ; post = (x3*y4 - y3*x4)
        x = ( pre * (x3 - x4) - (x1 - x2) * post ) / d
        y = ( pre * (y3 - y4) - (y1 - y2) * post ) / d
        IF ( x < MIN(x1, x2) OR x > MAX(x1, x2) OR x < MIN(x3, x4) OR x > MAX(x3, x4) ) THEN RETURN fail
        IF ( y < MIN(y1, y2) OR y > MAX(y1, y2) OR y < MIN(y3, y4) OR y > MAX(y3, y4) ) THEN RETURN fail
        ret.x = x ; ret.z = y
        RETURN ret
ENDFUNCTION

FUNCTION sortCube: i AS int
        IF box[i].xl > box[i].xr THEN SWAP box[i].xl , box[i].xr
        IF box[i].zf > box[i].zb THEN SWAP box[i].zf , box[i].zb
        IF box[i].yd > box[i].yu THEN SWAP box[i].yd , box[i].yu
ENDFUNCTION

FUNCTION DrawCube: i AS int
        DRAWLINE box[i].xl , box[i].zf , box[i].xr , box[i].zf , RGB( 122 , 255 , 55 + i * 20 )
        DRAWLINE box[i].xl , box[i].zf , box[i].xl , box[i].zb , RGB( 122 , 255 , 55 + i * 20 )
        DRAWLINE box[i].xr , box[i].zb , box[i].xl , box[i].zb , RGB( 122 , 255 , 55 + i * 20 )
        DRAWLINE box[i].xr , box[i].zb , box[i].xr , box[i].zf , RGB( 122 , 255 , 55 + i * 20 )
ENDFUNCTION
 

My Problem is, that this won´t work when the vector starts inside or at the very edge of the cube.
So the Player will run through walls sometimes.

Offline nabz32

  • Community Developer
  • Dr. Type
  • ******
  • Posts: 305
    • View Profile
A modified Version that seems to work
if the coordinates are always positive.

Code: GLBasic [Select]
CONSTANT maxBox = 5

TYPE coord
        x AS float
        y AS float
        z AS float
ENDTYPE


TYPE cBox
        xl AS float // smaller
        xr AS float // greater
        yd AS float // lower
        yu AS float // higher
        zf AS float // more near
        zb AS float // more far
        frict AS float
        exist AS int
ENDTYPE

GLOBAL box[] AS cBox

drawSimulation()

FUNCTION drawSimulation:
        LOCAL mx# AS float , my# AS float
        LOCAL l1S AS coord , l1E AS coord , get AS coord
        DIM box[10]
        FOR i = 0 TO maxBox - 2 // fill Boxes ( 2D only for simulation )
                box[i].xl = 50 * i
                box[i].xr = 50 + 50 * i
                box[i].yd = -50
                box[i].yu = 50
                box[i].zf = 50
                box[i].zb = 125
                box[i].exist = 1
                sortCube( i )
        NEXT
        box[4].xl = 125
        box[4].xr = 175
        box[4].yd = -50
        box[4].yu = 50
        box[4].zf = 125
        box[4].zb = 175
        box[4].exist = 1
        X_MAKE2D
        WHILE TRUE
                FOR i = 0 TO maxBox - 1
                        DrawCube(i)
                NEXT
                l1S.x = mx ; l1S.z = my
                IF KEY(203 ) THEN mx = mx -3 + (RND(20)*0.1)
                IF KEY(205 ) THEN mx = mx +3 - (RND(20)*0.1)
                IF KEY(200 ) THEN my = my -3 + (RND(20)*0.1)
                IF KEY(208 ) THEN my = my +3 - (RND(20)*0.1)
                l1E.x = mx ; l1E.z = my
                l1E.y = 0 ; l1S.y = 0
                DRAWLINE l1S.x , l1S.z , l1E.x , l1E.z , RGB( 122 , 122 , 122 )
                get = checkinters( l1S , l1E )
                IF get.x > -1 AND get.z > -1
                        mx = get.x
                        my = get.z
                ENDIF
                SHOWSCREEN
        WEND
ENDFUNCTION

FUNCTION checkinters AS coord: l1S AS coord , l1E AS coord
        LOCAL cPnt AS coord , temp AS coord , tempE AS coord , cpNear AS coord , smDist# AS float , iSm AS int , l1EO AS coord , l1SO AS coord
        l1SO = l1S
        l1EO = l1E
        FOR iG = 0 TO 1
                FOR i = 0 TO maxBox - 1
                        iSm = -1 ; smDist = 500000.0
                        IF box[i].exist = 1
                                FOR i2 = 0 TO 3
                                        IF i2 = 0
                                                temp.x = box[i].xl ; temp.z = box[i].zf ; tempE.x = box[i].xr ; tempE.z = box[i].zf // face along zfront ( 0 )
                                        ENDIF
                                        IF i2 = 1
                                                temp.x = box[i].xl ; temp.z = box[i].zf ; tempE.x = box[i].xl ; tempE.z = box[i].zb // face along xl     ( 1 )
                                        ENDIF
                                        IF i2 = 2
                                                temp.x = box[i].xr ; temp.z = box[i].zb ; tempE.x = box[i].xl ; tempE.z = box[i].zb // face along zb     ( 2 )
                                        ENDIF
                                        IF i2 = 3
                                                temp.x = box[i].xr ; temp.z = box[i].zb ; tempE.x = box[i].xr ; tempE.z = box[i].zf // face along xr     ( 3 )
                                        ENDIF
                                        cPnt = intersection( l1S , l1E , temp , tempE )
                                        IF cPnt.x > -1
                                                IF ( ( cPnt.x - l1SO.x ) * ( cPnt.x - l1SO.x ) + ( cPnt.z - l1SO.z ) * ( cPnt.z - l1SO.z ) ) < smDist
                                                        // also check if cut point is not between two near faces of different boxes
                                                        IF pointbetweenFaces( cPnt , i2 , i ) = 0
                                                                smDist = ( ( cPnt.x - l1S.x ) * ( cPnt.x - l1S.x ) + ( cPnt.z - l1S.z ) * ( cPnt.z - l1S.z ) ) ; cpNear = cPnt ; iSm = i2
                                                        ENDIF
                                                ENDIF
                                        ENDIF
                                NEXT
                                IF iSm = 0 THEN l1E.z = cpNear.z - 1.0
                                IF iSm = 2 THEN l1E.z = cpNear.z + 1.0
                                IF iSm = 1 THEN l1E.x = cpNear.x - 1.0
                                IF iSm = 3 THEN l1E.x = cpNear.x + 1.0
                        ENDIF
                NEXT
        NEXT
        RETURN l1E
ENDFUNCTION

FUNCTION pointbetweenFaces: point AS coord , side AS int , boxCh AS int
        LOCAL fChS AS coord , fChE AS coord , fTChS AS coord , fTChE AS coord
        IF side = 0
                fTChS.z = box[boxCh].zf
        ENDIF
        IF side = 1
                fTChS.x = box[boxCh].xl
        ENDIF
        IF side = 2
                fTChS.z = box[boxCh].zb
        ENDIF
        IF side = 3
                fTChS.x = box[boxCh].xr
        ENDIF
        fTChS.y = box[boxCh].yd ; fTChE.y = box[boxCh].yu
        FOR i = 0 TO maxBox - 1
                IF i <> boxCh AND box[i].exist = 1
                        IF side = 0 // get opposite face of another object to the checked faces direction
                                fChS.x = box[i].xl ; fChS.y = box[i].yd ; fChS.z = box[i].zb
                                fChE.x = box[i].xr ; fChE.y = box[i].yu ; fChE.z = box[i].zb
                        ENDIF
                        IF side = 1
                                fChS.x = box[i].xr ; fChS.y = box[i].yd ; fChS.z = box[i].zf
                                fChE.x = box[i].xr ; fChE.y = box[i].yu ; fChE.z = box[i].zb
                        ENDIF
                        IF side = 2
                                fChS.x = box[i].xl ; fChS.y = box[i].yd ; fChS.z = box[i].zf
                                fChE.x = box[i].xr ; fChE.y = box[i].yu ; fChE.z = box[i].zf
                        ENDIF
                        IF side = 3
                                fChS.x = box[i].xl ; fChS.y = box[i].yd ; fChS.z = box[i].zf
                                fChE.x = box[i].xl ; fChE.y = box[i].yu ; fChE.z = box[i].zb
                        ENDIF
                        IF side = 0 OR side = 2
                                IF ABS( fChS.z - fTChS.z ) <= 1.0
                                        IF point.x > fChS.x AND point.x < fChE.x AND point.y > fChS.y AND point.y < fChE.y
                                                RETURN 1
                                        ENDIF
                                ENDIF
                        ENDIF
                        IF side = 1 OR side = 3
                                IF ABS( fChS.x - fTChS.x ) <= 1.0
                                        IF point.z > fChS.z AND point.z < fChE.z AND point.y > fChS.y AND point.y < fChE.y
                                                RETURN 1
                                        ENDIF
                                ENDIF
                        ENDIF
                ENDIF
        NEXT
        RETURN 0
ENDFUNCTION


FUNCTION intersection AS coord: l1S AS coord , l1E AS coord , l2S AS coord , l2E AS coord
        LOCAL x1 AS float , y1 AS float , x2 AS float , y2 AS float , x3 AS float , y3 AS float , x4 AS float , y4 AS float  , d AS float , pre AS float
        LOCAL post AS float , x AS float , y AS float
        LOCAL fail AS coord , ret AS coord
        fail.x = -1 ; fail.z = -1 ; fail.y = -1 // assumes that coordinates are always positive values!
        x1 = l1S.x ; x2 = l1E.x ; x3 = l2S.x ; x4 = l2E.x
        y1 = l1S.z ; y2 = l1E.z ; y3 = l2S.z ; y4 = l2E.z
        d = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4)
        IF d = 0 THEN RETURN fail
        pre = (x1*y2 - y1*x2) ; post = (x3*y4 - y3*x4)
        x = ( pre * (x3 - x4) - (x1 - x2) * post ) / d
        y = ( pre * (y3 - y4) - (y1 - y2) * post ) / d
        IF ( x < MIN(x1, x2) OR x > MAX(x1, x2) OR x < MIN(x3, x4) OR x > MAX(x3, x4) ) THEN RETURN fail
        IF ( y < MIN(y1, y2) OR y > MAX(y1, y2) OR y < MIN(y3, y4) OR y > MAX(y3, y4) ) THEN RETURN fail
        ret.x = x ; ret.z = y
        RETURN ret
ENDFUNCTION

FUNCTION sortCube: i AS int
        IF box[i].xl > box[i].xr THEN SWAP box[i].xl , box[i].xr
        IF box[i].zf > box[i].zb THEN SWAP box[i].zf , box[i].zb
        IF box[i].yd > box[i].yu THEN SWAP box[i].yd , box[i].yu
ENDFUNCTION

FUNCTION DrawCube: i AS int
        DRAWLINE box[i].xl , box[i].zf , box[i].xr , box[i].zf , RGB( 122 , 255 , 55 + i * 20 )
        DRAWLINE box[i].xl , box[i].zf , box[i].xl , box[i].zb , RGB( 122 , 255 , 55 + i * 20 )
        DRAWLINE box[i].xr , box[i].zb , box[i].xl , box[i].zb , RGB( 122 , 255 , 55 + i * 20 )
        DRAWLINE box[i].xr , box[i].zb , box[i].xr , box[i].zf , RGB( 122 , 255 , 55 + i * 20 )
ENDFUNCTION
 

Added the Response handling in the Simulation for better testing.
« Last Edit: 2014-May-18 by nabz32 »

Offline nabz32

  • Community Developer
  • Dr. Type
  • ******
  • Posts: 305
    • View Profile
still won´t work when used in the 3D Environment with different updated coordinates through timer based movement. :(



Offline nabz32

  • Community Developer
  • Dr. Type
  • ******
  • Posts: 305
    • View Profile
Tested it more and it seems that it dosen´t like Floating Point movement values somehow...

When
Code: GLBasic [Select]
mx = mx + 3 -rnd(2)
no Problems at all.
But with
Code: GLBasic [Select]
mx = mx + 3 - rnd(20) * 0.1
I get random passthroughs through the walls.

Offline nabz32

  • Community Developer
  • Dr. Type
  • ******
  • Posts: 305
    • View Profile
I got everything working by casting the movement values to integer values before the calculation in the intersection function.

Based on this I wrote a 3D sliding collision routine for non rotated static boxes, that works great for jump and runs.

If anyone is interested, I will share the updated Routine too.

Offline Ian Price

  • Administrator
  • Prof. Inline
  • *******
  • Posts: 4094
  • On the shoulders of giants.
    • View Profile
    • My Apps
Please do share this with the community :)
I came. I saw. I played.

Offline erico

  • Community Developer
  • Prof. Inline
  • ******
  • Posts: 4057
    • View Profile
    • Portfolio
Yes please share!

Interesting read! I don´t have use for a function like that right now, but I´m sure it will come in handy in a future.
I also can´t comment much about it as the last time I tried a similar thing was back some 10 years on darkbasic, so that experience won´t help much.

Offline nabz32

  • Community Developer
  • Dr. Type
  • ******
  • Posts: 305
    • View Profile
sorry for being of for so Long,

I am going to write my tests at the beginning of the next month and I have gone all MU 0 Assembler since then.

The only Thing preventing me from sharing is a bug, where sometimes somehow my Offset values become the current coordinates.
I fixed this just by checking if the Offset values are to large, works on all the test, but because of this I was ashamed to post it, I will look at this closer when the Weekend sets in.

Basically it is to functions, one which holds X and Z in bounds and one for Y , I will also try to get everything into a single call.

Offline nabz32

  • Community Developer
  • Dr. Type
  • ******
  • Posts: 305
    • View Profile
As i cannot compact the code,
I am going to write a tutorial on how to get the box, cylindrical / sphere and diagonal collision going.
Maybe you guys can also point out some errors, so we can get this perfect.