Intersepting moving target

Blitz3D Forums/Blitz3D Programming/Intersepting moving target

Jack(Posted 2009) [#1]
Hope I can explain what I need so it makes sense....

Considering only two positions x and y and two moving objects called a and b.....

Lets say A is location x10 and y10.(pixel values)
And say B is location x45 and y10.(pixel values)
A is moving 1 pixel per loop and b is moving .7 pixels per loop. Heading to a higher Y location and in a straight line.(x is constant for B)

Just a simple example...a first step.Next I want to calculate constantly changing headings but I'll get to that later.

At what X and Y locations will the intersect.

Hope can be understood.

Thanks


Ross C(Posted 2009) [#2]
You need a line intersect equation. There are quite a few in the code archive.

I imagine you'd need to first calculate if the two paths would cross each other, regardless of speed. However, you want to intercept a moving target, it seems. So, i presume you will be adjusting the heading and speed on one of the objects?


Ginger Tea(Posted 2009) [#3]
why does that read like one of those maths problems
train a leaves the station at 8:45 and is traveling at 85mph
train b leaves the station at 7:45 and is traveling at 60mph
at what point do they pass

i always wanted to say "train? on time?" and "well due to rail works train b cannot go via this station so will not pass train a on any point of the track"


GIB3D(Posted 2009) [#4]
Well due to Train A being in the year 1990 and Train B being in the year 2058, I'd say they would never pass.


Jack(Posted 2009) [#5]
Ross C ---- yes actually both will be able to change direction but my first
concern was to get A to locate B which will (for now) be moving only in the Y direction away from A. Eventually I want to be able for a to adjust direction based on B changing direction.

I am not very knowledgeable on this type math but after finding some line intersect stuff in the code archives I did not find any I understood that took speed into consideration. "lineintersect equation" did not turn up anything in the code archives but maybe it is somewhere in the "lineintersect" codes I did find.


Jack(Posted 2009) [#6]
Do Ginger Tea and GIA_Green_Fire have anything helpfull or are they working with there flash cards. Gimmie a break guys.


Jasu(Posted 2009) [#7]
I don't really understand your example, but are you trying to find out if and when distance between A and B is zero? Not if their paths cross? That happens always unless the paths are parallel. In case you want to find a possible collision point, you are talking about a quadratic equation, since distance of the two objects create a parabola (unless paths are again parallel and heading in the same direction = distance is constant). The parabola is not created by x axis and y axis, but distance and time. Description would be like, 'what is the distance between the two objects at given time?'

This is not simple math, but not impossible for a regular coder. I solved a problem like this in my game where I had to make AI shoot targets in advance, considering direction and speed of the target and speed of the bullet.


Bobysait(Posted 2009) [#8]
You need to check the solution of yA+yB=0 according to points and directionnal vector for the two points

According, you 've got two lines, each defined by a point and a vector
Let's call them I{Xi,Yi} and J{Xj,Yj} , and Vi{viX,ViY}, Vj{VjX,VjY} the vector for those lines
Yi=A1*Xi+C1
Yj=A2*Xj+C2

We can Find A1 and A2 :
A1# = ViY/ViX
A2# = VjY/VjX

you might want to know first if they really intersect +> not //
if Vectors are colinear, then they won't cross.
+> If A1=A2 then they are colinear

Else :
we want to find C1 and C2 :
C1 = Yi - A1*Xi
C2 = Yj - A2*Xj

Now, We can find the intersection point solving Y(j)=Y(i)
A1*X + C1 = A2*X + C2
-> C1-C2 = A2*X - A1*X
-> X = (C2-C1)/(A1-A2)

To resolve Y, just use any of I and J .
Y = A1*X +C1 ( using the X solved above )

We have the point K {X,Y} intersection point of the two lines.

next Step : check the time that take point I and J to go to the Point K

DistI# = Sqr( (X-Xi)*(X-Xi) + (Y-Yi)*(Y-Yi) )
DistJ# = Sqr( (X-Xj)*(X-Xj) + (Y-Yj)*(Y-Yj) )

Then, you take the mag for vector to establish "when" they arrive
MagVi# = sqr(ViX*ViX+ViY*ViY)
MagVj# = sqr(VjX*VjX+VjY*VjY)
NbI = MagVi/DistI
NbJ = MagVj/DistJ

If Nbi=Nbj then the "I" and "J" will meet at "K"

And, now, You just arrived to create your first collision avoidance test. :)


AJ00200(Posted 2009) [#9]
Is this what you want?
EDIT: Boby got their first
x1#=20
y1#=10
x2#=45
y2#=10
go = True

Rect(x1, y1, 2, 2)
Rect(x2, y2, 2, 2)
While go
  Cls
  x1 = x1 + 1
  x2 = x2 + 0.7
  Rect(x1, y1, 2, 2)
  Rect(x2, y2, 2, 2)
  If (Floor(x1) = Floor(x2)) Then
    Print("A: " + x1 + ", " + y1)
    Print("B: " + x2 + ", " + y2)
    WaitKey()
    End
  End If
  Delay(75)
Wend
WaitKey()



Warpy(Posted 2009) [#10]
I'm assuming you want to know when two objects collide and not just if they cross paths. Next, if you want to know how to aim something to hit a moving target, I've covered this on my blog.

It's just about as complicated to explain the general case as for this particular example, so I'll just do that.

First of all, the conventional way of writing down co-ordinates is in the form (X,Y), where X is the number of pixels in the x-axis from the left of the screen, and Y is the number of pixels in the y-axis from the top of the screen. Note that the y-axis goes down instead of up on a computer screen, because of the way monitors used to be made.

Suppose A is at co-ordinates (ax,ay) and moving (avx, avy) pixels every loop, and that B is at co-ordinates (bx,by) and moving (bvx,bvy) pixels every loop.
What this means is each loop you move A avx pixels in the x-axis and avy pixels in the y-axis, and it's the same idea for B.

After you've done t loops, A is at (ax+ t * avx, ay + t * avy), and B is at (bx + t * bvy, by + t * bvy).

The positions of A and B depend only on t, so you want to find the value of t when A and B are at the same co-ordinates.
You do this by comparing A's x co-ordinate to B's x co-ordinate, and A's y co-ordinate to B's y co-ordinate:

ax + t * avx = bx + t * bvx
ay + t * avy = by + t * bxy

As we only need to find one variable, we only need to solve one of these. This is because we're assuming that the objects DO hit each other. If they don't, the solutions for each equation will be different, which doesn't make much sense.

Let's rearrange the first equation to find t:

t = (bx - ax) / ( avx - bvx )

You can then put t back into the co-ordinates of A and B to find the position where the collision occurs.


Hope this was helpful, you didn't make it terrfifically clear what exactly you were trying to do


Bobysait(Posted 2009) [#11]
Here is an implementation of the description below

Graphics 800,600,0,2
SetBuffer BackBuffer()


; points
Local A#[2],Va#[2]
Local B#[2],Vb#[2]
	A[0]=200:A[1]=250
	B[0]=300:B[1]=400

; Intersection Point
Local I#[2]

; vectors
	Local MagA# = 5.2
	Local MagB# = 9.5
	Va[0]=.2  : Va[1]=.9
	Vb[0]=.5 : Vb[1]=.5

Local Vx#=0.0
Local Vy#=0.0
Local N#=1.0

Repeat

	If MouseHit(1)
		A[0]=MouseX()
		A[1]=MouseY()
	ElseIf MouseDown(1)
		Vx=MouseX()-A[0]
		Vy=MouseY()-A[1]
		N=Sqr(Vx*Vx+Vy*Vy)
		Va[0]=MagA*Vx/N
		Va[1]=MagA*Vy/N
	EndIf
	If MouseHit(2)
		B[0]=MouseX()
		B[1]=MouseY()
	ElseIf MouseDown(2)
		Vx=MouseX()-B[0]
		Vy=MouseY()-B[1]
		N=Sqr(Vx*Vx+Vy*Vy)
		Vb[0]=MagB*Vx/N
		Vb[1]=MagB*Vy/N
	EndIf

	Local Res%=VectorIntersect(I, A,Va,B,Vb)
	Local CrossTimeA# = 0
	Local CrossTimeB# = 0

	If Res=1
		Local DistA#=Sqr( (A[0]-I[0])*(A[0]-I[0]) + (A[1]-I[1])*(A[1]-I[1]) )
		Local DistB#=Sqr( (B[0]-I[0])*(B[0]-I[0]) + (B[1]-I[1])*(B[1]-I[1]) )
		CrossTimeA = DistA/MagA
		CrossTimeB = DistB/MagB
	EndIf

	Cls
		Color 255,128,000
			DrawPoint(A,"A "+CrossTimeA)
			Drawvector(A,Va,800 ,True)
		Color 000,128,255
			DrawPoint(B,"B "+CrossTimeB)
			Drawvector(B,Vb,800 ,True)
		If Res
			Color 255,255,000
			If Abs(CrossTimeA-CrossTimeB)<.25	Color 255,0,0
			DrawPoint(I,"I")
			Text 10,10,I[0]
			Text 10,25,I[1]
		EndIf
	Flip
Until KeyHit(1)
End


Function DrawPoint(P#[2],name$)
	Rect P[0]-3,P[1]-3,7,7,0
	Text P[0]+15,P[1]+15,name
End Function

Function Drawvector(P#[2],Vp#[2],VectorSize#=100, DoubleSens%=False)
	Local d#=VectorSize/Sqr(Vp[0]*Vp[0]+Vp[1]*Vp[1])
	If DoubleSens
		d1=-d
		Line P[0]+Vp[0]*d1, P[1]+Vp[1]*d1, P[0]+Vp[0]*d,P[1]+Vp[1]*d
	Else
		Line P[0],P[1], P[0]+Vp[0]*d, P[1]+Vp[1]*d
	EndIf
End Function


; return 1 if intersection
; return 0 if rays are superimposed
; return -1 if rays are colinear
; Intersection Point is registered in Res[2] with Res[0] = X, and Res[1] = Y

Function VectorIntersect(Res#[2], P1#[2],V1#[2], P2#[2],V2#[2])

	;[Block] Rem :
	; 1/ basic equation for Ray/Line :
	; --------------------------------
	;	 Y = A*x + C = 0
	;
	;		for a line defined with P#[2] and V#[2] :
	;		A = V[1]/V[0]
	;
	;		now we have :
	;		Y = V[1]/V[0] * X + C
	;
	;		for X=P[0] :
	;			P[1] = (V[1]/V[0]) * P[0] + C
	;
	;		then we can calculate C :
	;			C=  P[1] - P[0] * V[1]/V[0]
	;
	;	! We have defined the equation for our lines !
	;
	;
	; 2/ Now we're going to check intersection Point :
	; ------------------------------------------------
	;		{ with : 
	;			y1 = a1*x + c1
	;			y2 = a2*x + c2
	;		}
	;	 we already know :
	;		a1, c1 , a2 , c2
	;		And For Each ray, a couple of coordinates that match the eqution ( the points given For P1 And P2 )
	;
	;	 We test for any X : y1=y2
	;
	;		a1*x+c1 = a2*x+c2
	;		a1*x-a2*x = c2-c1
	;		x*(a1-a2) = c2-c1
	;		x = (c2-c1)/(a1-a2)
	;
	;		We can use P1 or P2 to calculate Y :
	;		just using y =  a1*x+ b1.
	;
	;	/!\  if a1=a2 ( -> colinear -> No intersection. )
	;		 |
	;		 |-> if b1=b2	(V1) = (V2)
	;		 |-> if b1<>b2	(V1) // (V2)
	;[End Block]

	Res[0]=0
	Res[1]=0

	If Abs(V1[0]-V2[0])<.001
		If Abs(V1[1]-V2[1])<.001 Return -1
		Return 0
	EndIf

	; simple case 1 : V1[1]=0  or V1[2]=0
	If V1[1]=0
		; here we just solve X for Y=P1[1]
		Res[1] = P1[1]
		; Thales ! +> Vay/ (Yb-Ya) = Vax / (Xb-Xa) ; we know that Yb = Yi , so we can find Xi !
		; Xi = Xa + Vax * n [ with n = (Yb-Ya ) / Vay ]
		; Xi = Xa + (Yi-Ya)*(Vax/Vay)
		Res[0] = P2[0] + (P1[1]-P2[1]) * (V2[0]/V2[1])
		Return 1
	ElseIf V2[1]=0
		; here we just solve X for Y=P2[1]
		Res[1] = P2[1]
		Res[0] = P1[0] + (P2[1]-P1[1]) * (V1[0]/V1[1])
		Return 1
	EndIf

	; simple case 2 : V1[0]=0  or V1[0]=0
	If V1[0]=0
		; here we just solve X for Y=P1[1]
		Res[0] = P1[0]
		Res[0] = P2[1] + (P1[0]-P2[0]) * (V2[1]/V2[0])
		Return 1
	ElseIf V2[0]=0
		; here we just solve X for Y=P2[1]
		Res[0] = P2[0]
		Res[0] = P1[1] + (P2[0]-P1[0]) * (V1[1]/V1[0])
		Return 1
	EndIf

	; C= Y + x*A
	Local C1# = P1[1] - P1[0] * V1[1]/V1[0]
	Local C2# = P2[1] - P2[0] * V2[1]/V2[0]

	; x= (c2-c1)/(a1-a2)
	Res[0] = ( C2 - C1 ) / ( (V1[1]/V1[0]) - (V2[1]/V2[0]) )
	; y1 = a1*X1 + c1
	Res[1] = Res[0]*V1[1]/V1[0] + C1

	Return 1

End Function


MouseHit 1 +> Set position for A
MouseDown 1 +> Set Vector for A ( not magnitude )
MouseHit 2 +> Set position for B
MouseDown 2 +> Set Vector for B ( not magnitude )

If line cross AT THE SAME TIME , then it will be colored in red, else yellow

coordinates for I ( intersection Point ) are drawn in top left.


Jack(Posted 2009) [#12]
Wow.....Bobbysait and Warpy .......Thanks for all the effort in your replies.
Thanks to RossC too.

Just great that people would put forth such effort ot aid a math retard. I'm not new to programming in Blitz by the way.

I'll put this to use now and post again later.

By the way. I want to point A at B and since B will be moving and able to change direction I will need to recalculate after each loop. Yo my way of thinking that pretty much makes it impossible to look at a future location of B. Just for info I am NOT working on some kind of SHOOTER.


Stevie G(Posted 2009) [#13]
Perfect timing. I'm just getting onto improving the AI in my curent game and was in the process of working on the targetting for the CPU players.

I hope you don't consider this a hijack as I'm thinking along similar lines:

I need to know the coords of where a turret needs to aim in order to then adjust gun elevation as well as it's yaw rotation. At the moment I assume that the turret is static, get the time which the bullet will take to get to the target's current position, based on bullet speed. I then adjust where the turret aims by adding ( time * target velocity ) to the target's current position. It works not bad although always just behind the target which makes sense. I want it to be almost perfect and then dumb it down. Anyone have any tips?


AJ00200(Posted 2009) [#14]
@Stevie G - Have a random offset, or a random delay in the shot.


Bobysait(Posted 2009) [#15]

By the way. I want to point A at B and since B will be moving and able to change direction I will need to recalculate after each loop. Yo my way of thinking that pretty much makes it impossible to look at a future location of B. Just for info I am NOT working on some kind of SHOOTER.



If B move with a "Max" value, you can estimate the amount of V that A would have to reach to join B. Then, it gives you the number of loop that you need to do it.
If A need 10 loops to join B, you can be pretty sure that you can calculate the interset only once every 4 or 5 loops.


Who was John Galt?(Posted 2009) [#16]
at what point do they pass
London Marylebone?


GIB3D(Posted 2009) [#17]
@Jack
I was attempting to be uselessly funny.