Ellispsoid Collision Detection

BlitzMax Forums/BlitzMax Tutorials/Ellispsoid Collision Detection

Haramanai
 #1
This tutorial it’s about collision detection for games using ellipsoids.
The tutorial that created by Paul Nettle it’s at the location General collision detection for games using ellipsoids
Be sure to read it cause the only thing that you will find in this tutorial is the conversion of the psephtocode that it’s located at the end of article and the necessary tools that you will need to proceed all the steps.

First I am going to give you the the <Vector.BMX> that is a vector type originally created by SSS at the MaxPhisics Topic. I modified it a little bit make my life easier in the translation.
<Vector.Bmx>
'Strict
'Import BRL.Basic
Type TVector
	'VARIABLES
	Field _x:Double, _y:Double
	
	'METHODS
	Method New()
		_x = 0
		_y = 0
	End Method
	
	Method Set(x:Double,y:Double)
		_x=x
		_y=y
	End Method
	
	Method Get(x:Double Var, y:Double Var)
		x = _x
		y = _y
	End Method
	
	Method Multiply:TVector(factor:Double , bSelf:Byte = True)
		If bSelf = False
			Return TVector.create(_x*factor , _y*factor)
		Else	
			_x:*factor
			_y:*factor
			Return Self
		End If
	End Method
	
	Method Add:TVector(v:TVector,bself=False)
		If bself = False
			Return TVector.Create(_x+v._x,_y+v._y)
		Else
			_x:+v._x
			_y:+v._y
			Return Self 
		EndIf
	End Method
	
	Method Subtract:TVector(v:TVector,bself=False)
		If bself = False
			Return TVector.Create(_x-v._x,_y-v._y)
		Else
			_x:-v._x
			_y:-v._y
			Return Self
		EndIf
	End Method
	
	Method Copy:TVector()
		Return Create(_x,_y)
	End Method
	
	Method DotProduct:Double(v:TVector)
		Return _x*v._x+_y*v._y
	End Method
	
	Method AngleBetween:Double(v:TVector)
		Return ACos(DotProduct(v)/(Magnitude()*v.Magnitude()))
	EndMethod
	
	Method SetAngle(angle:Double)
		Local mag:Double = Magnitude()
		_x = Cos(angle)*mag
		_y = -Sin(angle)*mag
	End Method
	
	Method GetAngle:Double()
		Return ATan2(-_y,_x)
	End Method
	
	Method SetMagnitude(mag:Double)
		Normalise()
		_x:*mag
		_y:*mag
	End Method
	
	Method Magnitude:Double()
		Return Sqr(_x^2+_y^2)
	End Method
	
	Method MagSquared:Double()
		Return _x^2+_y^2
	End Method
	
	Method Normalise:TVector(bself:Byte=True)
		Local m:Double = Magnitude()
		If bself = False
			Return TVector.Create(_x/m,_y/m)
		Else
			_x:/m
			_y:/m
		EndIf
	End Method
	
	Method Normalize:TVector(bself:Byte = True)
		Local m:Double = Magnitude()
		If bself = False
			Return TVector.Create(-_y/m,_x/m)
		Else
			Local _tmpx:Double = _x
			_x = -_y/m
			_y = _tmpx/m
		End If
	End Method
	
	
	Method Reverse:TVector(bSelf:Byte = False)
		If bSelf = False
			Return TVector.create(-_x , -_y)
		Else
			_x = -_x
			_y = -_y
		End If
	End Method
		
	Method PrintVector()
		Print "(" + _x + "," + _y + ")"
	End Method
	
	Method Draw(xoff,yoff)
		DrawLine xoff,yoff,xoff+_x,yoff+_y
	End Method

	'FUNCTIONS
	Function Create:TVector(x:Double,y:Double)
		Local o:TVector = New TVector
		o._x=x
		o._y=y
		Return o
	End Function
	
	Function FromTo:TVector(v1:TVector,v2:TVector)
		Return Create(v2._x-v1._x,v2._y-v2._x)
	End Function
End Type


After that I am giving you the <Rest.Bmx> that contains the intersection and IntersectSphere functions from the document and The type Colliders and some other necessary functions.
<Rest.Bmx>
Global EPSILON:Double = 0.0002
Function intersect:Double(pOrigin:TVector , pNormal:TVector , rOrigin:TVector , rVector:TVector)
	Local d:Double = -pNormal.DotProduct(pOrigin)
	Local numer:Double = pNormal.DotProduct(rOrigin) + d
	Local denom:Double = pNormal.DotProduct(rVector)
	Return -(numer / denom)
End Function


Function closestPointOnTriangle:TVector(a:TVector , b:TVector , c:TVector , p:TVector)
	Local Rab:TVector = closestPointOnLine(a , b , p)
	Local Rbc:TVector = closestPointOnLine(b , c , p)
	Local Rca:TVector = closestPointOnLine(c , a , p)
	
	'''/// Return the closest point... how?
		'''' So I find the square distance from the point of lines to p
	Local RabM:Double =  (Rab._x - p._x)^2 + (Rab._y - p._y)^2 
	Local RbcM:Double = (Rbc._x - p._x)^2 + (Rbc._y - p._y)^2 
	Local RcaM:Double = (Rca._x - p._x)^2 + (Rca._y - p._y)^2
	
	If closestOfThree(RbcM , RabM , RcaM) Then Return Rbc
	If closestOfThree(RcaM , RbcM , RabM) Then Return Rca
	If closestOfThree(RabM , RbcM , RcaM) Then Return Rab

	Function closestOfThree:Byte(a:Double , b:Double , c:Double)
		If a < b And a < c Then Return True
		If a = b And a < c Then Return True
		If a < b And a = c Then Return True
		Return False
	End Function
End Function



Function closestPointOnLine:TVector(a:TVector , b:TVector , p:TVector)
	Local c:TVector = TVector.create(p._x - a._x , p._y - a._y) '''' c = p - a
	Local V:TVector = TVector.create(b._x - a._x , b._y - a._y)  ''' V = b - a
	V.normalise()
	Local d:Double = Sqr( (a._x - b._x)^2 + (a._y - b._y)^2 )
	Local t:Double = V.dotProduct(c)
	
	''''// Check to see if 't' is beyond the extemnds of line segment
	If t < 0 Then Return a
	If t > d Then Return b
	
	''''///Return the point between 'a' and 'b'
	V.setMagnitude(t)
	Return TVector.create(a._x + V._x , a._y + V._y)
	
End Function

Function intersectSphere:Double(rO:TVector , rV:TVector , sO:TVector , sR:Double)
	Local rv2:TVector = rV.normalise(False)
	Local Q:TVector = TVector.create(sO._x - rO._x , sO._y - rO._y)
	Local c:Double = Q.Magnitude()
	Local v:Double = Q.DotProduct(rV2)
	Local d:Double = sR^2 - (c^2 - v^2)
	'''/// If there is no intersection Return -1
	If (d < 0.0) Return -1.0
	
	'' Return the distance to the [first] intersection point
	Return v - Sqr(d)
End Function

Function DrawCircle(_x:Double , _y:Double , _r:Double)
	DrawOval _x - _r , _y - _r , _r*2 , _r*2
End Function

Function DrawVectorCircle(_P:TVector , _r:Double)
	DrawOval _P._x - _r , _P._y - _r , _r*2 , _r*2
End Function

Function Mirror( Vector:TVector , Normal:TVector )
	Local Dotprod:Double = -Vector._X * Normal._X - Vector._Y * Normal._Y
	Vector._X=Vector._X+2 * Normal._X * dotprod
	Vector._Y=Vector._Y+2 * Normal._Y * dotprod
End Function

Function DivideVector:TVector(Source:TVector , Scaler:TVector , bSelf:Byte = True)
	If bSelf = False
		Return TVector.create(Source._x / Scaler._x , Source._y / Scaler._y)
	Else
		Source.set(Source._x / Scaler._x , Source._y / Scaler._y)
	End If
End Function

Function MultiplyVector:TVector(Source:TVector , Scaler:TVector , bSelf:Byte = True)
	If bSelf = False
		Return TVector.create(Source._x * Scaler._x , Source._y * Scaler._y)
	Else
		Source.set(Source._x * Scaler._x , Source._y * Scaler._y)
	End If
End Function

Function scale_potential_colliders_to_ellipsoid_space(RadiusVector:TVector)
	For Local _Collider:TCollider= EachIn TCollider._List
		For Local i:Int = 0 To 1
			_Collider._p[i]._x:/ RadiusVector._x 
			_Collider._p[i]._y:/ RadiusVector._y
		Next
	Next
End Function

Function scale_back_potential_colliders_from_ellipsoid_space(RadiusVector:TVector)
	For Local _Collider:TCollider = EachIn TCollider._List
		For Local i:Int = 0 To 1
			_Collider._p[i]._x:* RadiusVector._x
			_Collider._p[i]._y:* RadiusVector._y
		Next
	Next
End Function

Function TouchTheGround(sourcePoint:TVector)
	'If KeyDown(KEY_D) Then DebugStop()
	For Local _Collider:TCollider = EachIn TCollider._List
		Local pOrigin:TVector = _Collider._p[0].copy()
		Local Plane:TVector =  _Collider._p[0].SubTract(_Collider._p[1])		
		Local pNormal:TVector = Plane.Normalize(False)
		Local Foot:TVector = sourcePoint.add( pNormal.Multiply(-1 , False) )
		Local OnLine:TVector = closestPointOnLine(_Collider._p[0] , _Collider._p[1] , foot)
		If Abs(Foot._x - OnLine._x) < EPSILON*2
			If Abs(Foot._y - OnLIne._y) < EPSILON*2
				Local pDist:Double = intersect(pOrigin , pNormal , foot , pNormal.Multiply(-1 , False))
				If pDist >= 0.0 And pDist <= EPSILON*2 And Abs(Plane.getAngle()) > 110
					DrawText "Touch" , 10 , 10
					Return True
				End If
			End If
		End If

	Next
	Return False
End Function



'WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
'WWW	COLIDERS
'WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
Rem
	It will be just lines with sored friction valuse to work with Ellipsoid code
End Rem

Type TCollider
	Field _p:TVector[2]
	Field _friction:Double
	Global _List:TList = CreateList()
	
	Function createFromVects:TCollider(_a:TVector , _b:TVector , _friction:Double)
		Local _Collider:TCollider = New TCollider
		_Collider._p[0] = _a.copy()
		_Collider._p[1] = _b.copy()
		_Collider._friction = _friction
		ListAddLast TCollider._List , _Collider
		Return _Collider
	End Function
	
	Method Draw()
		DrawLine _p[0]._x , _p[0]._y , _p[1]._x , _p[1]._y
	End Method
	
End Type


Here I am giving you the Translation of the pseutocode from the article <CollisionDetection.Bmx>
<CollisionDetection.Bmx>
'// The collision detection entry point
'?collisionDetection(Point sourcePoint, Vector velocityVector, Vector gravityVector)
Function collisionDetection(sourcePoint:TVector, velocityVector:TVector, gravityVector:TVector)
	'DebugStop()
	'?{
	'// We need To do any pre-collision detection work here. Such as adding
	'// gravity To our velocity vector. We want To do it in this
	'// separate routine because the following routine is recursive, And we
	'// don't want to recursively add gravity.
	'// Add gravity 
	'?velocityVector += gravityVector;
	If touch = False
		velocityVector.add(gravityVector , True)
	End If
	
	'// At this point, we_ll scale our inputs To the collision routine
	'?sourcePoint /= radiusVector;
	DivideVector(SourcePoint , radiusVector)
	'?velocityVector /= radiusVector;
	DivideVEctor(velocityVector , radiusVector)
	'// Okay! Time To do some collisions
	'call collideWithWorld(sourcePoint, velocityVector);
	collideWithWorld(sourcePoint, velocityVector)
	'// Our collisions are complete, un-scale the output
	'?sourcePoint *= radiusVector;
	MultiplyVector(sourcePoint , RadiusVector)
	MultiplyVector(VelocityVector , RadiusVector)
	'scale_back_potential_colliders_from_ellipsoid_space(RadiusVector)

	
'?}
End Function


'// The collision detection_s recursive routine
'?collideWithWorld(Point sourcePoint, Vector velocityVector)
Function collideWithWorld(sourcePoint:TVector, velocityVector:TVector)
	'If KeyDown(KEY_D) Then DebugStop()
	'?{
	'// How far do we need To go?
	'?Double distanceToTravel = length of velocityVector;
	Local distanceToTravel:Double = velocityVector.Magnitude()
	
	'// Do we need To bother?
	'?If (distanceToTravel < EPSILON) Then Return;
	If (distanceToTravel < EPSILON) Then Return
	'// Whom might we collide with?
	'?List potentialColliders = determine list of potential colliders;
	'// If there are none, we can safely move To the destination And bail
	'?If (potentialColliders is empty)
	If ListIsEmpty(TCollider._List)
		'?{
		'?sourcePoint += velocityVector;
		sourcePoint.add(velocityVector , True)
		'?Return;
		Return
		'?}
	End If
	
	'// You_ll need To write this routine To deal with your specific data
	'?scale_potential_colliders_to_ellipsoid_space(radiusVector);
	'scale_potential_colliders_to_ellipsoid_space(radiusVector)
	'// Determine the nearest collider from the list potentialColliders
	'?bool collisionFound = False;
	Local collisionFound = False
	'?Double nearestDistance = -1.0;
	Local nearestDistance:Double = -1.0
	'?Point nearestIntersectionPoint = Null;
	Local nearestIntersectionPoint:TVector = Null
	'?Point nearestPolygonIntersectionPoint = Null;
	Local nearestPolygonIntersectionPoint:TVector = Null
	''''' Store and the friction of the collider
	Local nearestFriction:Double


	'?For (each polygon in potentialColliders)
	For Local _Collider:TCollider = EachIn TCollider._List
		'?{

		'// Plane origin/normal
		'?Point pOrigin = any vertex from current poly;
		Local pOrigin:TVector = _Collider._p[0].copy()
		
		'?Vector pNormal = surface normal (unit vector) from current poly;
		'''' pNormal to the outer scope
		Local pNormal:TVector = _Collider._p[0].SubTract(_Collider._p[1])
		pNormal.normalize()
		
		'// Determine the distance from the plane To the source
		'?Double pDist = intersect(pOrigin, pNormal, source, -pNormal);
		Local pDist:Double = intersect(pOrigin , pNormal , sourcePoint , pNormal.Multiply(-1 , False))
		
		'?Point sphereIntersectionPoint;
		Local sphereIntersectionPoint:TVector
			
		'?Point planeIntersectionPoint;
		Local planeIntersectionPoint:TVector
			
		'// Is the source point behind the plane?
		'//
		'// [note that you can remove this condition If your visuals are Not
		'// using backface culling]
		'?If (pDist < 0.0) 
		If (pDist < 0.0) 
			'?{
			'Continue;
			Continue
			'?}
		Else 
		
		'// Is the plane embedded (i.e. within the distance of 1.0 For our
		'// unit sphere)?
			
			'?If (pDist <= 1.0)
			If pDist <= 1.0   ''''   ELISPOID
				'?{
				'// Calculate the plane intersection point
				'?Vector temp = -pNormal with length set To pDist;
				Local temp:TVector = pNormal.Multiply(-1 , False)
				temp.setMagnitude(pDist)

				'?planeIntersectionPoint = source + temp;
				planeIntersectionPoint = sourcePoint.add(temp)
					
				'?}
			Else
				'?{
				'// Calculate the sphere intersection point
				'?sphereIntersectionPoint = source - pNormal;
				'ELIPSOID    for elipsoid the length of pNormal that if setted to one it's ok
								'But for now we have to set it to circle radius
				Local tmp:TVector = pNormal.copy()
				'tmp.setMagnitude(RadiusVector._x)
				sphereIntersectionPoint = sourcePoint.subtract(tmp)

				'// Calculate the plane intersection point
				'?Double t = intersect(pOrigin, pNormal,
				'?		sphereIntersectionPoint, Velocity with
				'?		normalized length);
				Local t:Double = intersect(pOrigin , pNormal ,..
						sphereIntersectionPoint , velocityVector.normalise(False) )
							
				'// Are we traveling away from this polygon?
				'?If (t < 0.0) Continue;
				If t < 0.0 Then Continue
					
				'// Calculate the plane intersection point
				'?Vector V = velocityVector with length set To t;
				Local V:TVector = velocityVector.copy()
				V.setMagnitude(t)
					
				'?planeIntersectionPoint = sphereIntersectionPoint + V;
				planeIntersectionPoint = sphereIntersectionPoint.add(V)

			'?}
			End If
			'// Unless otherwise noted, our polygonIntersectionPoint is the
			'// same point as planeIntersectionPoint
			'?Point polygonIntersectionPoint = planeIntersectionPoint;
			Local polygonIntersectionPoint:TVector = planeIntersectionPoint.copy()
			'// So_ are they the same?
			Local closestPointPolygon:TVector = closestPointOnLine(_Collider._p[0] , _Collider._p[1],..
																planeIntersectionPoint)
				
			'?If (planeIntersectionPoint is Not within the current polygon)
			'''''''''''''''''''''  Those ifs does not work for verical and horizonal lines so...
			Local _an:Double = _Collider._p[0].subtract(_Collider._p[1]).getAngle()
			If Abs(_an) = 180.0 Or Abs(_an) = 0.0 '''Horizontal
				If Not Abs(closestPointPolygon._x - polygonIntersectionPoint._x) < EPSILON
					polygonIntersectionPoint = closestPointPolygon.copy()
				End If
			End If
			If Abs(_an) = 90.0  ''''VERTICAL
				If Not Abs(closestPointPolygon._y - polygonIntersectionPoint._y) < EPSILON
					polygonIntersectionPoint = closestPointPolygon.copy()
				End If
			End If
			If Not Abs(closestPointPolygon._x - polygonIntersectionPoint._x) < EPSILON
				If Not Abs(closestPointPolygon._y - polygonIntersectionPoint._y) < EPSILON
			'?{
				'?polygonIntersectionPoint = nearest point on polygon's
				'?perimeter To planeIntersectionPoint;
				polygonIntersectionPoint = closestPointPolygon.copy()
			'?}
				End If
			End If
			'// Invert the velocity vector
			'?Vector negativeVelocityVector = -velocityVector;
			Local negativeVelocityVector:TVector = velocityVector.Multiply(-1 , False)
			'// Using the polygonIntersectionPoint, we need To reverse-intersect
			'// with the sphere (note: the 1.0 below is the unit-sphere_s
			'// radius)
			'?Double t = intersectSphere(sourcePoint, 1.0,
									'?polygonIntersectionPoint, negativeVelocityVector);
			Local t:Double = intersectSphere(polygonIntersectionPoint , negativeVelocityVector ,..
										sourcePoint , 1.0)	''''' ELLIPSOID
										
			'// Was there an intersection with the sphere?
			'?If (t >= 0.0 && t <= distanceToTravel)
			If t >=0.0 And t<= distanceToTravel
			'?{
				'// Where did we intersect the sphere?
				'?Vector V = negativeVelocityVector with length set To t;
				Local V:TVector = negativeVelocityVector.copy()
				V.setMagnitude(t)
				'?Vector intersectionPoint = polygonIntersectionPoint + V;
				Local intersectionPoint:TVector = polygonIntersectionPoint.add(V)
				
				'// Closest intersection thus far?
				'?If (!collisionFound || t < nearestDistance)
				If Not collisionFound Or t < nearestDistance
				'?{
					'?nearestDistance = t;
					nearestDistance = t
					'?nearestIntersectionPoint = intersectionPoint;
					nearestIntersectionPoint = intersectionPoint.copy()
					'?nearestPolygonIntersectionPoint = polygonIntersectionPoint;
					nearestPolygonIntersectionPoint = PolygonIntersectionPoint.copy()
					'?collisionFound = True;
					collisionFound = True
					''' Pass and the friction of the collider
					nearestFriction = _Collider._Friction
					'?}
				End If
			'?}
			End If
		'?}
		End If
	'?}
	Next
	
	'// If we never found a collision, we can safely move To the destination
	'// And bail
	'?If (!collisionFound)
	If Not collisionFound
	'?{
		'?sourcePoint += velocityVector;
		sourcePoint.add(velocityVector , True)
		'?Return;
		Return
	'?}
	End If

			
	'// Move To the nearest collision
	'?Vector V = velocityVector with length set To (nearestDistance - EPSILON);
	Local V:TVector = velocityVector.copy()
	V.setMagnitude(nearestDistance - EPSILON)
	'?sourcePoint += V;
	sourcePoint.add(V , True)
	
	'// What's our destination (relative to the point of contact)?
	'Set length of V To (distanceToTravel _ nearestDistance);
	V.setMagnitude(distanceToTravel - nearestDistance)
	'''''Here I will apply the FRICTION
	V.Multiply(0.5)

	'Point destinationPoint = nearestPolygonIntersectionPoint + V;	
	Local destinationPoint:TVector = nearestPolygonIntersectionPoint.add(V)

	'// Determine the sliding plane
	'?Point slidePlaneOrigin = nearestPolygonIntersectionPoint;
	Local slidePlaneOrigin:TVector = nearestPolygonIntersectionPoint.copy()
	'?Vector slidePlaneNormal = nearestPolygonIntersectionPoint - sourcePoint;	
	Local slidePlaneNormal:TVector = nearestPolygonIntersectionPoint.subtract(sourcePoint)
	slidePlaneNormal.normalise()  

	'// We now project the destination point onto the sliding plane
	'?Double time = intersect(slidePlaneOrigin, slidePlaneNormal,
						'?destinationPoint, slidePlaneNormal);
	Local time:Double = intersect(slidePlaneOrigin , slidePlaneNormal , ..
							destinationPoint , slidePlaneNormal)

	'?Set length of slidePlaneNormal To time;
	slidePlaneNormal.setMagnitude(time)
		
	'?Vector destinationProjectionNormal = slidePlaneNormal;
	Local destinationProjectionNormal:TVector = slidePlaneNormal.copy()
	
	'?Point newDestinationPoint = destination + destinationProjectionNormal;	
	Local newDestinationPoint:TVector = destinationPoint.add(destinationProjectionNormal )
	
		
	'// Generate the slide vector, which will become our New velocity vector
	'// For the Next iteration
	'?Vector newVelocityVector = newDestinationPoint _nearestPolygonIntersectionPoint;
	Local newVelocityVector:TVector = newDestinationPoint.subtract(nearestPolygonIntersectionPoint)
	'here I am fixing the wrong newVelocityVector that I get from the positive time...
	If time > 0.0 Then newVelocityVector.Multiply(-1)

	'// Recursively slide (without adding gravity)
	'?collideWithWorld(sourcePoint, newVelocityVector);
	

	collideWithWorld(sourcePoint , newVelocityVector)

'}
End Function


A Map editor to create some test maps. <MapEditor.Bmx> . This is a very simple map editor becareful that you must create all your polygons with the clockwise rule. You don’t have to close the polygons but you must know what you are doing. For example the lower level of the map can stay open.
After you created your leve copy paste from the output the nessacary code in the map file you are including in your test.
<MapEditor.Bmx>
Strict

Include "Vector.Bmx"
Include "Rest.Bmx"
Include "Map.Bmx"

'WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
'                         COPY PASTE MAP
'                   To THE MAIN TEST CODE
'WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW



'Local cOrigin:TVector = TVector.Create( 244 , 468 )

'WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
Local LineSelected:TCollider
Local VectorSelected:TVector
Local friction:Double = 0.05

Graphics 800 , 600
While Not KeyDown(KEY_ESCAPE)
	Cls

	For Local Collider:TCollider = EachIn TCollider._List
		SetColor 255 , 255*friction , 0
		Collider.Draw()
	Next
	

	If Not VectorSelected = Null
		DrawVectorCircle(VectorSelected , 2)
	End If
	If MouseHit(1)
		If VectorSelected = Null
			VectorSelected  = TVector.create(MouseX() , MouseY())
		Else
			Local Collider:TCollider = TCollider.createFromVects(VectorSelected , TVector.create(MouseX() , MouseY()) , friction)
			VectorSelected = Collider._p[1]
		End If
	End If
	
	If MouseHit(2)
		For Local Collider:TCollider = EachIn TCollider._List
			For Local i:Int = 0 To 1
				If Abs(MouseX() - Collider._p[i]._x) < 3 And Abs(MouseY() - Collider._p[i]._y) < 3
					VectorSelected = Collider._p[i]
				End If
			Next
		Next
	End If
	
	If KeyDown(KEY_SPACE)
		VectorSelected = Null
	End If

	Flip
Wend

Print ""
Print""
Print "'WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW"
Print "'                         COPY PASTE MAP"
Print "'                   To THE MAIN TEST CODE"
Print "'WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW"
Print""

Local N:Int = 1
For Local Coll:TCollider = EachIn TCollider._List
	Local str:String = "Local Coll"
	str:+ N + ":TCollider = TCollider .CreateFromVects( TVector.Create( "+ Int(Coll._p[0]._x) +" , " +  Int(Coll._p[0]._y) + " ) "
	str:+ " , TVector.Create(" + Int(Coll._p[1]._x) +" , " +  Int(Coll._p[1]._y) + ")" +  " , " + Coll._friction +  ")"  
	Print str
	N:+1
Next
Print""
Local str:String = "Local cOrigin:TVector = TVector.Create( "
str:+ Int(cOrigin._x) + " , " + Int(cOrigin._y) + " )"
Print str
Print ""
Print "'WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW"
Print ""
End


Last I am Giving you a map <Map.Bmx>
<Map.Bmx>
'WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
'                         COPY PASTE MAP
'                   To THE MAIN TEST CODE
'WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW

Local Coll1:TCollider = TCollider .CreateFromVects( TVector.Create( 9 , 180 )  , TVector.Create(105 , 223) , 0.050000000745058060)
Local Coll2:TCollider = TCollider .CreateFromVects( TVector.Create( 105 , 223 )  , TVector.Create(113 , 547) , 0.050000000745058060)
Local Coll3:TCollider = TCollider .CreateFromVects( TVector.Create( 113 , 547 )  , TVector.Create(327 , 544) , 0.050000000745058060)
Local Coll4:TCollider = TCollider .CreateFromVects( TVector.Create( 327 , 544 )  , TVector.Create(326 , 538) , 0.050000000745058060)
Local Coll5:TCollider = TCollider .CreateFromVects( TVector.Create( 326 , 538 )  , TVector.Create(331 , 536) , 0.050000000745058060)
Local Coll6:TCollider = TCollider .CreateFromVects( TVector.Create( 331 , 536 )  , TVector.Create(339 , 527) , 0.050000000745058060)
Local Coll7:TCollider = TCollider .CreateFromVects( TVector.Create( 339 , 527 )  , TVector.Create(401 , 510) , 0.050000000745058060)
Local Coll8:TCollider = TCollider .CreateFromVects( TVector.Create( 401 , 510 )  , TVector.Create(441 , 530) , 0.050000000745058060)
Local Coll9:TCollider = TCollider .CreateFromVects( TVector.Create( 441 , 530 )  , TVector.Create(462 , 542) , 0.050000000745058060)
Local Coll10:TCollider = TCollider .CreateFromVects( TVector.Create( 462 , 542 )  , TVector.Create(470 , 565) , 0.050000000745058060)
Local Coll11:TCollider = TCollider .CreateFromVects( TVector.Create( 470 , 565 )  , TVector.Create(519 , 583) , 0.050000000745058060)
Local Coll12:TCollider = TCollider .CreateFromVects( TVector.Create( 519 , 583 )  , TVector.Create(624 , 577) , 0.050000000745058060)
Local Coll13:TCollider = TCollider .CreateFromVects( TVector.Create( 624 , 577 )  , TVector.Create(670 , 539) , 0.050000000745058060)
Local Coll14:TCollider = TCollider .CreateFromVects( TVector.Create( 670 , 539 )  , TVector.Create(688 , 465) , 0.050000000745058060)
Local Coll15:TCollider = TCollider .CreateFromVects( TVector.Create( 688 , 465 )  , TVector.Create(685 , 403) , 0.050000000745058060)
Local Coll16:TCollider = TCollider .CreateFromVects( TVector.Create( 685 , 403 )  , TVector.Create(663 , 352) , 0.050000000745058060)
Local Coll17:TCollider = TCollider .CreateFromVects( TVector.Create( 663 , 352 )  , TVector.Create(633 , 288) , 0.050000000745058060)
Local Coll18:TCollider = TCollider .CreateFromVects( TVector.Create( 633 , 288 )  , TVector.Create(564 , 245) , 0.050000000745058060)
Local Coll19:TCollider = TCollider .CreateFromVects( TVector.Create( 564 , 245 )  , TVector.Create(472 , 227) , 0.050000000745058060)
Local Coll20:TCollider = TCollider .CreateFromVects( TVector.Create( 472 , 227 )  , TVector.Create(472 , 188) , 0.050000000745058060)
Local Coll21:TCollider = TCollider .CreateFromVects( TVector.Create( 472 , 188 )  , TVector.Create(505 , 169) , 0.050000000745058060)
Local Coll22:TCollider = TCollider .CreateFromVects( TVector.Create( 505 , 169 )  , TVector.Create(598 , 154) , 0.050000000745058060)
Local Coll23:TCollider = TCollider .CreateFromVects( TVector.Create( 598 , 154 )  , TVector.Create(664 , 161) , 0.050000000745058060)
Local Coll24:TCollider = TCollider .CreateFromVects( TVector.Create( 664 , 161 )  , TVector.Create(751 , 131) , 0.050000000745058060)
Local Coll25:TCollider = TCollider .CreateFromVects( TVector.Create( 751 , 131 )  , TVector.Create(762 , 82) , 0.050000000745058060)
Local Coll26:TCollider = TCollider .CreateFromVects( TVector.Create( 762 , 82 )  , TVector.Create(795 , 49) , 0.050000000745058060)
Local Coll27:TCollider = TCollider .CreateFromVects( TVector.Create( 491 , 535 )  , TVector.Create(489 , 516) , 0.050000000745058060)
Local Coll28:TCollider = TCollider .CreateFromVects( TVector.Create( 489 , 516 )  , TVector.Create(519 , 514) , 0.050000000745058060)
Local Coll29:TCollider = TCollider .CreateFromVects( TVector.Create( 519 , 514 )  , TVector.Create(520 , 534) , 0.050000000745058060)
Local Coll30:TCollider = TCollider .CreateFromVects( TVector.Create( 520 , 534 )  , TVector.Create(492 , 533) , 0.050000000745058060)
Local Coll31:TCollider = TCollider .CreateFromVects( TVector.Create( 540 , 482 )  , TVector.Create(571 , 478) , 0.050000000745058060)
Local Coll32:TCollider = TCollider .CreateFromVects( TVector.Create( 571 , 478 )  , TVector.Create(572 , 499) , 0.050000000745058060)
Local Coll33:TCollider = TCollider .CreateFromVects( TVector.Create( 572 , 499 )  , TVector.Create(541 , 499) , 0.050000000745058060)
Local Coll34:TCollider = TCollider .CreateFromVects( TVector.Create( 541 , 499 )  , TVector.Create(540 , 481) , 0.050000000745058060)
Local Coll35:TCollider = TCollider .CreateFromVects( TVector.Create( 592 , 440 )  , TVector.Create(623 , 440) , 0.050000000745058060)
Local Coll36:TCollider = TCollider .CreateFromVects( TVector.Create( 623 , 440 )  , TVector.Create(624 , 461) , 0.050000000745058060)
Local Coll37:TCollider = TCollider .CreateFromVects( TVector.Create( 624 , 461 )  , TVector.Create(592 , 460) , 0.050000000745058060)
Local Coll38:TCollider = TCollider .CreateFromVects( TVector.Create( 592 , 460 )  , TVector.Create(592 , 440) , 0.050000000745058060)
Local Coll39:TCollider = TCollider .CreateFromVects( TVector.Create( 638 , 408 )  , TVector.Create(685 , 405) , 0.050000000745058060)
Local Coll40:TCollider = TCollider .CreateFromVects( TVector.Create( 685 , 405 )  , TVector.Create(686 , 441) , 0.050000000745058060)
Local Coll41:TCollider = TCollider .CreateFromVects( TVector.Create( 686 , 441 )  , TVector.Create(668 , 439) , 0.050000000745058060)
Local Coll42:TCollider = TCollider .CreateFromVects( TVector.Create( 668 , 439 )  , TVector.Create(670 , 428) , 0.050000000745058060)
Local Coll43:TCollider = TCollider .CreateFromVects( TVector.Create( 670 , 428 )  , TVector.Create(663 , 420) , 0.050000000745058060)
Local Coll44:TCollider = TCollider .CreateFromVects( TVector.Create( 663 , 420 )  , TVector.Create(652 , 419) , 0.050000000745058060)
Local Coll45:TCollider = TCollider .CreateFromVects( TVector.Create( 652 , 419 )  , TVector.Create(638 , 408) , 0.050000000745058060)
Local Coll46:TCollider = TCollider .CreateFromVects( TVector.Create( 557 , 368 )  , TVector.Create(602 , 365) , 0.050000000745058060)
Local Coll47:TCollider = TCollider .CreateFromVects( TVector.Create( 602 , 365 )  , TVector.Create(600 , 374) , 0.050000000745058060)
Local Coll48:TCollider = TCollider .CreateFromVects( TVector.Create( 600 , 374 )  , TVector.Create(557 , 375) , 0.050000000745058060)
Local Coll49:TCollider = TCollider .CreateFromVects( TVector.Create( 557 , 375 )  , TVector.Create(557 , 367) , 0.050000000745058060)
Local Coll50:TCollider = TCollider .CreateFromVects( TVector.Create( 482 , 324 )  , TVector.Create(533 , 327) , 0.050000000745058060)
Local Coll51:TCollider = TCollider .CreateFromVects( TVector.Create( 533 , 327 )  , TVector.Create(533 , 337) , 0.050000000745058060)
Local Coll52:TCollider = TCollider .CreateFromVects( TVector.Create( 533 , 337 )  , TVector.Create(481 , 332) , 0.050000000745058060)
Local Coll53:TCollider = TCollider .CreateFromVects( TVector.Create( 481 , 332 )  , TVector.Create(483 , 324) , 0.050000000745058060)
Local Coll54:TCollider = TCollider .CreateFromVects( TVector.Create( 409 , 292 )  , TVector.Create(460 , 294) , 0.050000000745058060)
Local Coll55:TCollider = TCollider .CreateFromVects( TVector.Create( 460 , 294 )  , TVector.Create(458 , 302) , 0.050000000745058060)
Local Coll56:TCollider = TCollider .CreateFromVects( TVector.Create( 458 , 302 )  , TVector.Create(408 , 299) , 0.050000000745058060)
Local Coll57:TCollider = TCollider .CreateFromVects( TVector.Create( 408 , 299 )  , TVector.Create(408 , 292) , 0.050000000745058060)
Local Coll58:TCollider = TCollider .CreateFromVects( TVector.Create( 347 , 242 )  , TVector.Create(394 , 244) , 0.050000000745058060)
Local Coll59:TCollider = TCollider .CreateFromVects( TVector.Create( 394 , 244 )  , TVector.Create(393 , 251) , 0.050000000745058060)
Local Coll60:TCollider = TCollider .CreateFromVects( TVector.Create( 393 , 251 )  , TVector.Create(345 , 247) , 0.050000000745058060)
Local Coll61:TCollider = TCollider .CreateFromVects( TVector.Create( 345 , 247 )  , TVector.Create(345 , 241) , 0.050000000745058060)
Local Coll62:TCollider = TCollider .CreateFromVects( TVector.Create( 431 , 188 )  , TVector.Create(455 , 187) , 0.050000000745058060)
Local Coll63:TCollider = TCollider .CreateFromVects( TVector.Create( 455 , 187 )  , TVector.Create(454 , 195) , 0.050000000745058060)
Local Coll64:TCollider = TCollider .CreateFromVects( TVector.Create( 454 , 195 )  , TVector.Create(430 , 195) , 0.050000000745058060)
Local Coll65:TCollider = TCollider .CreateFromVects( TVector.Create( 430 , 195 )  , TVector.Create(430 , 189) , 0.050000000745058060)
Local Coll66:TCollider = TCollider .CreateFromVects( TVector.Create( 454 , 189 )  , TVector.Create(473 , 188) , 0.050000000745058060)
Local Coll67:TCollider = TCollider .CreateFromVects( TVector.Create( 473 , 188 )  , TVector.Create(471 , 195) , 0.050000000745058060)
Local Coll68:TCollider = TCollider .CreateFromVects( TVector.Create( 471 , 195 )  , TVector.Create(453 , 194) , 0.050000000745058060)
Local Coll69:TCollider = TCollider .CreateFromVects( TVector.Create( 110 , 429 )  , TVector.Create(118 , 428) , 0.050000000745058060)
Local Coll70:TCollider = TCollider .CreateFromVects( TVector.Create( 118 , 428 )  , TVector.Create(118 , 433) , 0.050000000745058060)
Local Coll71:TCollider = TCollider .CreateFromVects( TVector.Create( 118 , 433 )  , TVector.Create(125 , 434) , 0.050000000745058060)
Local Coll72:TCollider = TCollider .CreateFromVects( TVector.Create( 125 , 434 )  , TVector.Create(124 , 438) , 0.050000000745058060)
Local Coll73:TCollider = TCollider .CreateFromVects( TVector.Create( 124 , 438 )  , TVector.Create(129 , 438) , 0.050000000745058060)
Local Coll74:TCollider = TCollider .CreateFromVects( TVector.Create( 129 , 438 )  , TVector.Create(129 , 443) , 0.050000000745058060)
Local Coll75:TCollider = TCollider .CreateFromVects( TVector.Create( 129 , 443 )  , TVector.Create(135 , 442) , 0.050000000745058060)
Local Coll76:TCollider = TCollider .CreateFromVects( TVector.Create( 135 , 442 )  , TVector.Create(136 , 448) , 0.050000000745058060)
Local Coll77:TCollider = TCollider .CreateFromVects( TVector.Create( 136 , 448 )  , TVector.Create(142 , 448) , 0.050000000745058060)
Local Coll78:TCollider = TCollider .CreateFromVects( TVector.Create( 142 , 448 )  , TVector.Create(142 , 454) , 0.050000000745058060)
Local Coll79:TCollider = TCollider .CreateFromVects( TVector.Create( 142 , 454 )  , TVector.Create(148 , 455) , 0.050000000745058060)
Local Coll80:TCollider = TCollider .CreateFromVects( TVector.Create( 148 , 455 )  , TVector.Create(149 , 460) , 0.050000000745058060)
Local Coll81:TCollider = TCollider .CreateFromVects( TVector.Create( 149 , 460 )  , TVector.Create(156 , 462) , 0.050000000745058060)
Local Coll82:TCollider = TCollider .CreateFromVects( TVector.Create( 156 , 462 )  , TVector.Create(156 , 467) , 0.050000000745058060)
Local Coll83:TCollider = TCollider .CreateFromVects( TVector.Create( 156 , 467 )  , TVector.Create(165 , 468) , 0.050000000745058060)
Local Coll84:TCollider = TCollider .CreateFromVects( TVector.Create( 165 , 468 )  , TVector.Create(166 , 472) , 0.050000000745058060)
Local Coll85:TCollider = TCollider .CreateFromVects( TVector.Create( 166 , 472 )  , TVector.Create(172 , 472) , 0.050000000745058060)
Local Coll86:TCollider = TCollider .CreateFromVects( TVector.Create( 172 , 472 )  , TVector.Create(172 , 479) , 0.050000000745058060)
Local Coll87:TCollider = TCollider .CreateFromVects( TVector.Create( 172 , 479 )  , TVector.Create(181 , 480) , 0.050000000745058060)
Local Coll88:TCollider = TCollider .CreateFromVects( TVector.Create( 181 , 480 )  , TVector.Create(181 , 484) , 0.050000000745058060)
Local Coll89:TCollider = TCollider .CreateFromVects( TVector.Create( 181 , 484 )  , TVector.Create(191 , 485) , 0.050000000745058060)
Local Coll90:TCollider = TCollider .CreateFromVects( TVector.Create( 191 , 485 )  , TVector.Create(191 , 492) , 0.050000000745058060)
Local Coll91:TCollider = TCollider .CreateFromVects( TVector.Create( 191 , 492 )  , TVector.Create(198 , 493) , 0.050000000745058060)
Local Coll92:TCollider = TCollider .CreateFromVects( TVector.Create( 198 , 493 )  , TVector.Create(198 , 497) , 0.050000000745058060)
Local Coll93:TCollider = TCollider .CreateFromVects( TVector.Create( 198 , 497 )  , TVector.Create(204 , 499) , 0.050000000745058060)
Local Coll94:TCollider = TCollider .CreateFromVects( TVector.Create( 204 , 499 )  , TVector.Create(203 , 504) , 0.050000000745058060)
Local Coll95:TCollider = TCollider .CreateFromVects( TVector.Create( 203 , 504 )  , TVector.Create(211 , 504) , 0.050000000745058060)
Local Coll96:TCollider = TCollider .CreateFromVects( TVector.Create( 211 , 504 )  , TVector.Create(212 , 508) , 0.050000000745058060)
Local Coll97:TCollider = TCollider .CreateFromVects( TVector.Create( 212 , 508 )  , TVector.Create(220 , 508) , 0.050000000745058060)
Local Coll98:TCollider = TCollider .CreateFromVects( TVector.Create( 220 , 508 )  , TVector.Create(220 , 514) , 0.050000000745058060)
Local Coll99:TCollider = TCollider .CreateFromVects( TVector.Create( 220 , 514 )  , TVector.Create(230 , 516) , 0.050000000745058060)
Local Coll100:TCollider = TCollider .CreateFromVects( TVector.Create( 230 , 516 )  , TVector.Create(230 , 519) , 0.050000000745058060)
Local Coll101:TCollider = TCollider .CreateFromVects( TVector.Create( 230 , 519 )  , TVector.Create(240 , 522) , 0.050000000745058060)
Local Coll102:TCollider = TCollider .CreateFromVects( TVector.Create( 240 , 522 )  , TVector.Create(239 , 527) , 0.050000000745058060)
Local Coll103:TCollider = TCollider .CreateFromVects( TVector.Create( 239 , 527 )  , TVector.Create(247 , 527) , 0.050000000745058060)
Local Coll104:TCollider = TCollider .CreateFromVects( TVector.Create( 247 , 527 )  , TVector.Create(247 , 531) , 0.050000000745058060)
Local Coll105:TCollider = TCollider .CreateFromVects( TVector.Create( 247 , 531 )  , TVector.Create(253 , 531) , 0.050000000745058060)
Local Coll106:TCollider = TCollider .CreateFromVects( TVector.Create( 253 , 531 )  , TVector.Create(253 , 535) , 0.050000000745058060)
Local Coll107:TCollider = TCollider .CreateFromVects( TVector.Create( 253 , 535 )  , TVector.Create(258 , 535) , 0.050000000745058060)
Local Coll108:TCollider = TCollider .CreateFromVects( TVector.Create( 258 , 535 )  , TVector.Create(258 , 540) , 0.050000000745058060)
Local Coll109:TCollider = TCollider .CreateFromVects( TVector.Create( 258 , 540 )  , TVector.Create(263 , 540) , 0.050000000745058060)
Local Coll110:TCollider = TCollider .CreateFromVects( TVector.Create( 263 , 540 )  , TVector.Create(265 , 544) , 0.050000000745058060)

Local cOrigin:TVector = TVector.Create( 244 , 468 )

'WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW


And Last an overall Test. <Test.Bmx>
<Test.Bmx>
Strict 
Include "Vector.Bmx"
Include "Rest.Bmx"
Include "CollisionDetection.Bmx"
Include "Map.Bmx"
Rem
	I found Out that if some lines are verical the collision detection its not working right
	and I get a NAN number for the sourcePoint ....
	I believe that this is somewhere in the SlidePlane...
End Rem

Const Inf:Double = 9999.0^9999.0
Const Nan:Double = (-1.0)^(0.5) 





'WWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
'WWWWWWWWWWWWWWWWWW	TEST
'WWWWWWWWWWWWWWWWWWWWWWWWWWWWW



Local GravityVector:TVector = TVEctor.create(0,8)
Global RadiusVector:TVector = TVector.create(10 , 20)
Local speed:Double = 5
Global Friction:Double = 1/12
Global touch:Byte
Local airFriction:Double  = 0.05
Local n:Double = 1/12
Local jump:Int = 0


Graphics 800 , 600 
While Not KeyDown(KEY_ESCAPE)
	Cls
	Local cVelocity:TVector = New TVector
	
	SetColor 255 , 0 , 0
	For Local _Collider:TCollider = EachIn TCollider._List
		_Collider.Draw()
	Next
	SetColor 0 , 255 , 0
	DrawOval cOrigin._x - RadiusVector._x , cOrigin._y - RadiusVector._y , RadiusVector._x * 2 , RadiusVector._y * 2	
	

	
	If KeyDown(KEY_LEFT)
		cVelocity.add(TVector.create( - speed , 0) , True)
	End If

	If KeyDown(KEY_RIGHT)
		cVelocity.add(TVector.create(speed , 0 ) , True)
	End If

		
	If KeyDown(KEY_UP) And touch = True
		jump = 10
	End If
	
	If jump > 0
		cVelocity.add(TVector.create(0 , - GravityVector._y - speed) , True)
	End If
	jump:-1
	

		
	
	scale_potential_colliders_to_ellipsoid_space(RadiusVector)
	DivideVector(cOrigin , radiusVector)
	touch = TouchTheGround(cOrigin)
	MultiplyVector(cOrigin , radiusVector)
	collisionDetection(cOrigin , cVelocity , GravityVector)
	scale_back_potential_colliders_from_ellipsoid_space(RadiusVector)
	


	SetColor 0 , 0 , 255
	cVelocity.Draw(cOrigin._x , cOrigin._y)
	DrawText "FPS : " + TFPS.getFPS(),10,10
	DrawText "Mem : " + GCMemAlloced(),10,20 
	DrawText " x : " + cOrigin._x , 10 , 30   
	DrawText " y : " + cOrigin._y , 10 , 40

	Flip 
	TFPS.Update()
Wend


Type TFPS
	Global FPS:Int  = 0
	Global Time:Int = 0
	Global frames:Int = 0
	
	Function getFPS:Int()
		Return FPS
	End Function  
	
	Function Update()
		If Time = 0 Then Time = MilliSecs()
		If MilliSecs()-Time > 999 Then 
			FPS = frames
			frames = 0  
			Time = MilliSecs()	
		Else                  
			frames:+1
		EndIf
	End Function
End Type



Be sure to create and store all the above files in the same directory. Run the test and navigate with the cursors keys. Jump with the Up arrow.
One last think the pseutocode it’s from the revision version of the document but the file CollisionDetection.Bmx contains all the code from the document. Like <’//> witch are the comments by the author and <’?> that is the code and some <’> that are mine.

Run it and see that with this way you can create much more realistic movement for you characters and you can climb stairs automatically.


I hope that I have not disturbed the community with all this because I all ready posted this stuff ( incomplete ) in the programming forum. But I believe this belongs here.

DreamLoader
 #2
this is nice!