October 28, 2020, 05:59:27 AM

Author Topic: [bb] Predict time of collision for two moving objects by Matty [ 1+ years ago ]  (Read 1438 times)

Offline BlitzBot

  • Jr. Member
  • **
  • Posts: 1
Title : Predict time of collision for two moving objects
Author : Matty
Posted : 1+ years ago

Description : This function takes a set of parameters - the positions and velocities of a pair of moving objects and returns the time (in number of frames) that the entities will collide.

The minimum and maximum time that you wish to allow for is passed in as well, and also a tolerance (which should always be some figure greater than zero)

There is error handling and validation within the function - if the user passes in invalid combinations of minimum/maximum time then it will return a particular value.

The return value of the function is the number of frames / position updates at those particular velocities that the entities will collide.

If they will not collide (for whatever reason) then it will return a -1.

I have included an example in the function "example".  This example will let the user move a little dot(green) around the screen by clicking locations on the map, and an enemy dot (purple) will chase and shoot at the player (yellow dot) when they are able to hit (as detected by the function).

The mathematics are pretty straight forward.

The two objects have a position vector and a velocity vector which is dependent linearly on time 't'.

The intersection point on each axis is found in terms of 't'.
If the 't' value found for each axis is within a given tolerance then the average of those 't' value is returned.

The function escapes as soon as a condition is met that means they won't collide. Eg - the difference in velocity in any component direction is zero, or the time required for any of the components is outside the specified range.
As an extra piece of useless information - I will definitely be using this in my own code for a game I'm writing for detecting whether an AI should shoot at a target - and also detecting whether two moving spaceships are going to collide etc.....

Hope you find it useful too.

from Matt


Code :
Code: BlitzBasic
  1. ;Author - Matt Lloyd 2015
  2. ;
  3. ;Function - whenwillicollide#()
  4. ;
  5. ;Used to determine the time at which a moving object (straight line) will collide with another moving object (straight line)
  6. ;
  7. ;The example (see example function) lets the user move a little 'spaceship' around the map by clicking on the screen, the AI unit
  8. ;will 'chase' and shoot at the player when they have a likely shot....of course - if the user changes direction then it will miss! (I'm not
  9. ;a fortune teller!)
  10. ;
  11. ;
  12. ;Hopefully this comes in useful - I will find it useful anyway....
  13. ;
  14.  
  15.  
  16.  
  17.  
  18. ;test example of usage...
  19. example()
  20.  
  21.  
  22. ;function definition..
  23. Function whenwillicollide#(dimensions,posx#,posy#,posz#,velx#,vely#,velz#,targetposx#,targetposy#,targetposz#,targetvelx#,targetvely#,targetvelz#,mintime#,maxtime#,tolerance#=0.1)
  24. ;Parameters are:
  25. ;
  26. ;Dimensions is a value from 1 to 3....indicates the number of dimensions to use...
  27. ;For example - a 2d game would use '2', a 3d game would use '3', and I'm not sure why you would use less than 2 dimensions...but hey...
  28. ;
  29. ;
  30. ;Position of first entity x,y,z (floats)
  31. ;Velocity of first entity in x,y,z (floats)
  32. ;
  33. ;Position of second entity x,y,z (floats)
  34. ;Velocity of second entity in x,y,z (floats)
  35. ;
  36. ;Minimum time to accept (float)
  37. ;Maximum time to accept (float)
  38. ;
  39. ;Tolerance (float) - allowable difference between times in each coordinate system...optional value........
  40. ;
  41. ;Return values are:
  42. ;
  43. ;-1 if the vectors never intersect (either because they are skew lines or because they intersect outside of the allowable range or because they do not
  44. ;intersect on the same axis within the specified tolerance
  45. ;
  46. ;-2 if the mintime or maxtime are set incorrectly (ie less than zero or maxtime is less than mintime)
  47. ;
  48. ;-3 if the dimensions has an invalid value (must be either 2 or 3)
  49. ;
  50. ;
  51. ;Assumes two entities are NOT at the same location..ie not already collided!
  52. ;
  53.  
  54.  
  55. Local intersectiontime#[2] ;array containing the intersection time of each coordinate....
  56. ;0 = x index, 1 = y index, 2 = z index
  57.  
  58. If(dimensions<2 Or dimensions>3) Then Return -3
  59.  
  60. If(mintime<0 Or maxtime<0 Or maxtime<mintime) Then Return -2
  61.  
  62.  
  63. If(targetvelx - velx)=0  Then Return -1
  64. intersectiontime[0] = (posx - targetposx) / (targetvelx - velx)
  65. If(intersectiontime[0]<mintime Or intersectiontime[0]>maxtime) Then Return -1
  66. If(targetvely - vely)=0 Then Return -1
  67. intersectiontime[1] = (posy - targetposy) / (targetvely - vely)
  68. If(intersectiontime[1]<mintime Or intersectiontime[1]>maxtime) Then Return -1
  69. If (Abs(intersectiontime[1]-intersectiontime[0]))>tolerance Then Return -1
  70. If(dimensions=2) Then Return (intersectiontime[0]+intersectiontime[1])*0.5
  71. If(targetvelz - velz)=0 Then Return -1
  72. intersectiontime[2] = (posz - targetposz) / (targetvelz - velz)
  73. If(intersectiontime[2]<mintime Or intersectiontime[2]>maxtime) Then Return -1
  74. If (Abs(intersectiontime[2]-intersectiontime[1]))>tolerance Then Return -1
  75. If (Abs(intersectiontime[2]-intersectiontime[0]))>tolerance Then Return -1
  76.  
  77. Return (intersectiontime[0]+intersectiontime[1]+intersectiontime[2])*0.33333
  78.  
  79. End Function
  80.  
  81. Function example()
  82. ;
  83. ;
  84. ;2 dimensional example....
  85.  
  86. Local maxvel = 2.0,maxbulletvel = 4.0
  87. Local playerX#,playerY#,playervelX#,playervelY#,playeraccelX#,playeraccelY#
  88. Local enemyX#,enemyY#,enemyvelX#,enemyvelY#,enemyaccelX#,enemyaccelY#
  89. Local enemybulletX#,enemybulletY#,enemybulletvelX#,enemybulletvelY#,enemybulletlife
  90. Local startedchasing=0
  91.  
  92.  
  93. Graphics 512,512,0,2
  94.  
  95. playerx = Rnd(256)+128
  96. playery = Rnd(256)+128
  97. playervelx = 0
  98. playervely = 0
  99. playeraccelx = 0
  100. playeraccely = 0
  101.  
  102. enemyx = Rnd(256)+128
  103. enemyy = Rnd(256)+128
  104.  
  105. enemybulletx = -1
  106. enemybullety = -1
  107. enemybulletlife = 0
  108.  
  109.  
  110. SetBuffer BackBuffer()
  111. Repeat
  112.  
  113. playerx = playerx + playervelx
  114. playery = playery + playervely
  115.  
  116. playervelx = playervelx + playeraccelx
  117. playervely = playervely + playeraccely
  118.  
  119. If(playervelx*playervelx+playervely*playervely)>maxvel*maxvel Then
  120.         playervelx = playervelx * maxvel/Sqr((playervelx*playervelx+playervely*playervely))
  121.         playervely = playervely * maxvel/Sqr((playervelx*playervelx+playervely*playervely))
  122. EndIf
  123.  
  124. enemyx = enemyx + enemyvelx
  125. enemyy = enemyy + enemyvely
  126.  
  127. enemyvelx = enemyvelx + enemyaccelx
  128. enemyvely = enemyvely + enemyaccely
  129.  
  130. If(enemyvelx*enemyvelx+enemyvely*enemyvely)>maxvel*maxvel Then
  131.         enemyvelx = enemyvelx * maxvel/Sqr((enemyvelx*enemyvelx+enemyvely*enemyvely))
  132.         enemyvely = enemyvely * maxvel/Sqr((enemyvelx*enemyvelx+enemyvely*enemyvely))
  133. EndIf
  134.  
  135. ;move the bullet....
  136. If(enemybulletlife>0) Then
  137.  
  138. enemybulletx = enemybulletx + enemybulletvelx
  139. enemybullety = enemybullety + enemybulletvely
  140. enemybulletlife = enemybulletlife - 1
  141.  
  142.  
  143. EndIf
  144.  
  145.  
  146. If(MouseDown(1)) Then ;player provides thrust towards point pressed by mouse....
  147.         dx# = MouseX() - playerx
  148.         dy# = MouseY() - playery
  149.         length# = dx*dx+dy*dy
  150.         If(length>0)
  151.                 length = Sqr(length)
  152.                 dx = 0.65*dx/length
  153.                 dy = 0.65*dy/length
  154.                
  155.                 playeraccelx = dx
  156.                 playeraccely = dy
  157.                 startedchasing = 1
  158.         EndIf
  159.  
  160. EndIf
  161.  
  162. ;enemy tracks player....and moves around chasing them......(after the player starts moving)
  163. If(startedchasing=1) Then
  164.         dx# = playerx - enemyx
  165.         dy# = playery - enemyy
  166.         length# = dx*dx+dy*dy
  167.         If(length>0)
  168.                 length = Sqr(length)
  169.                 dx = 0.55*dx/length
  170.                 dy = 0.55*dy/length
  171.                
  172.                 enemyaccelx = dx
  173.                 enemyaccely = dy
  174.                 startedchasing = 1
  175.         EndIf
  176.  
  177.         If(enemybulletlife<=0) Then
  178.                 ;;;see if we should fire a bullet.....
  179.                
  180.                 ;bullet starts from enemy pos
  181.                 enemybulletx = enemyx
  182.                 enemybullety = enemyy
  183.                
  184.                 ;bullet starts with same velocity as enemy (ie good old vector addition - assuming non relativistic speeds!
  185.                 enemybulletvelx = enemyvelx
  186.                 enemybulletvely = enemyvely
  187.                
  188.                
  189.                 dx# = playerx - enemybulletx
  190.                 dy# = playery - enemybullety
  191.                 length# = dx*dx+dy*dy
  192.                 If(length>0)
  193.                         length = Sqr(length)
  194.                         dx = dx / length
  195.                         dy = dy / length
  196.                        
  197.                         ;bullet velocity will be faster than ships - it will be..twice as fast as the maxvel...
  198.                         enemybulletvelx = enemybulletvelx + dx
  199.                         enemybulletvely = enemybulletvely + dy
  200.                        
  201.                         If(enemybulletvelx*enemybulletvelx+enemybulletvely*enemybulletvely)>(maxbulletvel)*(maxbulletvel) Then
  202.                                 enemybulletvelx = enemybulletvelx * (maxbulletvel) / Sqr((enemybulletvelx*enemybulletvelx+enemybulletvely*enemybulletvely))
  203.                                 enemybulletvely = enemybulletvely * (maxbulletvel) / Sqr((enemybulletvelx*enemybulletvelx+enemybulletvely*enemybulletvely))
  204.                         EndIf
  205.                        
  206.                         ;okay but will we hit our target? if so then we want to fire...
  207.                         ;now....the life of the bullet we will say is...60 frames....just an arbitrary number...can be anything....but most games I've written usually have a maximum 'lifetime' of the bullet (especially useful if it continues to fly off into deep space!)
  208.                        
  209.                         ;this is where I call the function above - if it returns a non zero value then I want to fire!
  210.                         enemybulletlife = whenwillicollide(2,enemybulletx,enemybullety,0,enemybulletvelx,enemybulletvely,0,playerx,playery,0,playervelx,playervely,0,0,300,(maxbulletvel+maxvel+2))                    
  211.  
  212.                         If(enemybulletlife<0)
  213.                                 enemybulletlife = 0
  214.                         Else
  215.                                 ;enemybulletlife = 60 ;(uncomment this and the bullet will only travel until it reaches where it should have hit the player at...)
  216.                         EndIf  
  217.                 EndIf
  218.         EndIf
  219.  
  220.  
  221. EndIf
  222. Cls
  223. Color 0,255,0
  224. Rect playerx-1,playery-1,3,3,1
  225.  
  226. Color 255,0,255
  227. Rect enemyx-1,enemyy-1,3,3,1
  228.  
  229. Color 255,255,0
  230. If(enemybulletlife>0) Then
  231.         Rect enemybulletx-1,enemybullety-1,3,3,1
  232. EndIf
  233. Flip
  234.  
  235. Until KeyDown(1)
  236.  
  237. End
  238.  
  239.  
  240. End Function


Comments :


Rick Nasher(Posted 1+ years ago)

 My compliments. Might come in handy and should be fairly easy to use in 3d environement too as you took provisions for that.


 

SimplePortal 2.3.6 © 2008-2014, SimplePortal