January 20, 2021, 10:14:54 AM

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

#### BlitzBot

• Jr. Member
• Posts: 1
##### [bb] Predict time of collision for two moving objects by Matty [ 1+ years ago ]
« on: June 29, 2017, 12:28:43 AM »
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