Need Math Help - Sliding on a Line

BlitzMax Forums/BlitzMax Programming/Need Math Help - Sliding on a Line

AndrewT(Posted 2009) [#1]
So I'm trying to create a sliding collision system for a 2D top-down game. Basically I have a bunch of lines representing walls, and I've got a point representing the player. When the player hits a wall on an angle I want him to slide along the wall rather than just stick. So it seemed fairly straightforward at first. I have a good idea of what I need to do, but I'm having some trouble implementing it.

Since I'm terrible at explaining things like this, I'll post a little diagram I made to represent what I'm trying to do:



And here is the my current code:

SuperStrict

Type TPoint
	Field X:Float
	Field Y:Float
	Function Create:TPoint(X:Float, Y:Float)
		Local Point:TPoint = New TPoint
		Point.X = X
		Point.Y = Y
		Return Point
	EndFunction
EndType

Type TLine
	Field P1:TPoint
	Field P2:TPoint
	Method New()
		P1 = New TPoint
		P2 = New TPoint
	EndMethod
	Function Create:TLine(X1:Float, Y1:Float, X2:Float, Y2:Float)
		Local Line:TLine = New TLine
		
		Line.P1.X = X1
		Line.P1.Y = Y1
		Line.P2.X = X2
		Line.P2.Y = Y2
		
		Return Line
	EndFunction
EndType

Graphics(1024, 768, 1)

Global g_ColPoint:TPoint = New TPoint

Local LineList:TList = CreateList()

LineList.AddLast(TLine.Create(100, 100, 200, 300))
LineList.AddLast(TLine.Create(300, 150, 400, 600))

Local PlayerPos:TPoint = New TPoint
PlayerPos.X = 50
PlayerPos.Y = 50
Local PlayerOldPos:TPoint = New TPoint
Local ColPoint:TPoint = New TPoint

Repeat

	Cls
	
	PlayerOldPos.X = PlayerPos.X
	PlayerOldPos.Y = PlayerPos.Y
	
	If KeyDown(KEY_UP)
		PlayerPos.Y = PlayerPos.Y - 4.0
	EndIf
	
	If KeyDown(KEY_DOWN)
		PlayerPos.Y = PlayerPos.Y + 4.0
	EndIf

	If KeyDown(KEY_LEFT)
		PlayerPos.X = PlayerPos.X - 4.0
	EndIf
	
	If KeyDown(KEY_RIGHT)
		PlayerPos.X = PlayerPos.X + 4.0
	EndIf
	
	For Local L:TLine = EachIn LineList
	
		If LineIntersection(PlayerOldPos.X, PlayerOldPos.Y, PlayerPos.X, PlayerPos.Y, L.P1.X, L.P1.Y, L.P2.X, L.P2.Y)
		
			PlayerOldPos.X = PlayerOldPos.X - (PlayerPos.X - PlayerOldPos.X)
			PlayerOldPos.Y = PlayerOldPos.Y - (PlayerPos.Y - PlayerOldPos.Y)
			
			Local BackPoint:TPoint = New TPoint
			
			BackPoint.X = g_ColPoint.X + (PlayerPos.X - PlayerOldPos.X)
			BackPoint.Y = g_ColPoint.Y + (PlayerPos.Y - PlayerOldPos.Y)
			
			Local Slope:Float
			
			Slope = (L.P2.Y - L.P1.Y) / (L.P2.X - L.P1.X)
			
			Slope = -(1 / Slope)
			
			Local Ang:Float = ATan(Slope)
			
			Local NewPoint:TPoint = New TPoint
			
			NewPoint.X = BackPoint.X + Sin(Ang) * 6.0
			NewPoint.Y = BackPoint.Y + Cos(Ang) * 6.0
			
			PlayerPos.X = NewPoint.X
			PlayerPos.Y = NewPoint.Y
			
			Exit
		
		EndIf
	
	Next
	
	DrawRect(PlayerPos.X - 2, PlayerPos.Y - 2, 4, 4)
	
	DrawLineList(LineList)

	Flip
	
Until KeyHit(KEY_ESCAPE)

Function DrawLineList(List:TList)

	For Local L:TLine = EachIn List
	
		DrawLine(L.P1.X, L.P1.Y, L.P2.X, L.P2.Y)
		
	Next
	
EndFunction

Function LineIntersection:Int(XS1:Int, YS1:Int, XE1:Int, YE1:Int, XS2:Int, YS2:Int, XE2:Int, YE2:Int)

	Local XT1:Int
	Local YT1:Int
	Local XT2:Int
	Local YT2:Int

	If XS1 = XE1 Then XE1 = XS1 + 1
	If XS2 = XE2 Then XE2 = XS2 + 1
	
	Local xdif1:Float= XE1 - XS1
	Local ydif1:Float = YE1 - YS1

	Local m1:Float = ydif1 / xdif1
	Local b1:Float = YS1 - XS1 * m1

	Local xdif2:Float = (XE2-XS2)
      Local ydif2:Float = (YE2-YS2)
	
	Local m2:Float = ydif2 / xdif2
	Local b2:Float = YS2 - XS2 * m2
	
	Local x:Float = (b2 - b1) / (m1 - m2)
	g_ColPoint.X = x
	
	Local y:Float = m1 * x + b1
	g_ColPoint.Y = y
	
	If XS1 > XE1 
		XT1 = XS1
		XS1 = XE1
		XE1 = XT1
	EndIf
	If YS1 > YE1
		YT1 = YS1
		YS1 = YE1
		YE1 = YT1
	EndIf
	If XS2 > XE2
		XT2 = XS2
		XS2 = XE2
		XE2 = XT2
	EndIf
	If YS2 > YE2
		YT2 = YS2
		YS2 = YE2
		YE2 = YT2
	EndIf

	If x => XS1
		If x <= XE1
			If x => XS2
				If x <= XE2
					If y => YS1
						If y <= YE1
							If y => YS2
								If y <= YE2
									Return 1
								EndIf
							EndIf
						EndIf
					EndIf
				EndIf
			EndIf
		EndIf
	EndIf

	Return 0
	
EndFunction


You control the little box with the arrow keys. If you run that you'll notice that the box only slides along with line if it is going directly up into the line. If it's moving down, horizontally, or diagonally it goes right through it.

Any help is appreciated.


Warpy(Posted 2009) [#2]
I've written this out about five times I think on this forum, so the answer you want is in the archives somewhere. If you can wait until I get back from France on Thursday I'll do a write-up on my blog.

Your line intersection function is either wrong or not as simple as it could be, so google that, and to get a sliding effect you need to project the object's velocity vector onto the line it's colliding with, which you can also find on google.


Warpy(Posted 2009) [#3]
ah! Knew I'd find it: here


AndrewT(Posted 2009) [#4]
Thanks very much, I've actually come up with a different method, using a circle instead of just a point for the player. Basically I check the distance from the center of the circle to each line segment, and if that distance is less than the circle's radius then it's colliding. If it's colliding then I change the velocity vector of the circle to be parallel with the line, then I multiply the velocity vector by the cosine of the difference between the angle of the line and the angle of the player, and this slows down the player depending on how directly he's facing the wall.

Once again I'm pretty bad at explaining so I'll post my new code and you can take a look at it.

SuperStrict

Type TPoint
	Field X:Float
	Field Y:Float
	Function Create:TPoint(X:Float, Y:Float)
		Local Point:TPoint = New TPoint
		Point.X = X
		Point.Y = Y
		Return Point
	EndFunction
EndType

Type TLine
	Field P1:TPoint
	Field P2:TPoint
	Method New()
		P1 = New TPoint
		P2 = New TPoint
	EndMethod
	Function Create:TLine(X1:Float, Y1:Float, X2:Float, Y2:Float)
		Local Line:TLine = New TLine
		
		Line.P1.X = X1
		Line.P1.Y = Y1
		Line.P2.X = X2
		Line.P2.Y = Y2
		
		Return Line
	EndFunction
EndType

Graphics(1024, 768, 1)

Global g_ColPoint:TPoint = New TPoint
Global g_IntersectPoint:TPoint = New TPoint

Local LineList:TList = CreateList()

LineList.AddLast(TLine.Create(100, 100, 500, 100))
LineList.AddLast(TLine.Create(500, 100, 500, 500))
LineList.AddLast(TLine.Create(250, 100, 250, 500))

Local PlayerPos:TPoint = New TPoint
PlayerPos.X = 350
PlayerPos.Y = 250
Local PlayerVel:TPoint = New TPoint
Local PlayerOldPos:TPoint = New TPoint
Local PlayerRadius:Float = 8.0
Local PlayerAng:Float = 0.0
Local ColPoint:TPoint = New TPoint

Repeat

	Cls
	
	DrawText("Control the circle with the arrowkeys - UP = Move forward - DOWN = Move backward - RIGHT = Turn right - LEFT = Turn left", 10, 10)
	
	PlayerOldPos.X = PlayerPos.X
	PlayerOldPos.Y = PlayerPos.Y
	
	PlayerVel.X = 0.0
	PlayerVel.Y = 0.0
	
	If KeyDown(KEY_UP)
		PlayerVel.X = Sin(PlayerAng) * 4.0
		PlayerVel.Y = Cos(PlayerAng) * 4.0
	EndIf
	If KeyDown(KEY_LEFT)
		PlayerAng = PlayerAng + 4.0
	EndIf
	If KeyDown(KEY_RIGHT)
		PlayerAng = PlayerAng - 4.0
	EndIf
	If KeyDown(KEY_DOWN)
		PlayerVel.X = -Sin(PlayerAng) * 4.0
		PlayerVel.Y = -Cos(PlayerAng) * 4.0
	EndIf		
	
	For Local L:TLine = EachIn LineList
	
		If DistanceToLineSegment(L.P1.X, L.P1.Y, L.P2.X, L.P2.Y, PlayerPos.X + PlayerVel.X, PlayerPos.Y + PlayerVel.Y) <= PlayerRadius
					
			Local LineAng:Float
			Local PlayerAng:Float
			Local AngDif:Float
			
			LineAng = ATan((L.P2.Y - L.P1.Y) / (L.P2.X - L.P1.X))
			PlayerAng = ATan(PlayerVel.Y / PlayerVel.X)
			AngDif = PlayerAng - LineAng
			
			If PlayerVel.X > 0.0
			
				PlayerVel.X = Cos(LineAng) * 4.0 * Cos(AngDif)
				PlayerVel.Y = Sin(LineAng) * 4.0 * Cos(AngDif)
			
			Else
			
				PlayerVel.X = Cos(LineAng) * 4.0 * -Cos(AngDif)
				PlayerVel.Y = Sin(LineAng) * 4.0 * -Cos(AngDif)
				
			EndIf
		
		EndIf
	
	Next
	
	PlayerPos.X = PlayerPos.X + PlayerVel.X
	PlayerPos.Y = PlayerPos.Y + PlayerVel.Y
	
	DrawCircle(PlayerPos.X, PlayerPos.Y, PlayerRadius)
	
	DrawLineList(LineList)

	Flip
	
Until KeyHit(KEY_ESCAPE)

Function DrawLineList(List:TList)

	For Local L:TLine = EachIn List
	
		DrawLine(L.P1.X, L.P1.Y, L.P2.X, L.P2.Y)
		
	Next
	
EndFunction

Function DistanceToLineSegment:Double(ax:Double,ay:Double, bx:Double,by:Double, px:Double,py:Double)
	'Returns the distance from p to 
	'	the closest point on line segment a-b.
	
	Local dx:Double=bx-ax
	Local dy:Double=by-ay
	
	Local t:Double =  ( (py-ay)*dy + (px-ax)*dx ) / (dy*dy + dx*dx)
	
	If t<0
		dx=ax
		dy=ay
	ElseIf t>1
		dx=bx
		dy=by
	Else
		dx = ax+t*dx
		dy = ay+t*dy
	End If
	
	dx:-px
	dy:-py
	
	g_ColPoint.X = PX + DX
	g_ColPoint.Y = PY + DY
	
	Return Sqr(dx*dx + dy*dy)
	
End Function

Function DistanceToLine:Double(ax:Double,ay:Double, bx:Double,by:Double, px:Double,py:Double)
	'Returns the distance from p to the closest point
	'	ont the line passing through a and b.
	
	Local dx:Double=bx-ax
	Local dy:Double=by-ay
	
	Return ( (ay-py)*dx + (px-ax)*dy ) / Sqr(dy*dy + dx*dx)
		
EndFunction

Function LineIntersection(line11x:Float, line11y:Float, line12x:Float, line12y:Float, line21x:Float, line21y:Float, line22x:Float, line22y:Float)
	'Calculate intersection point.
	g_IntersectPoint.X = line11x + (((line22x-line21x)*(line11y-line21y)-(line22y-line21y)*(line11x-line21x))/((line22y-line21y)*(line12x-line11x)-(line22x-line21x)*(line12y-line11y)))*(line12x-line11x)
	g_IntersectPoint.Y = line11y + (((line22x-line21x)*(line11y-line21y)-(line22y-line21y)*(line11x-line21x))/((line22y-line21y)*(line12x-line11x)-(line22x-line21x)*(line12y-line11y)))*(line12y-line11y)
EndFunction

Function CCW:Int(P1:TPoint, P2:TPoint, P3:TPoint)

	Local DX1:Int
	Local DX2:Int
	Local DY1:Int
	Local DY2:Int
		
	DX1 = P2.x - P1.x
	DY1 = P2.y - P1.y
	DX1 = P3.x - P1.x
	DY2 = P3.y - P1.y;
		
	If dx1*dy2 > dy1*dx2
		Return 1
	EndIf
	If dx1*dy2 < dy1*dx2
		Return -1
	EndIf
	If (dx1*dx2 < 0) Or (dy1*dy2 < 0)
		Return -1
	EndIf
	If (dx1*dx1 + dy1*dy1) < (dx2*dx2 + dy2*dy2)
		Return 1
	EndIf
		
	Return 0
	
EndFunction


Function DrawCircle(xCentre:Float, yCentre:Float, Radius:Float) 
	DrawOval(xCentre - (Radius), yCentre - (Radius), Radius * 2, Radius * 2) 
EndFunction


There are still quite a few problems with it--the circle occasionally gets stuck on outside corners, and sometimes it will just randomly disappear--so if you have a better method (and you probably do) then I'd appreciate it if you could do the write-up on your blog, although I'm still going to attempt to improve this one as well.

Thanks!