rigz.collision - need some help plz

BlitzMax Forums/BlitzMax Programming/rigz.collision - need some help plz

Rick_72

(Posted 2010) [#1]

Hi all,

using the pretty cool rigz.collision I have some issue with a collision detection. It doesn't work as I expect it to. Here's some code:

Type TPlayer Extends TGameObject
		
	Field _verts:Float[] = [0.0, 0.0, 10.0, 0.0, 10.0, 10.0, 0.0, 10.0]
	Field _poly:tlPolygon = CreatePolygon(50, 50, _verts)

	Method Update()
		If KeyDown(KEY_LEFT) Turn(-4)
		If KeyDown(KEY_RIGHT) Turn(+ 4)
		If KeyDown(KEY_UP) 
			SpeedUp()
		Else If KeyDown(Key_DOWN)
		 	SpeedDown()
		Else 
			break()
		End If	
'		If KeyDown(KEY_SPACE) Shoot()

	End Method	

	Method PlayerMove(_tree:tlQuadTree)

		_x = Cos(_angle) * _speed
		_y = Sin(_angle) * _speed
		_poly.SetVelocity(_x, _y)
		
		QueryQuadtreeBox(_tree, _poly, _poly, BouncePlayer)
		
		_poly.Move(_poly.velocity.x, _poly.velocity.y)
		_poly.SetAngle(_angle)
		
	End Method
		
	Function BouncePlayer(o:Object, data:Object)

		Local _poly:tlPolygon = tlPolygon(data)
		Local _wall:tlLine = tlLine(o)
		
		Local result:tlCollisionResult = CheckCollision(_poly, _wall)
		PreventOverlap(result)
		
	End Function

..

End Type


Type TGameField

	Field x:Float, y:Float, w:Float, h:Float
	Field Tree:tlQuadTree

	
        Method CreateTree()
		Self.Tree = CreateQuadtree(Self.x, Self.y, Self.w, Self.h)
	
	End Method

	
	Method CreateField(x:Float, y:Float, w:Float, h:Float)
		Self.x = x
		Self.y = y
		Self.w = w
		Self.h = h
		
		CreateTree()
		CreateBoundaries()
	End Method
	
	
	Method CreateBoundaries()
		AddBoundaryToQuadtree(Tree, CreateLine(Self.x, Self.y, Self.x + Self.w, Self.y))
		AddBoundaryToQuadtree(Tree, CreateLine(Self.x + Self.w, Self.y, Self.x + Self.w, Self.y + Self.h))
		AddBoundaryToQuadtree(Tree, CreateLine(Self.x + Self.w, Self.y + Self.h, Self.x, Self.y + Self.h))
		AddBoundaryToQuadtree(Tree, CreateLine(Self.x, Self.y + Self.h, Self.x, Self.y))
		
	End Method

..

End Type

..

Repeat

	Cls
	
	GameField.DrawGameField()
	

	Player.Update()
	Player.PlayerMove(qTree)

	Player.DrawPlayer()

	
	Flip
	
Until KeyHit(KEY_ESCAPE)

The .. (dots) just represent that there's more code that I didn't show up since it would confuse and overload the topic.

Some explanations:
- Type TPlayer: Method Turn() simply alters _angle as well as SpeedUp() and SpeedDown() alter _speed
- Type TGameField: nothing more than 4 lines added to a QuadTree

Now the issue with this code is that I can fly through the boundary (lines) if _poly is small enough (as you see _poly is now a square of 10 px. width). If the square is next to a boundary line the collision detection works without issues unless I turn the square. Doing so the square slips through the boundary.

Using a circle instead of a square does not show this behaviour.

Can anyone help?

Pete Rigz

(Posted 2010) [#2]

My first guess is that this is due to tunnelling, whereby if the objects speed is faster then its size then it can skip over objects that are also small (such as a line), however that may not be the case here as you say it works ok with a circle.

If it is tunnelling then a common approach to avoid this is to simply take this into account with level design by using thicker walls and boundaries, alternatively you can increase your logic rate so that your game runs faster and collision checks are made more often between frames.

If it's essential that you need to avoid tunnelling then a full blown physics system may be in order such as box2d which (I believe) uses a technique called sweeping to avoid this, but that may be overkill depending on your needs.

If you can post a small example code with the problem I can check there are no other bugs lurking :)

Jesse

(Posted 2010) [#3]

the problem with flying over the boundaries is because you are moving too many pixels at once, if you are moving at more thant ten pixels at a time. try to check collision every 5 pixels or any number less than the size of the square.
the other problem I am thinking is because you are using one of the corners for rotation and not the center instead of using 0 and 10 for vertices use -5 and 5. this should rotate the poly around the center not a corner. vertices should be [-5,-5, 5,-5, 5,5, -5,5]

Rick_72

(Posted 2010) [#4]

Thanks for your help, guys!

@Pete: I tried to avoid too big steps (per frame) by setting a speed limit. In this case is was set to 4 px. (the moving box: edge length = 10px). So the box can not move more than 4 px. per frame. The distance between centre (of the box) and boundary (of the box) is 5 px. Should work. Increasing the box size does not work allways.

When the box slides along the boundaries (at some shallow angle) it kind of dips into it. As far as I have understood your module code it shouldn't do so. Before I move the box (_poly.move() ) I use PreventOverlap() that sets back (in case of overlapping) the box using translationVector (which represents the amount of overlapping). TranslationVector is calculated using the polygon's velocity-vector. Both should be equal in case of a collision so that in the end the polygon isn't moved at all. But the dipping indicates that those vectors are somehow not equal. Any ideas? Or maybe I misunderstood the basics of your module. Any comment is appreciated. :-)

@Jesse: the rotation works fine. Rigz module automatically centers the polygon.

Rick_72

(Posted 2010) [#5]

@Pete: I have just found out that translationVec does *not* equal velocityVec. So this explains what happens within my code:
PreventOverLap() moves the box back using translationVec which is the minimum distance to seperate line and box. Next I move the box (_poly.move) using its velocityVec. Since the abs. value of velocityVec. is higher than the abs. val. of translationVec. the box 'dips' into the boundary. That reduces the safety margin (max. speed) so the box might tunnel the line within the next frame.

Best solution? Avoid using velocityVec. to move the polygon after a collision? Using thicker boxes instead of lines as boundary? Both might work. What do you suggest?

Pete Rigz

(Posted 2010) [#6]

Ahh I see now. Yes I think you just need change the order that you update your poly. I think you should move stuff first, then check for collisions for best results, so try:

	Method PlayerMove(_tree:tlQuadTree)

		_x = Cos(_angle) * _speed
		_y = Sin(_angle) * _speed
		_poly.SetVelocity(_x, _y)

		_poly.Move(_poly.velocity.x, _poly.velocity.y)
		_poly.SetAngle(_angle)
		
		QueryQuadtreeBox(_tree, _poly, _poly, BouncePlayer)
		
	End Method

Rick_72

(Posted 2010) [#7]

No, this results in tunneling. I have to check first for collisions and decide afterwards wether to move forward or not.

Another thing is that I want to avoid the box from sticking to the wall. If it slides along the wall in some angle it sticks to it. The best way might be to get the target boundary by calling GetTargetBoundary. Then I have turn the box velocityVec until its parallel to the boundary. Any other idea is welcome!

Is there a simple way to get the boundary as a vector?

I guess I have to do some more research on the way your code works.

Pete Rigz

(Posted 2010) [#8]

Oh yeh, my memory isn't working too good :) It should go after you're right. I made this quick test with the same size box and a line, and as long as the maximum speed is no more then 5 I can't get it to tunnel, and it seems to be behaving ok. I can't immediately see what the difference with your code is though, except I didn't bother with a quadtree - that shouldn't make a difference though.

SuperStrict

Import rigz.collision

Graphics 800, 600

'a local collision result to store the result of the collision test
Local result:tlCollisionResult = New tlCollisionResult

'some velocity vectors to move the box about
Local VelVector:tlVector2 = CreateVector2(0, 0)
Local Direction:Float = 180
Local speed:Float = 5
Local velocity:Float

Local _verts:Float[] = [0.0, 0.0, 10.0, 0.0, 10.0, 10.0, 0.0, 10.0]
Local box:tlPolygon = CreatePolygon(50, 50, _verts)
Local line:tlLine = CreateLine(600, 10, 600, 500)

While Not KeyDown(KEY_ESCAPE)
	
	Cls
	
	'some basic movement controls for the box
	If KeyDown(KEY_RIGHT) direction:+4
	If KeyDown(KEY_LEFT) direction:-4
	If KeyDown(KEY_UP) Or KeyDown(KEY_DOWN)
		velocity = -speed
	Else
		velocity = 0
	End If
	velvector.SetPosition(Cos(direction), Sin(direction))
	'set the box velocity so that the collision check can see whether the 2 objects will collide
	'the next frame. You don't *have* to do this, but it makes for more accurate collisions
	box.velocity = velvector.Scale(velocity)

	'check for a collision with the poly
	result = CheckCollision(box, line)
	
	'prevent the box from overlapping the poly
	PreventOverlap(result)
	
	'move the box. Important to do this after the collision check, but only if you're setting
	'the box velicity.
	box.Move(box.velocity.x, box.velocity.y)
	box.SetAngle(direction)
	
	box.draw()
	line.draw()
	
	Flip
	
Wend

Does your game object have it's own set of coordinates separate from the collision box? If so are you updating it's coordinates after an overlap has been prevented? That can cause problems if the game object coordinates are not synchronised properly with the collision box.

Rick_72

(Posted 2010) [#9]

Pete, I think I've found out what happens. Have a look at this code, plz:


SuperStrict

Import rigz.collision

Graphics 800, 600

'a local collision result to store the result of the collision test
Local result:tlCollisionResult = New tlCollisionResult

'some velocity vectors to move the box about
Local VelVector:tlVector2 = CreateVector2(0, 0)
Local Direction:Float = 180
Local speed:Float = 5
Local velocity:Float

Local _verts:Float[] = [0.0, 0.0, 10.0, 0.0, 10.0, 10.0, 0.0, 10.0]
Local box:tlPolygon = CreatePolygon(50, 50, _verts)

Local Tree:tlQuadTree = CreateQuadtree(0, 0, 800, 600)
AddBoundaryToQuadtree(Tree, CreateLine(600, 10, 600, 500))



While Not KeyDown(KEY_ESCAPE)
	
	Cls

	If KeyDown(KEY_RIGHT) direction:+4
	If KeyDown(KEY_LEFT) direction:-4
	If KeyDown(KEY_UP) Or KeyDown(KEY_DOWN)
		velocity = -speed
	Else
		velocity = 0
	End If

	velvector.SetPosition(Cos(direction), Sin(direction))
	box.velocity = VelVector.Scale(velocity)

'***OPTION 1****
	'Query box area results in tunneling	
	'QueryQuadtreeBox(Tree, box, box, HandleCollision)
	
'***OPTION 2****
	'Query a wider area works fine
	QueryQuadtreeArea(Tree, box.world.x-10, box.world.y-10, 20, 20, box, HandleCollision)
	
	box.Move(box.velocity.x, box.velocity.y)
	box.SetAngle(Direction)
	
	box.draw()
	QueryQuadtreeArea(Tree, 0,0,800,600, Null, RenderTree)

	Flip
	
Wend

Function HandleCollision(o:Object, data:Object)

	Local _box:tlBox = tlBox(data)
	Local _line:tlLine = tlLine(o)
	
	Local result:tlCollisionResult = CheckCollision(_box, _line)
	PreventOverlap(result)
	
End Function

Function RenderTree(o:Object, data:Object)
	Local box:tlBox = tlBox(o)
	box.draw()
End Function

Option 1 works if speed is low enough. If speed's too high and the box is located right next to the line no collision is detected. Within the next frame the box tunnels the line.

Option 2 works better since the area to check is wider. If the area is bigger than the max. boundaries of the box plus the max pixel movement (amx. speed) all possible collisions (within the next frame) are predicted before they actually happen.

Pete Rigz

(Posted 2010) [#10]

Thanks for the example. I found the problem and it was because of the quadtree. It wasn't taking into account the velocity when collision checking objects found in the quadtree. I've committed the changes to SVN so hopefully that fixes it :)

Rick_72

(Posted 2010) [#11]

OK, cool, thanks for that!