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

#### nabz32

• Community Developer
• Dr. Type
• Posts: 318
##### My take on sliding non tile based rectangle collision
« on: 2014-May-16 »
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 = 5TYPE coord x AS float y AS float z AS floatENDTYPETYPE 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 intENDTYPEGLOBAL box[] AS cBoxdrawSimulation()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 WENDENDFUNCTIONFUNCTION 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 l1EENDFUNCTIONFUNCTION 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 0ENDFUNCTIONFUNCTION 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 retENDFUNCTIONFUNCTION 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].yuENDFUNCTIONFUNCTION 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.

#### nabz32

• Community Developer
• Dr. Type
• Posts: 318
##### Re: My take on sliding non tile based rectangle collision
« Reply #1 on: 2014-May-16 »
A modified Version that seems to work
if the coordinates are always positive.

Code: (glbasic) [Select]
`CONSTANT maxBox = 5TYPE coord x AS float y AS float z AS floatENDTYPETYPE 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 intENDTYPEGLOBAL box[] AS cBoxdrawSimulation()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 WENDENDFUNCTIONFUNCTION 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 l1EENDFUNCTIONFUNCTION 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 0ENDFUNCTIONFUNCTION 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 retENDFUNCTIONFUNCTION 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].yuENDFUNCTIONFUNCTION 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 »

#### nabz32

• Community Developer
• Dr. Type
• Posts: 318
##### Re: My take on sliding non tile based rectangle collision
« Reply #2 on: 2014-May-16 »
still won´t work when used in the 3D Environment with different updated coordinates through timer based movement.

#### nabz32

• Community Developer
• Dr. Type
• Posts: 318
##### Re: My take on sliding non tile based rectangle collision
« Reply #3 on: 2014-May-18 »
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.

#### nabz32

• Community Developer
• Dr. Type
• Posts: 318
##### Re: My take on sliding non tile based rectangle collision
« Reply #4 on: 2014-May-24 »
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.

#### Ian Price

• Administrator
• Prof. Inline
• Posts: 4159
• On the shoulders of giants.
##### Re: My take on sliding non tile based rectangle collision
« Reply #5 on: 2014-May-24 »
Please do share this with the community
I came. I saw. I played.

#### erico

• Community Developer
• Prof. Inline
• Posts: 4396
##### Re: My take on sliding non tile based rectangle collision
« Reply #6 on: 2014-May-25 »
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.

#### nabz32

• Community Developer
• Dr. Type
• Posts: 318
##### Re: My take on sliding non tile based rectangle collision
« Reply #7 on: 2014-Jun-12 »
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.

#### nabz32

• Community Developer
• Dr. Type
• Posts: 318
##### Re: My take on sliding non tile based rectangle collision
« Reply #8 on: 2014-Sep-01 »
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.