[bb] Predict time of collision for two moving objects by Matty [ 1+ years ago ]

Started by BlitzBot, June 29, 2017, 00:28:43

Previous topic - Next topic
Print
Go Down Pages1
User actions

BlitzBot

June 29, 2017, 00:28:43
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) Select
;Author - Matt Lloyd 2015
;
;Function - whenwillicollide#()
;
;Used to determine the time at which a moving object (straight line) will collide with another moving object (straight line)
;
;The example (see example function) lets the user move a little 'spaceship' around the map by clicking on the screen, the AI unit
;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
;a fortune teller!)
;
;
;Hopefully this comes in useful - I will find it useful anyway....
;




;test example of usage...
example()


;function definition..
Function whenwillicollide#(dimensions,posx#,posy#,posz#,velx#,vely#,velz#,targetposx#,targetposy#,targetposz#,targetvelx#,targetvely#,targetvelz#,mintime#,maxtime#,tolerance#=0.1)
;Parameters are:
;
;Dimensions is a value from 1 to 3....indicates the number of dimensions to use...
;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...
;
;
;Position of first entity x,y,z (floats)
;Velocity of first entity in x,y,z (floats)
;
;Position of second entity x,y,z (floats)
;Velocity of second entity in x,y,z (floats)
;
;Minimum time to accept (float)
;Maximum time to accept (float)
;
;Tolerance (float) - allowable difference between times in each coordinate system...optional value........
;
;Return values are:
;
;-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
;intersect on the same axis within the specified tolerance
;
;-2 if the mintime or maxtime are set incorrectly (ie less than zero or maxtime is less than mintime)
;
;-3 if the dimensions has an invalid value (must be either 2 or 3)
;
;
;Assumes two entities are NOT at the same location..ie not already collided!
;


Local intersectiontime#[2] ;array containing the intersection time of each coordinate....
;0 = x index, 1 = y index, 2 = z index

If(dimensions<2 Or dimensions>3) Then Return -3

If(mintime<0 Or maxtime<0 Or maxtime<mintime) Then Return -2


If(targetvelx - velx)=0  Then Return -1
intersectiontime[0] = (posx - targetposx) / (targetvelx - velx)
If(intersectiontime[0]<mintime Or intersectiontime[0]>maxtime) Then Return -1
If(targetvely - vely)=0 Then Return -1
intersectiontime[1] = (posy - targetposy) / (targetvely - vely)
If(intersectiontime[1]<mintime Or intersectiontime[1]>maxtime) Then Return -1
If (Abs(intersectiontime[1]-intersectiontime[0]))>tolerance Then Return -1
If(dimensions=2) Then Return (intersectiontime[0]+intersectiontime[1])*0.5
If(targetvelz - velz)=0 Then Return -1
intersectiontime[2] = (posz - targetposz) / (targetvelz - velz)
If(intersectiontime[2]<mintime Or intersectiontime[2]>maxtime) Then Return -1
If (Abs(intersectiontime[2]-intersectiontime[1]))>tolerance Then Return -1
If (Abs(intersectiontime[2]-intersectiontime[0]))>tolerance Then Return -1

Return (intersectiontime[0]+intersectiontime[1]+intersectiontime[2])*0.33333

End Function

Function example()
;
;
;2 dimensional example....

Local maxvel = 2.0,maxbulletvel = 4.0
Local playerX#,playerY#,playervelX#,playervelY#,playeraccelX#,playeraccelY#
Local enemyX#,enemyY#,enemyvelX#,enemyvelY#,enemyaccelX#,enemyaccelY#
Local enemybulletX#,enemybulletY#,enemybulletvelX#,enemybulletvelY#,enemybulletlife
Local startedchasing=0


Graphics 512,512,0,2

playerx = Rnd(256)+128
playery = Rnd(256)+128
playervelx = 0
playervely = 0
playeraccelx = 0
playeraccely = 0

enemyx = Rnd(256)+128
enemyy = Rnd(256)+128

enemybulletx = -1
enemybullety = -1
enemybulletlife = 0


SetBuffer BackBuffer()
Repeat

playerx = playerx + playervelx
playery = playery + playervely

playervelx = playervelx + playeraccelx
playervely = playervely + playeraccely

If(playervelx*playervelx+playervely*playervely)>maxvel*maxvel Then
playervelx = playervelx * maxvel/Sqr((playervelx*playervelx+playervely*playervely))
playervely = playervely * maxvel/Sqr((playervelx*playervelx+playervely*playervely))
EndIf

enemyx = enemyx + enemyvelx
enemyy = enemyy + enemyvely

enemyvelx = enemyvelx + enemyaccelx
enemyvely = enemyvely + enemyaccely

If(enemyvelx*enemyvelx+enemyvely*enemyvely)>maxvel*maxvel Then
enemyvelx = enemyvelx * maxvel/Sqr((enemyvelx*enemyvelx+enemyvely*enemyvely))
enemyvely = enemyvely * maxvel/Sqr((enemyvelx*enemyvelx+enemyvely*enemyvely))
EndIf

;move the bullet....
If(enemybulletlife>0) Then

enemybulletx = enemybulletx + enemybulletvelx
enemybullety = enemybullety + enemybulletvely
enemybulletlife = enemybulletlife - 1


EndIf


If(MouseDown(1)) Then ;player provides thrust towards point pressed by mouse....
dx# = MouseX() - playerx
dy# = MouseY() - playery
length# = dx*dx+dy*dy
If(length>0)
length = Sqr(length)
dx = 0.65*dx/length
dy = 0.65*dy/length

playeraccelx = dx
playeraccely = dy
startedchasing = 1
EndIf

EndIf

;enemy tracks player....and moves around chasing them......(after the player starts moving)
If(startedchasing=1) Then
dx# = playerx - enemyx
dy# = playery - enemyy
length# = dx*dx+dy*dy
If(length>0)
length = Sqr(length)
dx = 0.55*dx/length
dy = 0.55*dy/length

enemyaccelx = dx
enemyaccely = dy
startedchasing = 1
EndIf

If(enemybulletlife<=0) Then
;;;see if we should fire a bullet.....

;bullet starts from enemy pos
enemybulletx = enemyx
enemybullety = enemyy

;bullet starts with same velocity as enemy (ie good old vector addition - assuming non relativistic speeds!
enemybulletvelx = enemyvelx
enemybulletvely = enemyvely


dx# = playerx - enemybulletx
dy# = playery - enemybullety
length# = dx*dx+dy*dy
If(length>0)
length = Sqr(length)
dx = dx / length
dy = dy / length

;bullet velocity will be faster than ships - it will be..twice as fast as the maxvel...
enemybulletvelx = enemybulletvelx + dx
enemybulletvely = enemybulletvely + dy

If(enemybulletvelx*enemybulletvelx+enemybulletvely*enemybulletvely)>(maxbulletvel)*(maxbulletvel) Then
enemybulletvelx = enemybulletvelx * (maxbulletvel) / Sqr((enemybulletvelx*enemybulletvelx+enemybulletvely*enemybulletvely))
enemybulletvely = enemybulletvely * (maxbulletvel) / Sqr((enemybulletvelx*enemybulletvelx+enemybulletvely*enemybulletvely))
EndIf

;okay but will we hit our target? if so then we want to fire...
;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!)

;this is where I call the function above - if it returns a non zero value then I want to fire!
enemybulletlife = whenwillicollide(2,enemybulletx,enemybullety,0,enemybulletvelx,enemybulletvely,0,playerx,playery,0,playervelx,playervely,0,0,300,(maxbulletvel+maxvel+2))

If(enemybulletlife<0)
enemybulletlife = 0
Else
;enemybulletlife = 60 ;(uncomment this and the bullet will only travel until it reaches where it should have hit the player at...)
EndIf
EndIf
EndIf


EndIf
Cls
Color 0,255,0
Rect playerx-1,playery-1,3,3,1

Color 255,0,255
Rect enemyx-1,enemyy-1,3,3,1

Color 255,255,0
If(enemybulletlife>0) Then
Rect enemybulletx-1,enemybullety-1,3,3,1
EndIf
Flip

Until KeyDown(1)

End


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.
Print
Go Up Pages1
User actions