Collision Problem

BlitzMax Forums/BlitzMax Programming/Collision Problem

Yahfree

(Posted 2009) [#1]

Alright, so I have two rectangles I want to test collision for. I'm having a extremely difficult time with the math behind this one though, as one is rotating. Both objects have the same dimensions, however one of them is fixed with it's longer side against the X Axis. It also only moves on the X Axis.

Here's an image to explain:

So what do I do? I've tried implementing a Separating Axis Theorem algorithm, but that didn't work.

_Skully

(Posted 2009) [#2]

Its all in here... came from the code archives

SuperStrict

Type Poly
	Function TFormPolyToTFormPoly:Int( p1_xy:Float[], p1_x:Float=0, p1_y:Float=0,..
							p1_rot:Float=0, p1_scale_x:Float=1, p1_scale_y:Float=1,..
							p1_handle_x:Float=0, p1_handle_y:Float=0,..
							p1_origin_x:Float=0, p1_origin_y:Float=0,..
							p2_xy:Float[], p2_x:Float=0, p2_y:Float=0,..
							p2_rot:Float=0, p2_scale_x:Float=1, p2_scale_y:Float=1,..
							p2_handle_x:Float=0, p2_handle_y:Float=0,..
							p2_origin_x:Float=0, p2_origin_y:Float=0)
		
		If p1_xy.length<6 Or (p1_xy.length&1) Return False
		If p2_xy.length<6 Or (p2_xy.length&1) Return False
		
		Local tform1_xy:Float[]=TFormPoly(p1_xy,p1_x,p1_y,p1_rot,p1_scale_x,p1_scale_y,..
							p1_handle_x,p1_handle_y,p1_origin_x,p1_origin_y)
		
		Local tform2_xy:Float[]=TFormPoly(p2_xy,p2_x,p2_y,p2_rot,p2_scale_x,p2_scale_y,..
							p2_handle_x,p2_handle_y,p2_origin_x,p2_origin_y)
		
		If PolyToPoly(tform1_xy,tform2_xy)
			Return True
		Else
			Return False
		EndIf
		
	End Function
	
	Function PolyToTFormPoly:Int( p1_xy:Float[], p2_xy:Float[],..
							p2_x:Float=0, p2_y:Float=0, rot:Float=0,..
							scale_x:Float=1, scale_y:Float=1,..
							handle_x:Float=0, handle_y:Float=0,..
							origin_x:Float=0, origin_y:Float=0 )
		
		If p1_xy.length<6 Or (p1_xy.length&1) Return False
		If p2_xy.length<6 Or (p2_xy.length&1) Return False
		
		Local tform_xy:Float[]=TFormPoly(p2_xy,p2_x,p2_y,rot,scale_x,scale_y,..
							handle_x,handle_y,origin_x,origin_y)
		
		If PolyToPoly(p1_xy,tform_xy)
			Return True
		Else
			Return False
		EndIf
		
	End Function
	
	Function PolyToPoly:Int( p1_xy:Float[], p2_xy:Float[] )
		
		If p1_xy.length<6 Or (p1_xy.length&1) Return False
		If p2_xy.length<6 Or (p2_xy.length&1) Return False
		
		For Local i:Int=0 Until p1_xy.Length Step 2
			If PointInPoly(p1_xy[i],p1_xy[i+1],p2_xy) Then Return True
		Next
		For Local i:Int=0 Until p2_xy.Length Step 2
			If PointInPoly(p2_xy[i],p2_xy[i+1],p1_xy) Then Return True
		Next
		
		Local l1_x1:Float=p1_xy[p1_xy.Length-2]
		Local l1_y1:Float=p1_xy[p1_xy.Length-1]
		For Local i1:Int=0 Until p1_xy.Length Step 2
			Local l1_x2:Float=p1_xy[i1]
			Local l1_y2:Float=p1_xy[i1+1]
			
			Local l2_x1:Float=p2_xy[p2_xy.Length-2]
			Local l2_y1:Float=p2_xy[p2_xy.Length-1]
			For Local i2:Int=0 Until p2_xy.Length Step 2
				Local l2_x2:Float=p2_xy[i2]
				Local l2_y2:Float=p2_xy[i2+1]
				
				If LinesCross(l1_x1,l1_y1,l1_x2,l1_y2,l2_x1,l2_y1,l2_x2,l2_y2)
					Return True
				EndIf
				
				l2_x1=l2_x2
				l2_y1=l2_y2
			Next
			l1_x1=l1_x2
			l1_y1=l1_y2
		Next
		Return False
	End Function
	
	Function CircleToTFormPoly:Int( circle_x:Float, circle_y:Float, radius:Float,..
							xy:Float[], poly_x:Float=0, poly_y:Float=0, rot:Float=0,..
							scale_x:Float=1, scale_y:Float=1,..
							handle_x:Float=0, handle_y:Float=0,..
							origin_x:Float=0, origin_y:Float=0 )
		
		If xy.length<6 Or (xy.length&1) Return False
		
		Local tform_xy:Float[]=TFormPoly(xy,poly_x,poly_y,rot,scale_x,scale_y,..
							handle_x,handle_y,origin_x,origin_y)
		
		Return CircleToPoly(circle_x,circle_y,radius,tform_xy)
	End Function
	
	Function CircleToPoly:Int( circle_x:Float, circle_y:Float, radius:Float, xy:Float[] )
		
		If xy.length<6 Or (xy.length&1) Return False
		
		If PointInPoly(circle_x,circle_y,xy) Then Return True
		
		Local x1:Float=xy[xy.Length-2]
		Local y1:Float=xy[xy.Length-1]
		
		For Local i:Int=0 Until Len xy Step 2
			Local x2:Float=xy[i]
			Local y2:Float=xy[i+1]
			
			If LineToCircle(x1,y1,x2,y2,circle_x,circle_y,radius) Then Return True
			x1=x2
			y1=y2
		Next
		
		Return False
	End Function
	
	Function LineToTFormPoly:Int( line_x1:Float, line_y1:Float, line_x2:Float, line_y2:Float,..
							xy:Float[], poly_x:Float=0, poly_y:Float=0,..
							rot:Float=0, scale_x:Float=1, scale_y:Float=1,..
							handle_x:Float=0, handle_y:Float=0,..
							origin_x:Float=0, origin_y:Float=0 )
		
		If xy.length<6 Or (xy.length&1) Return False
		
		TFormGlobalToLocal(line_x1,line_y1,poly_x,poly_y,rot,scale_x,..
							scale_y,handle_x,handle_y,origin_x,origin_y)
		
		TFormGlobalToLocal(line_x2,line_y2,poly_x,poly_y,rot,scale_x,..
							scale_y,handle_x,handle_y,origin_x,origin_y)
		
		Return LineToPoly(line_x1,line_y1,line_x2,line_y2,xy)
	End Function
	
	Function LineToPoly:Int( line_x1:Float, line_y1:Float, line_x2:Float, line_y2:Float, xy:Float[] )
		
		If xy.length<6 Or (xy.length&1) Return False
		
		If PointInPoly(line_x1,line_y1,xy) Then Return True
		
		Local poly_x1:Float=xy[xy.Length-2]
		Local poly_y1:Float=xy[xy.Length-1]
		
		For Local i:Int=0 Until Len xy Step 2
			Local poly_x2:Float=xy[i]
			Local poly_y2:Float=xy[i+1]
			
			If LinesCross(line_x1,line_y1,line_x2,line_y2,..
							poly_x1,poly_y1,poly_x2,poly_y2) Then Return True
			poly_x1=poly_x2
			poly_y1=poly_y2
		Next
		
		Return False
		
	End Function
	
	Function PointInTFormPoly:Int( point_x:Float, point_y:Float, xy:Float[],..
							poly_x:Float=0, poly_y:Float=0, rot:Float=0,..
							scale_x:Float=1, scale_y:Float=1,..
							handle_x:Float=0, handle_y:Float=0,..
							origin_x:Float=0, origin_y:Float=0 )
		
		If xy.length<6 Or (xy.length&1) Return False
		
		TFormGlobalToLocal(point_x,point_y,poly_x,poly_y,rot,scale_x,..
							scale_y,handle_x,handle_y,origin_x,origin_y)
		
		Return PointInPoly(point_x,point_y,xy)
	End Function
	
	Function PointInPoly:Int( point_x:Float, point_y:Float, xy:Float[] )
		
		If xy.length<6 Or (xy.length&1) Return False
		
		Local x1:Float=xy[xy.Length-2]
		Local y1:Float=xy[xy.Length-1]
		Local cur_quad:Int=GetQuad(point_x,point_y,x1,y1)
		Local next_quad:Int
		Local total:Int
		
		For Local i:Int=0 Until Len xy Step 2
			Local x2:Float=xy[i]
			Local y2:Float=xy[i+1]
			next_quad=GetQuad(point_x,point_y,x2,y2)
			Local diff:Int=next_quad-cur_quad
			
			Select diff
			Case 2,-2
				If ( x2 - ( ((y2 - point_y) * (x1 - x2)) / (y1 - y2) ) )<point_x
					diff=-diff
				EndIf
			Case 3
				diff=-1
			Case -3
				diff=1
			End Select
			
			total:+diff
			cur_quad=next_quad
			x1=x2
			y1=y2
		Next
		
		If Abs(total)=4 Then Return True Else Return False
	End Function
	
	Function TFormPoly:Float[]( xy:Float[], tform_x:Float=0, tform_y:Float=0, rot:Float=0,..
							scale_x:Float=1, scale_y:Float=1,..
							handle_x:Float=0, handle_y:Float=0,..
							origin_x:Float=0, origin_y:Float=0 )
		
		If xy.length<6 Or (xy.length&1) Return Null
		
		Local tform_xy:Float[]=xy[..]
		
		For Local i:Int=0 Until tform_xy.Length Step 2
			TFormLocalToGlobal(tform_xy[i],tform_xy[i+1],tform_x,tform_y,rot,..
							scale_x,scale_y,handle_x,handle_y,origin_x,origin_y)
		Next
		
		Return tform_xy
	End Function
	
	Function TFormGlobalToLocal( point_x:Float Var, point_y:Float Var,..
							tform_x:Float=0, tform_y:Float=0, rot:Float=0,..
							scale_x:Float=1, scale_y:Float=1,..
							handle_x:Float=0, handle_y:Float=0,..
							origin_x:Float=0, origin_y:Float=0 )
		
		point_x:-origin_x
		point_y:-origin_y
		
		point_x:-tform_x
		point_y:-tform_y
		
		Local mag:Float=Sqr(point_x*point_x+point_y*point_y)
		Local ang:Float=ATan2(point_y,point_x)
		point_x=Cos(ang-rot)*mag
		point_y=Sin(ang-rot)*mag
		
		point_x:/scale_x
		point_y:/scale_y
		
		point_x:+handle_x
		point_y:+handle_y
	End Function
	
	Function TFormLocalToGlobal( point_x:Float Var, point_y:Float Var,..
							tform_x:Float=0, tform_y:Float=0, rot:Float=0,..
							scale_x:Float=1, scale_y:Float=1,..
							handle_x:Float=0, handle_y:Float=0,..
							origin_x:Float=0, origin_y:Float=0 )
		
		point_x:-handle_x
		point_y:-handle_y
		
		point_x:*scale_x
		point_y:*scale_y
		
		Local mag:Float=Sqr(point_x*point_x+point_y*point_y)
		Local ang:Float=ATan2(point_y,point_x)
		point_x=Cos(ang+rot)*mag
		point_y=Sin(ang+rot)*mag
		
		point_x:+tform_x
		point_y:+tform_y
		
		point_x:+origin_x
		point_y:+origin_y
	End Function
	
	'Adapted from Fredborg's code
	Function LinesCross:Int( x0:Float, y0:Float , x1:Float, y1:Float,..
							x2:Float ,y2:Float, x3:Float, y3:Float )
		  
		Local n:Float=(y0-y2)*(x3-x2)-(x0-x2)*(y3-y2)
		Local d:Float=(x1-x0)*(y3-y2)-(y1-y0)*(x3-x2)
		
		If Abs(d) < 0.0001 
			' Lines are parallel!
			Return False
		Else
			' Lines might cross!
			Local Sn:Float=(y0-y2)*(x1-x0)-(x0-x2)*(y1-y0)
	
			Local AB:Float=n/d
			If AB>0.0 And AB<1.0
				Local CD:Float=Sn/d
				If CD>0.0 And CD<1.0
					' Intersection Point
					Local X:Float=x0+AB*(x1-x0)
			       	Local Y:Float=y0+AB*(y1-y0)
					Return True
				End If
			End If
		
			' Lines didn't cross, because the intersection was beyond the end points of the lines
		EndIf
	
		' Lines do Not cross!
		Return False
	
	End Function
	
	'Adapted from TomToad's code
	Function LineToCircle:Int( x1:Float, y1:Float, x2:Float, y2:Float, px:Float, py:Float, r:Float )
		
		Local sx:Float = x2-x1
		Local sy:Float = y2-y1
		
		Local q:Float = ((px-x1) * (x2-x1) + (py - y1) * (y2-y1)) / (sx*sx + sy*sy)
		
		If q < 0.0 Then q = 0.0
		If q > 1.0 Then q = 1.0
		
		Local cx:Float=(1-q)*x1+q*x2
		Local cy:Float=(1-q)*y1 + q*y2
		
		
		If PointToPointDist(px,py,cx,cy) < r
			
			Return True
			
		Else
			
			Return False
			
		EndIf
	
		
	End Function 
	
	Function PointToPointDist:Float( x1:Float, y1:Float, x2:Float, y2:Float )
	
		Local dx:Float = x1-x2
		Local dy:Float = y1-y2
		
		Return Sqr(dx*dx + dy*dy)
	End Function
	
	
	Function GetQuad:Int(axis_x:Float,axis_y:Float,vert_x:Float,vert_y:Float)
		If vert_x<axis_x
			If vert_y<axis_y
				Return 1
			Else
				Return 4
			EndIf
		Else
			If vert_y<axis_y
				Return 2
			Else
				Return 3
			EndIf	
		EndIf
	
	End Function
	
	Function DrawPoly( xy:Float[], fill:Int=True, x:Float=0, y:Float=0 )
		Local origin_x:Float
		Local origin_y:Float
		GetOrigin origin_x,origin_y
		Local handle_x:Float
		Local handle_y:Float
		GetHandle handle_x,handle_y
		
		If fill
			_max2dDriver.DrawPoly xy,..
			-handle_x,-handle_y,..
			x+origin_x,y+origin_y
		Else
			Local x1:Float=xy[xy.Length-2]
			Local y1:Float=xy[xy.Length-1]
			For Local i:Int=0 Until Len xy Step 2
				Local x2:Float=xy[i]
				Local y2:Float=xy[i+1]
				_max2dDriver.DrawLine..
				-handle_x+x1,-handle_y+y1,..
				-handle_x+x2,-handle_y+y2,..
				x+origin_x-0.5,y+origin_y-0.5
				x1=x2
				y1=y2
			Next
		EndIf
	End Function	
End Type

Yahfree

(Posted 2009) [#3]

I don't see anything in there having to do with rotated poly -> poly.

Jesse

(Posted 2009) [#4]

the TFormPolyToTFormPoly function checks the polygon collision just pass the untransformed poygon's with their rotation amount and position and it will return whether their is a collision or not.

Yahfree

(Posted 2009) [#5]

I'll give it a shot. Thanks!

Yahfree

(Posted 2009) [#6]

Here's a dumb question not deserving it's own thread:

What's the proper way to declare multiple things in an array at once?

For example...

"
pointsetxy = [x, y, x + 100, y, x + 100, y + 45, x, y + 45]
"

returns the error

"Compile Error: Unable to convert from 'Float Array' to 'Int'"

Oddball

(Posted 2009) [#7]

pointsetxy:float[] = [x, y, x + 100, y, x + 100, y + 45, x, y + 45]

Also the array fields must be of the same type as the array. So in the above example x and y must be floats. If they are not floats you must cast them like so:

pointsetxy:float[] = [float(x), float(y), x + 100.0, float(y), x + 100.0, y + 45.0, float(x), y + 45.0]

Yahfree

(Posted 2009) [#8]

mhmm..

	Field pointsetxy:Float[8]
	Method Create(l:Int)
		lane = l
		rem
			------>lane1-------> x+
			<------lane2<------- x-
			------>lane3-------> x+
			<------lane4<------- x-
			<------lane5<------- x-
			>------lane6>------- x+
		end rem
		Select lane
			Case 1
				y = 200
				x = -50
				direction = 1
				speed = 2
			Case 2
				y = 260
				x = 1074
				direction = -1
				speed = 3
			Case 3
				y = 320
				x = -50
				direction = 1
				speed = 1
			Case 4
				y = 380
				x = 1074
				direction = -1
				speed = 2
			Case 5
				y = 440
				x = 1074
				direction = -1
				speed = 1.5
			Case 6
				y = 500
				x = -50
				direction = 1
				speed = 3.8
		End Select
		ListAddLast(EnemyList, Self)
		pointsetxy:Float[] = [x, y, x + 100, y, x + 100, y + 45, x, y + 45]
		
	End Method

still produces a syntax error on the '=' sign. :\

_Skully

(Posted 2009) [#9]

Can you have math equations in an array initializer? I didn't think so... but just for the heck of it, try enclosing them in ()'s

Yahfree

(Posted 2009) [#10]

same thing:

Compile Error: Expecting expression but encountered '='

with

	Field pointsetxy:Float[8]
	Method Create(l:Int)
		lane = l
		rem
			------>lane1-------> x+
			<------lane2<------- x-
			------>lane3-------> x+
			<------lane4<------- x-
			<------lane5<------- x-
			>------lane6>------- x+
		end rem
		Select lane
			Case 1
				y = 200
				x = -50
				direction = 1
				speed = 2
			Case 2
				y = 260
				x = 1074
				direction = -1
				speed = 3
			Case 3
				y = 320
				x = -50
				direction = 1
				speed = 1
			Case 4
				y = 380
				x = 1074
				direction = -1
				speed = 2
			Case 5
				y = 440
				x = 1074
				direction = -1
				speed = 1.5
			Case 6
				y = 500
				x = -50
				direction = 1
				speed = 3.8
		End Select
		ListAddLast(EnemyList, Self)
		pointsetxy:Float[] = ([x, y, x + 100, y, x + 100, y + 45, x, y + 45])

I mean, I could do pointsetxy[0]...pointsetxy[1]....

But that would be a lot of extra writing... surely there's a way for this to work?

Yahfree

(Posted 2009) [#11]

I found a different solution with global variables, and the TFormPoly code seems to work, thanks everyone!