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

Offline nabz32

  • Community Developer
  • Dr. Type
  • ******
  • Posts: 311
    • 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: 311
    • 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: 311
    • 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: 311
    • 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.1I get random passthroughs through the walls.

Offline nabz32

  • Community Developer
  • Dr. Type
  • ******
  • Posts: 311
    • 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: 4158
  • 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: 4329
    • View Profile
    • FUED
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: 311
    • 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: 311
    • 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.