Collision course

Blitz3D Forums/Blitz3D Programming/Collision course

MuffinRemnant(Posted 2004) [#1]
With two entities moving on the x/z plane what's the easiest (!) way to check if they are on a collision course (disregarding their speed of movement)?


slenkar(Posted 2004) [#2]
entitypick


MuffinRemnant(Posted 2004) [#3]
Sorry, I'll rephrase the question...

How can I tell if the two entities trajectories cross?


Genexi2(Posted 2004) [#4]
Maybe create a function to give the distance between two entities with the value of the trajectories added in?


Jeppe Nielsen(Posted 2004) [#5]
In a plane two entities trajectories will always intersect, unless they are parallel. This might be of interest since your are only testing in a plane (2d):
http://www.blitzbasic.co.nz/codearcs/codearcs.php?code=471


MuffinRemnant(Posted 2004) [#6]
Jeppe, I understand what you're saying but that intersection could be 'in the past' and therefore not relevant. Checking that codearc... Thanks!

Genexi2, yea but I want something simpler(faster) than that :)


jfk EO-11110(Posted 2004) [#7]
erm... nothing :)


Bot Builder(Posted 2004) [#8]
plus that won't work if their movin fast enough. Your not getting much simpler.


Jeppe Nielsen(Posted 2004) [#9]
Here you go :)
Uses the function from the above mentioned code archive:
;How to predict if two entities will collide, not taking their speed into consideration
;By Jeppe Nielsen 2004
;Lines_intersect function by sswift

; Values returned by the Lines_Intersect() function.
Global Intersection_X#									
Global Intersection_Y#
Global Intersection_AB#
Global Intersection_CD#

Graphics3D 800,600,16,2

SeedRnd MilliSecs()
cam=CreateCamera()

PositionEntity cam,0,400,0
RotateEntity cam,90,0,0
CameraZoom cam,5

Global ent1=CreateCube() : EntityFX ent1,1
Global ent2=CreateCube() : EntityFX ent2,1

Global intersectsphere=CreateSphere()
EntityColor intersectsphere,255,255,0
EntityFX intersectsphere,1
HideEntity intersectsphere

PositionEntity ent1,20,0,10
RotateEntity ent1,0,45,0
PositionEntity ent2,0,0,-20
RotateEntity ent2,0,0,0

	Repeat
	
	MoveEntity ent1,0,0,0.1
	MoveEntity ent2,0,0,0.1
	
	If KeyHit(57)
	
		resetentities
	
	EndIf
	
	RenderWorld
	
	Text 400,10,"Space to reset entities",1
	Text 400,20,"Flashing yellow sphere indicates intersection point",1
	
	If CollisionCourse(ent1,ent2)
	
		Text 400,300,"ENTITIES ARE ON A COLLISION COURSE!",1,1
		
		If Sin(MilliSecs()*5)>0
			ShowEntity intersectsphere
		Else
			HideEntity intersectsphere
		EndIf
		
		PositionEntity intersectsphere,Intersection_X#,0,Intersection_Y#
		
	Else
	
		HideEntity intersectsphere
	
	EndIf
	
	Flip
	
Until KeyDown(1)
End

Function resetentities()
	
	PositionEntity ent1,Rnd(-20,20),0,Rnd(-20,20)
	RotateEntity ent1,0,Rnd(360),0
	PositionEntity ent2,Rnd(-20,20),0,Rnd(-20,20)
	RotateEntity ent2,0,Rnd(360),0
	
End Function

Function CollisionCourse(e1,e2)
	
	x1#=EntityX(e1,1)
	z1#=EntityZ(e1,1)
	
	TFormVector 0,0,1,e1,0
	
	dx1#=TFormedX()
	dz1#=TFormedZ()
	
	x2#=EntityX(e2,1)
	z2#=EntityZ(e2,1)
	
	TFormVector 0,0,1,e2,0
	
	dx2#=TFormedX()
	dz2#=TFormedZ()
	
	
	;if trajectories are parallel
	If Lines_Intersect(x1,z1,x1+dx1,z1+dz1,x2,z2,x2+dx2,z2+dz2)=False
	
		Return False
	
	Else
	
	Return Intersection_AB#>=0 And Intersection_CD#>=0
	
	EndIf
	
End Function


;function by sswift
Function Lines_Intersect(Ax#, Ay#, Bx#, By#, Cx#, Cy#, Dx#, Dy#)
  

	Rn# = (Ay#-Cy#)*(Dx#-Cx#) - (Ax#-Cx#)*(Dy#-Cy#)
        Rd# = (Bx#-Ax#)*(Dy#-Cy#) - (By#-Ay#)*(Dx#-Cx#)

	If Rd# = 0 
		
		; Lines are parralel.

		; If Rn# is also 0 then lines are coincident.  All points intersect. 
		; Otherwise, there is no intersection point.
	
		Return False
	
	Else
	
		; The lines intersect at some point.  Calculate the intersection point.
	
                Sn# = (Ay#-Cy#)*(Bx#-Ax#) - (Ax#-Cx#)*(By#-Ay#)

		Intersection_AB# = Rn# / Rd#
		Intersection_CD# = Sn# / Rd#

		Intersection_X# = Ax# + Intersection_AB#*(Bx#-Ax#)
         	Intersection_Y# = Ay# + Intersection_AB#*(By#-Ay#)
			
		Return True
		
	EndIf


End Function



Almo(Posted 2004) [#10]
This formula handles the full 3D case.

http://mathworld.wolfram.com/Line-LineDistance.html

This gives the distance between the two points on two lines that are closest to one another. If this distance doesn't allow the two objects to pass one another, then they are on a collision course.


SoggyP(Posted 2004) [#11]
Hi folks,

Would using the 3d-lines code in the archive help at all? Just wondering...

Later,

Jes


Jeppe Nielsen(Posted 2004) [#12]
Did you try out my code, in my above post? :)
I think it does solve the problem.


MuffinRemnant(Posted 2004) [#13]
Jeppe, yes thank you that'll do the trick nicely with a bit of reworking to fit :)


AlmoAtAcclaim, that looks interesting but might be overkill for my purposes - useful nevertheless, thank you.


Jeppe Nielsen(Posted 2004) [#14]
You´re welcome :-)
You only need the CollisionCourse(), and Lines_intersect() functions to do what you want, I think.