October 17, 2021, 11:25:18

### Author Topic: [bb] General solution to the lead target problem by Matty [ 1+ years ago ]  (Read 1655 times)

#### BlitzBot

• Jr. Member
•  • Posts: 1 ##### [bb] General solution to the lead target problem by Matty [ 1+ years ago ]
« on: June 29, 2017, 00:28:42 »
Title : General solution to the lead target problem
Author : Matty
Posted : 1+ years ago

Description : Okay...I posted another function a little earlier which was for a specific situation.

This code is more general.

Assuming you have two entities moving in any direction at a constant speed then there may exist a direction to fire a bullet which has a fixed muzzle speed which will hit the target.

Eg....think of air combat games where you need to lead the target in order to hit it.  This will solve that problem of where to aim.

Note there are cases where no solution exists.   This is documented in the code.

I've included an example.

The maths behind it is based on parametrising the position vectors in terms of time, then applying a constraint of a fixed muzzle velocity and solving for the time since we now have an additional degree of freedom required.   The equation to solve ends up being the quadratic formula but in 3 dimensions.

Have a look below for yourself.

Code :
Code: BlitzBasic
1. ;Function to find the velocity needed to hit a moving target, from a moving platform for a fixed muzzle velocity.
2. ;Because of the constraint of a fixed muzzle velocity we need a degree of freedom, in this case I have chosen the
3. ;time to hit the target, though another possibility would have been the velocity of the moving platform - however in
4. ;practice this is less easy to control for.
5. ;
6.
7.
8. ;Note only calculateMuzzleVelocity is useful for the end user....the other functions are for internal use only.....
9.
10.
11. Dim MuzzleVelocity#(3) ;unfortunately because I cannot return an array with a blitz3d/plus function I have to define an array to receive the values from the function...if there is
12.                                                 ; a better solution I don't know it.....banks are nice but lead to memory leaks if forgotten about, types are overkill for this.....alternatively returning
13.                                                 ;a comma separated string would work but be highly inefficient......
14.
15.
16. ;simple example... Works in both 2D and 3D.....
17. example2D()
18.
19.
20. Function calculateMuzzleVelocity(posx#,posy#,posz#,velx#,vely#,velz#,targetx#,targety#,targetz#,targetvelx#,targetvely#,targetvelz#,maximummuzzlevel#)
21. ;Pass in the values above....should make perfect sense....
22. ;
23. ;Positions of platform (posx,posy,posz), velocities of platform (velx,vely,velz)
24. ;Positions of target (targetx,targety,targetz), velocities of target (targetvelx,targetvely,targetvelz)
25. ;
26. ;Maximum muzzle velocity - ie the maximum speed the bullet is allowed to travel at - not including any acquired velocity from the moving platform.....
27. ;
28. ;Returns:
29. ;
30. ;false if unable to hit target (and does not alter contents of array)
31. ;
32. ;true if able to hit target (and populates array with velocity in x,y,z directions...)
33. ;Oh...the 3rd index in muzzle velocity is actually the time - not a spatial coordinate....useful number to have
34. ;
35.
36.
37.
38. T# = getT(getD(targetx,posx),getD(targety,posy),getD(targetz,posz),getVD(targetvelx,velx),getVD(targetvely,vely),getVD(targetvelz,velz),maximummuzzlevel)
39. If(T=-1 Or T=0) Then
40.         ;;not possible to hit target....
41.         Return False
42. EndIf
43.
44. MuzzleVelocity(0) = getVm(targetx,posx,targetvelx,velx,T)
45. MuzzleVelocity(1) = getVm(targety,posy,targetvely,vely,T)
46. MuzzleVelocity(2) = getVm(targetz,posz,targetvelz,velz,T)
47. MuzzleVelocity(3) = T
48. Return True;
49.
50.
51. End Function
52.
53.
54.
55.
56.
57. Function getVm#(target#,platform#,vtarget#,vplatform#,T#)
58. ;used in all 3 coordinate axes...hence no specific axis mentioned...
59. ;do not call for T=0....
60. ;
61. ;Technically - you shouldn't need to call this - it is another helper function like the ones below..
62. ;
63. ;
64. ;
65. ;Parameters
66. ;
67. ;target = position of target on axis
68. ;platform = position of target on axis
69. ;vtarget = velocity of target on axis
70. ;vplatform = velocity of target on axis
71. ;
72. ;Return value
73. ;
74. ;Muzzle velocity along the axis required to hit target at time T. (T is calculated elsewhere...see further down)
75. ;
76.
77.
78.
79. If(T<>0) Then
80.         Return (target - platform + (vtarget - vplatform)*T)/T
81. EndIf
82.
83. End Function
84.
85.
86. Function getD#(target#,platform#)
87. ;helper function...no need to call this...effectively a private method
88.
89. Return target - platform
90.
91. End Function
92. Function getVD#(vtarget#,vplatform#)
93. ;unfortunate name for a function but oh well...don't worry you won't need to call this...another private method...
94.
95. Return vtarget - vplatform
96.
97. End Function
98.
99.
100.
101.
102. Function getT#(Dx#,Dy#,Dz#,VDx#,VDy#,VDz#,L#)
103. ;function to calculate the appropriate time needed to satisfy the equation.
104. ;Note - sometimes there is no solution, and sometimes there is multiple solutions and sometimes there is a single solution.
105. ;When there is more than one solution there may be a nonsensical solution - this is ignored.
106. ;In the event there are two realistic solutions then the earlier one is returned...
107. ;
108. ;Note - you should never have to call this function - if blitz had a way of describing private methods - this would be a private method.
109.
110.
111.
112.
113. DxDx# = Dx*Dx
114. DyDy# = Dy*Dy
115. DzDz# = Dz*Dz
116.
117. DxVDx# = Dx*VDx
118. DyVDy# = Dy*VDy
119. DzVDz# = Dz*VDz
120.
121. VDxVDx# = VDx*VDx
122. VDyVDy# = VDy*VDy
123. VDzVDz# = VDz*VDz
124.
125. LL# = L*L
126.
127. If(LL = VDxVDx + VDyVDy + VDzVDz)
128.         ;impossible to hit.....ie will take eternity to do so....
129.         Return -1
130. EndIf
131.
132. BB# = (DxVDx + DyVDy + DzVDz)*(DxVDx + DyVDy + DzVDz)
133. AC# = (LL - VDxVDx - VDyVDy - VDzVDz)*(DxDx + DyDy + DzDz)
134.
135. If(BB+AC<0) Then
136.         Return -1
137.         ;impossible to hit....various possible reasons....
138. EndIf
139.
140. T1# = ((DxVDx + DyVDy + DzVDz) + Sqr(BB+AC))/(LL-(VDxVDx+VDyVDy+VDzVDz))
141. T2# = ((DxVDx + DyVDy + DzVDz) - Sqr(BB+AC))/(LL-(VDxVDx+VDyVDy+VDzVDz))
142.
143. If(T1<0) Then
144.         If(T2>0) Then
145.                 Return T2
146.         EndIf
147. EndIf
148. If(T2<0) Then
149.         If(T1>0) Then
150.                 Return T1
151.         EndIf
152. EndIf
153.
154. If(T1<T2) Then Return T1
155.
156. Return T2
157.
158. End Function
159.
160.
161. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;EXAMPLE 2D
162.
163. Function example2D()
164. Graphics 512,512,0,2
165. SetBuffer BackBuffer()
166.
167. ;let's do some little interactive demo ...have a couple of 'dots' fly around and shoot at each other......
168.
169. Local px#,py#,pvx#,pvy#,pax#,pay#
170. Local qx#,y#,qvx#,qvy#,qax#,qay#
171. Local spd#
172. Local maxspd# = 4.0 ;arbitrary
173.
174. Local bx#,by#,bvx#,bvy#
175. Local blife = 0
176. Local maxmuzzlevel# = 10.0 ;arbitrary
177.
178. Local startchase = False
179. px = Rnd(128)+256
180. py = Rnd(128)+256
181.
182. qx = Rnd(128)+256
183. qy = Rnd(128)+256
184.
185. pvx = 0
186. pvy = 0
187.
188. qvx = 0
189. qvy = 0
190.
191.
192.
193. MoveMouse 256,256
194.
195. Repeat
196. Cls
197.
198. px = px + pvx
199. py = py + pvy
200.
201. pvx = pvx + pax
202. pvy = pvy + pay
203.
204.
205. spd = Sqr(pvx*pvx+pvy*pvy)
206. If(startchase = True) Then
207.         ;;;;
208.         pax = (qx - px) * 0.01
209.         pay = (qy - py) * 0.01
210.
211. EndIf
212.
213. If(spd>maxspd) Then
214.         pvx = pvx * maxspd/spd
215.         pvy = pvy * maxspd/spd
216. EndIf
217.
218.
219. qx = qx + qvx
220. qy = qy + qvy
221.
222. qvx = qvx + qax
223. qvy = qvy + qay
224.
225.
226. spd = Sqr(qvx*qvx+qvy*qvy)
227. If(MouseDown(1)) Then
228.         startchase = True
229.         qax = (MouseX() - qx) * 0.01
230.         qay = (MouseY() - qy) * 0.01
231. EndIf
232. If(spd>maxspd) Then
233.         qvx = qvx * maxspd/spd
234.         qvy = qvy * maxspd/spd
235. EndIf
236.
237.
238. If(bx<0 Or by<0 Or bx>511 Or by>511) Then blife = 0
239.
240. If(blife>0) Then
241.         blife = blife-1
242.         bx = bx + bvx
243.         by = by + bvy
244.         Color 255,255,0
245.         Rect bx-1,by-1,3,3,1
246. Else
247.         ;see if we should shoot....and see where we should at!
248.         If(calculateMuzzleVelocity(px,py,0,pvx,pvy,0,qx,qy,0,qvx,qvy,0,maxmuzzlevel))
249.                 bx = px
250.                 by = py
251.                 bvx = pvx + MuzzleVelocity(0) ;VX
252.                 bvy = pvy + MuzzleVelocity(1) ;VY
253.                 blife = MuzzleVelocity(3) ;TIME
254.         EndIf
255. EndIf
256.
257. Color 255,0,255
258. Rect px-1,py-1,3,3,1
259.
260. Color 0,255,0
261. Rect qx-1,qy-1,3,3,1
262.
263. Flip
264.
265. Until KeyHit(1)
266. EndGraphics
267.
268.
269.
270. End Function

Matty(Posted 1+ years ago)

Fixed a minor typo.  In a check for division by zero I had added two numbers instead of multiplying.  Other than that it's all good.  Oh....I could probably replace one of the square roots.   Currently it uses two but one of them is unnecessary. ..the two lines where T1 and T2 are calculated I should really use a variable containing the result of the square root rather than calculating the same value twice.

Matty(Posted 1+ years ago)

Note - replace the above example with this to see a more 'interesting' example - click the screen and watch......see it in action....
Code: [Select]
`;;;;;;;;;;;;;;;;;;;;;;;;;;;;;EXAMPLE 2DFunction example2D()Graphics 512,512,0,2SetBuffer BackBuffer();let's do some little interactive demo ...have a couple of 'dots' fly around and shoot at each other......Local px#,py#,pvx#,pvy#,pax#,pay#Local qx#,y#,qvx#,qvy#,qax#,qay#Local spd#Local maxspd# = 4.0 ;arbitraryLocal bx#,by#,bvx#,bvy#Local blife = 0Local maxmuzzlevel# = 8.0 ;arbitraryLocal time = MilliSecs()Local startchase = Falsepx = Rnd(128)+256py = Rnd(128)+256qx = Rnd(128)+256qy = Rnd(128)+256pvx = 0pvy = 0qvx = 0qvy = 0MoveMouse 256,256RepeatClspx = px + pvxpy = py + pvypvx = pvx + paxpvy = pvy + payspd = Sqr(pvx*pvx+pvy*pvy)If(startchase = True) Then ;;;; pax = (qx - px) * 0.01 pay = (qy - py) * 0.01 EndIfIf(spd>maxspd) Then pvx = pvx * maxspd/spd pvy = pvy * maxspd/spdEndIfqx = qx + qvxqy = qy + qvyqvx = qvx + qaxqvy = qvy + qayspd = Sqr(qvx*qvx+qvy*qvy)If(MouseDown(1)) Then startchase = True qay = Rnd(10,20)*0.01 qax = Rnd(10,20)*0.01 time = MilliSecs()+Rand(100,1000)EndIfIf(startchase) ThenIf(qy>400) Then qay = Rnd(10,20)*0.01 qay = -Abs(qay)EndIfIf(qy<50) Then qay = Rnd(10,20)*0.01 qay = Abs(qay)EndIfIf(qx<50) Then qax = Rnd(10,20)*0.01 qax=Abs(qax)EndIfIf(qx>400) Then qax = Rnd(10,20)*0.01 qax=-Abs(qax)EndIfIf(Abs(qx-256)<96 And Abs(qy-256)<96) Or MilliSecs()>time Then qax = Rnd(10,20)*0.01 qay = Rnd(10,20)*0.01 time = MilliSecs()+Rand(100,1000)EndIfEndIfIf(spd>maxspd) Then qvx = qvx * maxspd/spd qvy = qvy * maxspd/spdEndIfIf(bx<0 Or by<0 Or bx>511 Or by>511) Then blife = 0If(blife>0) Then blife = blife-1 bx = bx + bvx by = by + bvy Color 255,255,0 Rect bx-1,by-1,3,3,1Else ;see if we should shoot....and see where we should at! If(calculateMuzzleVelocity(px,py,0,pvx,pvy,0,qx,qy,0,qvx,qvy,0,maxmuzzlevel)) bx = px by = py bvx = pvx + MuzzleVelocity(0) ;VX bvy = pvy + MuzzleVelocity(1) ;VY blife = MuzzleVelocity(3) ;TIME EndIf EndIf Color 255,0,255Rect px-1,py-1,3,3,1Color 0,255,0Rect qx-1,qy-1,3,3,1Color 255,255,255Text 0,0,"Click the screen to start. Press escape to exit."If(startchase) Then Text 0,15,"Watch as the little purple dot chases after the green dot" Text 0,30," and shoots him....see how many times he hits the target..."EndIfFlipUntil KeyHit(1)EndGraphicsEnd Function`