Ooops
October 28, 2020, 06:35:13 AM

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

Offline BlitzBot

  • Jr. Member
  • **
  • Posts: 1
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


Comments :


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 2D

Function example2D()
Graphics 512,512,0,2
SetBuffer 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 ;arbitrary

Local bx#,by#,bvx#,bvy#
Local blife = 0
Local maxmuzzlevel# = 8.0 ;arbitrary

Local time = MilliSecs()

Local startchase = False
px = Rnd(128)+256
py = Rnd(128)+256

qx = Rnd(128)+256
qy = Rnd(128)+256

pvx = 0
pvy = 0

qvx = 0
qvy = 0



MoveMouse 256,256

Repeat
Cls

px = px + pvx
py = py + pvy

pvx = pvx + pax
pvy = pvy + pay


spd = Sqr(pvx*pvx+pvy*pvy)
If(startchase = True) Then
;;;;
pax = (qx - px) * 0.01
pay = (qy - py) * 0.01

EndIf

If(spd>maxspd) Then
pvx = pvx * maxspd/spd
pvy = pvy * maxspd/spd
EndIf


qx = qx + qvx
qy = qy + qvy

qvx = qvx + qax
qvy = qvy + qay


spd = 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)
EndIf
If(startchase) Then

If(qy>400) Then
qay = Rnd(10,20)*0.01
qay = -Abs(qay)
EndIf
If(qy<50) Then
qay = Rnd(10,20)*0.01
qay = Abs(qay)
EndIf
If(qx<50) Then
qax = Rnd(10,20)*0.01
qax=Abs(qax)
EndIf
If(qx>400) Then
qax = Rnd(10,20)*0.01
qax=-Abs(qax)
EndIf
If(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)
EndIf


EndIf

If(spd>maxspd) Then
qvx = qvx * maxspd/spd
qvy = qvy * maxspd/spd
EndIf


If(bx<0 Or by<0 Or bx>511 Or by>511) Then blife = 0

If(blife>0) Then
blife = blife-1
bx = bx + bvx
by = by + bvy
Color 255,255,0
Rect bx-1,by-1,3,3,1
Else
;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,255
Rect px-1,py-1,3,3,1

Color 0,255,0
Rect qx-1,qy-1,3,3,1

Color 255,255,255
Text 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..."
EndIf
Flip

Until KeyHit(1)
EndGraphics



End Function


 

SimplePortal 2.3.6 © 2008-2014, SimplePortal