Judging the intersection point of moving objects

Blitz3D Forums/Blitz3D Programming/Judging the intersection point of moving objects

Makepool

(Posted 2005) [#1]

Imagine you have a game where an AI player fires a projectile weapon that takes time for the projectile to travel the distance to whatever the NPC is shooting at. Now imagine the NPC is shooting at a target moving laterally to the NPC. Does any body know the equation to work out what angle the NPC should shoot at to hit the moving target?

DJWoodgate

(Posted 2005) [#2]

Well here is a link I found to some projectile aiming code. Intended for use in Unreal but you might be able to convert it to your situation.

http://wiki.beyondunreal.com/wiki/Projectile_Aiming

sswift

(Posted 2005) [#3]

I dunno if this will help you at all, but that is the sort of problem I was working on at one point in my tank game:

			; Calculate if any bullets will hit this player.
	
				Px#  = EntityX#(ThisPlayer\Avatar, True)
				Py#  = EntityY#(ThisPlayer\Avatar, True)
				Pz#  = EntityZ#(ThisPlayer\Avatar, True)

				PVx# = ThisPlayer\Vx#
				PVz# = ThisPlayer\Vz#

				PSpeed# = Sqr#(PVx#*PVx# + PVz#*PVz#)

				Bullet_Will_Collide = False
		
				For ThisBullet.Bullet = Each Bullet			

	
					Bx#  	= EntityX#(ThisBullet\Avatar, True)
					Bz#  	= EntityZ#(ThisBullet\Avatar, True)
					BVx# 	= ThisBullet\Vx#
					BVz# 	= ThisBullet\Vz#
					BSpeed# = Sqr#(BVx#*BVx# + BVz#*BVz#)	


					; Check to see if the bullet's path intersects the computer's path, and calculate where.
					If Lines_Intersect(Px#, Pz#, Px#+PVx#, Pz#+PVz#, Bx#, Bz#, Bx#+BVx#, Bz#+BVz#)


						; Are both objects heading towards the point where their paths intersect?
						If (Intersection_AB# >= 0) And (Intersection_CD# >= 0)


							; Because the length of the line segments is equal to the distance that the entities will travel
							; over a period of 1 second, the realtive intersection points tell us the time which each entity
							; will reach the collision point.  Ie, if Intersection_AB# is 1.0, then the computer will reach
							; the intersection point in exactly one second.


							; Will the computer reach the intersection point in the near future?
							If (Intersection_AB# < 2.0)
			
				
								; Calculate the difference in the arrival time of the two entites at the intersection point.
								Arrival_Time_Diffrence# = Abs(Intersection_AB# - Intersection_CD#)
				
					
								; Will both entites arrive at almost the same time at the intersection point of their paths?
								If (Arrival_Time_Diffrence# < 2.0)
												
								
									; It's very likely that the computer is going to collide with the bullet if it keeps
									; moving in this direction.
						
									;EntityColor ThisPlayer\Avatar, 0, 255, 0
					
									Bullet_Will_Collide = True	
					
								EndIf
					
							EndIf		
				
						EndIf				
					
					EndIf			
											
				Next

Some thoughts:

For each point along the player's line of motion, there is a time it takes for the player to get there.

And each those points will also have a time for the bullet to get there.

You need to find the point where these two times are equal.

You need to find the point on the line which the player and bullet will be at at the same point in time.

Andy	(Posted 2005) [#4]

Create a pivot(a) and attach another pivot(b) to it.

Move pivot b further out on one axis the faster the model moves and always orient it in the direction the model is moving. point the gun towards pivot b.

Andy

Viperfish

(Posted 2005) [#5]

I'm working on a space shooter in which all craft have completely free 360 degree movment. And I had this problem. When the enemy shoot (at the player) how do they know how much to lead the target by?

It took me a long time but it can be solved with 1 formula.

Create a pivot in front of the target entity. Call it TargetLeader. This entity is always directly infront and moves in and out depending on the following formula. The attacking entity will by firing at this pivot. Create a field in the attacking entity's type called 'leader' ie 'e\leader'.

You will need the following variables.

myspeed (forward speed of the target entity.)
EnemyBulletSpeed (forward speed of the attacking entity's projectile)

Here's the formula ('pvt' is the target pivot).

e\leader = (e\leader/((e\leader/myspeed)-(EntityDistance(e\entity,TargetLeader)/EnemyBulletSpeed)+(EntityDistance(e\entity,pvt)/EnemyBulletSpeed)))*(EntityDistance(e\entity,pvt)/EnemyBulletSpeed)
PositionEntity targetleader,0,0,e\leader

The value assigned to 'e/leader' by this formula is the distance the TargetEntity should be set infront of the target. Then orientate your attacking craft towards the TargetLeader. If the attacking craft fires at this point it will hit every time.

How does it work? I wrote this a few months ago now. But basically it works out;
1. The time it will take fot the targetentity to reach the TargetLeaders position set last frame.
2. the time it will take for the enemybullet to travel to the target entity's actual position.
3. The time is will take for the enemybullet to travel to TargetLeaders Position.

It first works out how long it will take for the attacking crafts bullet to reach the targets current position.(EntityDistance(e\entity,pvt)/EnemyBulletSpeed)
This target is moving so it will get there too late and miss. If we fire at the Target Leader how long will it take? (EntityDistance(e\entity,TargetLeader)/EnemyBulletSpeed)
Then it works out how far the target will have travelled in that time (EntityDistance(e\entity,pvt)/EnemyBulletSpeed). With these three values we can now calculate the distance TargetLeader needs to be infront of the target.

It's a complicated formula and there is probably an easier way. Some methods, like Andy's method above takes the entity's speed into consideration but it doesn't take into consideration the attackers distance or the speed of the projectile. The further away the attacker is the further out the leader needs to be. The faster the projectile the closer it needs to be. This formula wraps it all together.

Anyway, I'm rambling now and this may not even be what you need. But, I hope it helps.

EDIT: Make sure you set an initial value to e\leader. It can be anything as long as it's not zero. If you leave it at zero it will never change!

Makepool

(Posted 2005) [#6]

Thanks for the responses, I don't have time to test any off the ideas given as I'm really busy with uni work but in the next few weeks I hope to get things sorted.

DJWoodgate

(Posted 2005) [#7]

Well I have just unravelled Johns formula and it certainly seems pretty good at getting a solution for objects moving at a fixed speed and constant direction. Here is a simple testbed.

Graphics3D 800,600,0,2

SeedRnd MilliSecs()
HidePointer
Const NUMWAYPOINTS=20
Const FIRETIME=200
Const NUMTARGETS=25
Const FIRERANGE#=100
Const FIRESPEED#=4
Const TARGETMAXSPEED#=1
Const TARGETMINSPEED#=0.2

Global Targetcount,ShellCount

Type target
Field entity
Field speed#
Field Leader
Field waypoint.waypoint
End Type

Type waypoint
Field pivot
End Type

Type Vector
Field x#,y#,z#
End Type

Type Shell
Field entity
Field speed#
Field range#
End Type

Type gun
Field Entity
Field bulletspeed#
Field target.target
Field leader#
End Type


shell=CreateCylinder(8,True) : RotateMesh shell,90,0,0
ScaleEntity shell,0.2,0.2,0.2
EntityRadius shell,0.25
EntityType shell,1
HideEntity shell


Dim waypoints.waypoint(NUMWAYPOINTS)

For i=1 To NUMWAYPOINTS

waypoints(i)=New waypoint
waypoints(i)\pivot=CreatePivot()

Repeat
	mindist#=10000
	PositionEntity waypoints(i)\pivot,Rnd(-30,30),Rnd(-30,30),Rnd(30,80)
	For j=1 To i-1
		dist#=EntityDistance(waypoints(i)\pivot,waypoints(j)\pivot)
		If dist<mindist Then mindist=dist
	Next
Until mindist>10

Next

For i=1 To NUMTARGETS
	t.target=New target
	targetcount=targetcount+1
	If i=1 Then
		entity=CreateCone()
		RotateMesh entity,90,0,0
		EntityType entity,2
		leader=CreatePivot(entity)
	Else
		entity=CopyEntity(entity)
	EndIf
	t\entity=entity
	t\leader=GetChild(entity,1)
	t\speed=Rnd(TARGETMINSPEED,TARGETMAXSPEED)
	EntityColor t\entity,255,255*t\speed,0
	PositionEntity t\entity,Rnd(-30,30),Rnd(-30,30),Rnd(30,60)
	t\waypoint=waypoints(Rand(1,NUMWAYPOINTS))
Next

cam=CreateCamera()

light=CreateLight()
RotateEntity light,45,45,0

gun.gun=New gun
gun\entity=cam
gun\bulletspeed=FIRESPEED
gun\leader=1.0

vec.vector=New vector

plane=CreatePlane(1,cam)
EntityPickMode plane,2
EntityAlpha plane,0
RotateEntity plane,-90,0,0
PositionEntity plane,0,0,10
point=CreatePivot()
manualfire = True
Collisions 1,2,1,1

Repeat

For t.target=Each target

	If EntityDistance(t\Entity,t\waypoint\pivot)<t\speed*5 Then t\waypoint=waypoints(Rand(1,NUMWAYPOINTS))
	If t\waypoint = Null Then t\waypoint=First waypoint
	
	DeltaVec(t\entity,t\waypoint\pivot,Vec)
	
	AligntoVec(t\entity,Vec,3,0.1)
	
	MoveEntity t\entity,0,0,t\speed
Next

t.target=First target


If KeyHit(57) Then manualfire=Not manualfire

mx=MouseX() : my=MouseY()


If manualfire Then 
	If MouseDown(1)>0 And MilliSecs()>firetimer Then
		Firetimer=MilliSecs()+FIRETIME
		CameraPick cam,mx,my
		PositionEntity point,PickedX(),PickedY(),PickedZ()
		s.shell=New shell
		shellcount=shellcount+1
		s\speed=gun\bulletspeed
		s\entity=CopyEntity(shell)
		PointEntity s\entity,point
	EndIf
Else 
	If gun\target=Null Then
		gun\target=First target
	EndIf
	
	If gun\target<>Null Then
		TargetLeader=gun\target\leader
		TargetEntity=gun\target\entity
		EntityColor targetentity,0,0,255
		GunEntity=gun\entity
	
		Targetspeed#=gun\target\speed		
		BulletSpeed#=gun\bulletspeed

		TargetTime#=EntityDistance(GunEntity,TargetEntity)/Bulletspeed
		LeaderTime#=EntityDistance(GunEntity,TargetLeader)/Bulletspeed
		
		gun\leader=gun\leader/((gun\leader/Targetspeed) - LeaderTime + TargetTime) * TargetTime
		
		PositionEntity Targetleader,0,0,gun\leader

		CameraProject cam, EntityX(targetleader,1),EntityY(targetleader,1),EntityZ(targetleader,1)
		mx=ProjectedX() : my=ProjectedY()
		If MilliSecs()>firetimer Then
			Firetimer=MilliSecs()+FIRETIME
			s.shell=New shell
			shellcount=shellcount+1
			s\speed=bulletspeed
			s\entity=CopyEntity(shell)
			PointEntity s\entity,targetleader
		EndIf
	EndIf

EndIf

For s.shell=Each shell
	If CountCollisions(s\entity)>0 Then
		entity=CollisionEntity(s\entity,1) 
		For t.target=Each target
			If t\entity=entity Then
				FreeEntity  t\entity
				Delete t
				targetcount=targetcount-1
				FreeEntity s\entity
				Delete s
				shellcount=shellcount-1
			EndIf 
		Next
	ElseIf s\range>FIRERANGE Then 
		FreeEntity s\entity
		Delete s
		shellcount=shellcount-1
	Else
		MoveEntity s\entity,0,0,s\speed
		s\range=s\range+s\speed
	EndIf
Next

UpdateWorld
RenderWorld

Rect mx-4,my-4,8,8,False

Text 0,0,"Targets="+targetcount+". Shells="+Shellcount
Text 0,12,"Hit space key to toggle auto fire"
Flip
Until KeyDown(1)

Function DeltaVec(source,target,v.vector)
v\x=EntityX(target,1)-EntityX(source,1)
v\y=EntityY(target,1)-EntityY(source,1)
v\z=EntityZ(target,1)-EntityZ(source,1)
End Function

Function AligntoVec(source,v.vector,axis=3,rate#=1)
AlignToVector source,v\x,v\y,v\z,axis,rate
End Function

Viperfish

(Posted 2005) [#8]

Heres a link to a download of my game in which the enemy AI uses the above formula. It's a couple of months old now and has gone through a lot of changes since this upload. But you will be able to see the AI in action. When you leave the space station, start shooting at other craft and pretty soon you will be fired at and turned into space junk.

http://www.blitzcoder.com/cgi-bin/showcase/showcase_showentry.pl?id=bigjohnno03142005145609&comments=no

Chroma

(Posted 2005) [#9]

I was also working on some code like this for an AA gun. This is what I came up with:

1. find the speed and vector of the object being shot at
2. find the distance between the shooter and victim
3. calculate the time it will take for the bullet to arrive
4. find the predicted spot based on speed, vector, time
5. aim and shoot at the predicted spot