2D - Circle to Line collision issue

Blitz3D Forums/Blitz3D Programming/2D - Circle to Line collision issue

necky(Posted 2013) [#1]
Hi everyone!

I've been working on some 2D line-to-circle collision system and it's been coming on quite well. BUT, I have hit a bit of an issue with it. If you run this code below in Blitz3D and move the collision circle to the top left it starts to really shake around. (use a joypad/controller's left analogue stick to move it around).

Now the issue seems to arise when the ball goes from one line to another, especially if the two lines are dramatically different in angles.

The big question is, does anyone know, looking at my code below, if there is a solution to this issue? And if so, how would you tackle it?

Maybe a question you could possibly answer Mr Sibly, as know you have a solution to this in 3D for your sphere to poly collision system? :)

Anyway, any help would be gratefully recieved :)

all the best!

Mike :)




Kryzon(Posted 2013) [#2]
Hi. A couple of comments.

1) Most people don't have a Joypad handy to test that code, so you should've changed it to keyboard control. That's what I did to test it here.
	playerX = playerX + ( KeyDown( 205 ) - KeyDown( 203 ) ) * 4
	playerY = PlayerY + ( KeyDown( 208 ) - Keydown( 200 ) ) * 4

2) The problem is happening because you're using a 'deterministic' approach, in that given a collision with a line, you are directly relocating the circle itself (by using that abstract position Collision_New_Position_n).
When the circle collides with a line, it is being relocated to a different position, and then it happens to collide with another line because of that. So this becomes a cycle which gives the flickering.

You should instead be handling only its motion vector, which indirectly relocates the circle. This is a more physics oriented approach.

The desired behavior is that at the nodes common to two line segments the circle stops. You achieve this by having each collision with a line 'contribute' towards stopping the circle - so you begin with a full length vector from the player controls moving the circle, then take that vector and at each collision with a line you reduce it given the orientation of the player in relation to the line, and so the vector accumulates resistances from collisions until it results in zero and the circle stops.

If the vector isn't zero (regardless if the circle collided or not, because it can slide along a line even when colliding), the circle should keep moving for that frame.


necky(Posted 2013) [#3]
Hi Kryzon!

This is terrific advice! :D Thank you so much! :D I'll take a look at this tomorrow night (I'm just off to bed).

thanks again!

Mike


necky(Posted 2013) [#4]
Righteo! I've rewritten my code and the results are WAY better than before. It still shudders a bit in the corners, but I think I know what this is :) The point though is Kryzon was spot on with his help, so thanks again!

Here's my code if anyone else is interested in doing this and a starting point :)



Thanks
Mike


necky(Posted 2013) [#5]
Hey!

Well, I've been plowing on with this and have made some good progress.

I've got the circle bouncing off the lines at the correct angle now, which is good. :)

But there's an issue (like always!) where the circle sometimes gets stuck and freaks out. If you run this code below you can see what I mean. The first time it hits the wall it sticks to it before wiggling itself free. When it does it then continues to behave correctly, but can still become stuck again under the correct conditions.

From what I can tell it doesn't look happy when it collides with two lines at once.

Can anyone help me out here as I really can't figure out how to fix this. :/

Thanks in advance :)

Mike


;****************
;* 2d Collision *
;****************

Graphics 800,600,32,2

SetBuffer BackBuffer()

Global lineAx#	= 300
Global lineAy#	= 300

Global lineBx#	= 400
Global lineBy#	= 100

;-----------------------------------

Type COLLISION_LINE

	Field Collision_Line_vertA_PosX#
	Field Collision_Line_vertA_PosY#

	Field Collision_Line_vertB_PosX#
	Field Collision_Line_vertB_PosY#

End Type

;-----------------------------------

Global circleX# = 450
Global circleY# = 200

Global radius#	= 32

Global PlayerVelocityX# = 1 ;.5
Global PlayerVelocityY# = 1 ;.5

Global PlayerSpeed#		= 1

Global PlayerVelocityDamping# = 0.75

Global velocityX# 			; these are related exclusively to the circle_to_line_collision() function 
Global velocityY#			;
Global collisionFinished    ;

;-----------------------------------

Create_Collision_Line(174.0, 83.0, 88, 192)
Create_Collision_Line(88.0, 192.0, 69, 303)
Create_Collision_Line(69.0, 303.0, 121, 399)
Create_Collision_Line(121.0, 399.0, 207, 394)
Create_Collision_Line(207.0, 394.0, 265, 341)
Create_Collision_Line(265.0, 341.0, 323, 304)
Create_Collision_Line(323.0, 304.0, 383, 308)
Create_Collision_Line(383.0, 308.0, 456, 357)
Create_Collision_Line(456.0, 357.0, 490, 427)
Create_Collision_Line(490.0, 427.0, 541, 482)
Create_Collision_Line(541.0, 482.0, 645, 489)
Create_Collision_Line(645.0, 489.0, 711, 423)
Create_Collision_Line(711.0, 423.0, 735, 344)
Create_Collision_Line(735.0, 344.0, 748, 236)
Create_Collision_Line(748.0, 236.0, 701, 185)
Create_Collision_Line(701.0, 185.0, 670, 134)
Create_Collision_Line(670.0, 134.0, 685, 69)
Create_Collision_Line(685.0, 69.0, 640, 29)
Create_Collision_Line(640.0, 29.0, 517, 32)
Create_Collision_Line(517.0, 32.0, 430, 76)
Create_Collision_Line(430.0, 76.0, 378, 109)
Create_Collision_Line(378.0, 109.0, 293, 101)
Create_Collision_Line(293.0, 101.0, 247, 57)
Create_Collision_Line(247.0, 57.0, 165, 87)

;********
;* MAIN *
;********

While KeyDown(1)=0

Cls

Draw_Collision_Lines()
updatePlayerVelocity()

t = 0
While t<360
	Plot circleX#+Sin(t)*radius#, circleY#+Cos(t)*radius#
	t=t+1
Wend

Flip

Wend

;*************************
;* Create Collision Line *
;*************************

Function Create_Collision_Line(xa#,ya#,xb#,yb#)

level.COLLISION_LINE = New COLLISION_LINE

	level\Collision_Line_vertA_PosX#	= xb#
	level\Collision_Line_vertA_PosY#	= yb#

	level\Collision_Line_vertB_PosX#	= xa#
	level\Collision_Line_vertB_PosY#	= ya#

End Function

;************************
;* Draw Collision Lines *
;************************

Function Draw_Collision_Lines()

For level.COLLISION_LINE = Each COLLISION_LINE

	Line level\Collision_Line_vertA_PosX#,level\Collision_Line_vertA_PosY#, level\Collision_Line_vertB_PosX#,level\Collision_Line_vertB_PosY#
	
Next

End Function

;**************************
;* Update Player Velocity *
;**************************

Function updatePlayerVelocity()

;If KeyDown(203)=1 Then PlayerVelocityX# = -1
;If KeyDown(205)=1 Then PlayerVelocityX# = 1
;If KeyDown(200)=1 Then PlayerVelocityY# = -1
;If KeyDown(208)=1 Then PlayerVelocityY# = 1

If Not JoyX()>-0.1 And JoyX()<0.1

	If collisionFinished =0
		PlayerVelocityX# = (JoyX()*PlayerSpeed#)											; moving the 'player' around with the joypad (left analogue stick)
	EndIf
	
EndIf


If Not JoyY()>-0.1 And JoyY()<0.1

	If collisionFinished =0
		PlayerVelocityY# = (JoyY()*PlayerSpeed#)											; moving the 'player' around with the joypad (left analogue stick)
	EndIf
	
EndIf

;---Check collision ----

velocityX# = PlayerVelocityX#
velocityY# = PlayerVelocityY#

g=0	

collisionFinished = 0 

For level.COLLISION_LINE = Each COLLISION_LINE

	If collisionFinished = 0

		circle_To_Line_Collision(level\Collision_Line_vertA_PosX#,level\Collision_Line_vertA_PosY#, level\Collision_Line_vertB_PosX#,level\Collision_Line_vertB_PosY#, circleX#, circleY#, radius#, PlayerVelocityX#, PlayerVelocityY# )
		PlayerVelocityX# = velocityX#
		PlayerVelocityY# = velocityY#
		
	EndIf
		

Next

PlayerVelocityX# = velocityX#
PlayerVelocityY# = velocityY#

circleX# = circleX# + PlayerVelocityX#
circleY# = circleY# + PlayerVelocityY#

;-- Apply Damping ------

;PlayerVelocityX# = PlayerVelocityX# * PlayerVelocityDamping# 
;PlayerVelocityY# = PlayerVelocityY# * PlayerVelocityDamping# 

End Function

;****************************
;* Circle to line collision *
;****************************

Function circle_To_Line_Collision(ax#, ay#, bx#, by# ,cx#, cy# ,cr#, velox#, veloy#)

; pvx# & pvy# = player velocity

velocityX# = velox#
velocityY# = veloy#

vx# = bx# - ax#
vy# = by# - ay#

xdiff# = ax# - cx#
ydiff# = ay# - cy#

a# = (vx#*vx#) + (vy# * vy#)
b# = 2*( (vx#*xdiff#) + (vy# * ydiff#) )  
c# = (xdiff#*xdiff#) + (ydiff# * ydiff#) - (cr#*cr#)

quad# = (b#*b#) - (4*a#*c#)

lineAngle# = ATan2 (vx#,vy#); + 90

Color 255,255,255
;Line ax#,ay#,ax#+(Sin(lineAngle#)*40), ay#+(Cos(lineAngle#)*40)		

Color 0,255,0
Rect ax#,ay#,4,4
Color 255,255,255

If (quad# >0 Or quad# = 0)

	quadsqrt# = Sqr(quad#) 
i= -1

	For i = -1 To 1
	
		t# = (i*-b# + quadsqrt#) / (2*a#)
		
		x# = ax# + (i * vx# * t#)			; x# & y# are the collision coordinates
		y# = ay# + (i * vy# * t#)
	
		If x# > min#(ax#,bx#) Or x# = min#(ax#,bx#) And x# < max#(ax#, bx#) Or x# = max#(ax#, bx#) And y# > min#(ay#,by#) Or y# = min#(ay#,by#) And y# < max#(ay#,by#) Or y# = max#(ay#,by#) 

			Rect x#,y#,6,6

			impactLineX#= (x#-cx#)
			impactLineY#= (y#-cy#)
		
			impactAngle# = ATan2(velox#,veloy#)
			impactAngle# = -impactAngle#+(lineAngle# *2 )
		
;			Color 255,0,255
;			Line ax#,ay#,ax#+(Sin(impactAngle#)*40), ay#+(Cos(impactAngle#)*40)		

			velocityX# = Sin(impactAngle#)*3
			velocityY# = Cos(impactAngle#)*3
			
			collisionFinished = collisionFinished + 1
									
			Return True	
			
		End If

		i=i+2

	Next
	
	Return False

EndIf

End Function 

;**********************
;* Min value function *
;**********************

Function min#(a#,b#)

	If a#<b#
	
		Return a#
	Else
	
		Return b#
	
	EndIf

End Function


;**********************
;* Max value function *
;**********************

Function max#(a#,b#)

	If a#>b#
	
		Return a#
	Else
	
		Return b#
	
	EndIf

End Function




Stevie G(Posted 2013) [#6]
I think your collision routine is seriously flawed. You are not resolving penetration and you are handling velocity incorrectly.

For penetration you should be moving the ball away from the collision by it's penetration depth + .0001 (or some small factor to ensure it's no longer colliding with the line) in the direction of the line normal. The velocity should be correctly reflected based on the collision normals. This should be done for every circle line collision, not just with the last collision.

By not resolving the penetration and correctly handling the velocity, any collisions with multiple lines will keep changing the velocity causing this back and forward jittering.


Floyd(Posted 2013) [#7]
That's essentially what I was going to say. Sometimes the circle passes through a line segment, which must never happen. You must move the circle back so it is no longer colliding. Figure out the appropriate movement to put it back so it is exactly colliding, then multiply that amount by a small "fudge factor" such as 1.0001 so it is no longer colliding.

Determining the response based on line angles is doomed to fail at the endpoints. When the circle hits something the response is entirely determined by the point of impact. You can do this based on the "collision normal". That's usually a vector perpendicular to the thing the circle collided with. But for an endpoint this is not well defined.

However, since the moving object is a circle we know the normal must be directed from the impact point toward the center of the circle.


Kryzon(Posted 2013) [#8]
I suggest you change your paradigm to vectors entirely.
It's much easier than using trigonometry.

I used this article as reference:
http://doswa.com/2009/07/13/circle-segment-intersectioncollision.html

Then I coded something.
It's not perfect. At all node junctions the circle jitters around.




necky(Posted 2013) [#9]
Hi Kryzon!
This is terrific! Thank you! :D Thanks again for all your help, you've been brilliant!

all the best!
Mike


Kryzon(Posted 2013) [#10]
Hi. As it was, the collision function would check for collisions based on the same "future position" from the player.
But when colliding against several lines at once, this has them all correcting against the exact same old position.

So every time a collision is detected you need to update the "future position" with these corrections - this means each line will give corrections consecutively, based on each other's corrections. It further improves against the jittering; It's still not perfect but it's much better.

In the CheckCollisions function, add two lines in this block:
		If closestLength < ( Player\radius ) Then
			
			Player\numCollisions = Player\numCollisions + 1
						
			closestDirX = (newPlayerX - closestPointX) / closestLength
			closestDirY = (newPlayerY - closestPointY) / closestLength
				
			penetrationX = ( Player\radius - closestLength ) * closestDirX
			penetrationY = ( Player\radius - closestLength ) * closestDirY 
				
			Player\motionVecX = Player\motionVecX + Int( penetrationX )
			Player\motionVecY = Player\motionVecY + Int( penetrationY )
			
			;Update the future position being tested with the corrections from each collision.
			newPlayerX = Player\x + Player\motionVecX ;*** Added.
			newPlayerY = Player\y + Player\motionVecY ;*** Added.			

		EndIf