# Detect if two objects are going to collide

I am working on a car game where I am to create an AI. In the game there are other cars and a few objects moving around that I do not want to crash with, I have the speed, position and direction of all objects including my own car, but how would I go about calculating if my car is on a collision course with another object given my current speed and the other objects current speed? I tried coming up with an algorithm myself but I'm not very good at algebra.

• You might want to look into simply creating polynomials using the position formulae for the outermost points in the collision box and the Pythagorean Theorem and then finding the discriminants of the resulting polynomials. If the discriminant of a polynomial is positive, then the quadratic has at least one x-intercept. Otherwise, it has no x-intercepts. Thus, if any of the discriminants for any two points, each on the perimeters of the collision boxes, is positive, then we can say a collision will occur at some point in time, assuming the two objects stay on their courses. – moonman239 May 13 '16 at 5:45

I thought this would be an interesting challenge to test some of the math I learned in school, so here's what I figured out.

This approach assumes each object can be considered a circle for collision purposes. Naturally a car isn't a perfect circle, but it could be used as an approximation. You could use more circles to fill the area of the car better if you want a better approximation. E.g you could have one big circle in the center and one more in each corner of the car (for a total of 5 circles), or you could fill the car with 3x2 circles or 4x2 circles.

To make sure the final solution was correct and actually worked, I have now implemented it so you can see for yourself: http://codepen.io/sveinatle/pen/OPqLKE?editors=011. The code for this demo is at the bottom of the post as well.

I will describe the main concepts and give the final expressions needed here. To see the details please have a look at this online worksheet. The worksheet includes calculating the relevant values for a test case as well, so you could use that test case to check if you are applying the formulas correctly to the given variables. You can also see a plot which illustrates how the distance of the two points in the test case changes over time. You might want to draw the start- and finish-position of each of the two points on 8x8 grid to visualize meaning of the test case values which are calculated in the worksheet.

For each car/object/point, you know the following:

initial x position
speed in x direction
initial y position
speed in y direction


For two points a and b then, lets define the following variables:

xa0: initial x position of point A
xat: speed in x direction of point A
ya0: initial y position of point A
yat: speed in y direction of point A

xb0 initial x position of point B
xbt speed in x direction of point B
yb0 initial y position of point B
ybt speed in y direction of point B


The distance between to points is given by Pythagoras. By expressing this distance as a function of time (based on the given variables above), then we can solve for the minimum possible distance. If we do this then we get a formula which will give us the time of minimum distance. The details of this derivation can be seen in the worksheet -- I won't repeat them here -- but the result is the following formula:

mintime =
-(xa0*xat - xat*xb0 - (xa0 - xb0)*xbt + ya0*yat - yat*yb0 - (ya0 - yb0)*ybt)
/
(xat^2 - 2*xat*xbt + xbt^2 + yat^2 - 2*yat*ybt + ybt^2)


As you can see, this is a straight forward expression using only the given variables. The resulting value mintime is the time in seconds (or whatever unit your speeds are expressed in) when the two points will be the closest. This time is relative to the time of the starting positions, so if this time is negative then that means that the potential collision would have been in the past. In other words, there is no pending collision in the future and your work is done.

If the calculated mintime is positive, then that means the time of minimum distance is in the future. The next step then is to determine just how close that minimum distance will be: Is it close enough to consider it a collision?

The distance at any time t is given by the following expression:

dist = sqrt((t*xat - t*xbt + xa0 - xb0)^2 + (t*yat - t*ybt + ya0 - yb0)^2)


Once again a fairly simple expression. It depends on the given variables in addition to t. To calculate the minimum distance then, you just evaluate it using the minimum time you calculated previously. So with t = mintime:

mindist = sqrt(
(mintime*xat - mintime*xbt + xa0 - xb0)^2
+
(mintime*yat - mintime*ybt + ya0 - yb0)^2
)


And there you have your answer. The last thing to do now is to compare this minimum distance to the radius of the to circles. If mindist > radius_A + radius_B, then the two circles will never touch. If is less than or equal, then they will touch and you know there will be a collision within mintime-seconds. The collision might actually happen before mintime-seconds because the edges of the circles will touch each other before their centers are at their closest.

## CoffeeScript

$body =$('body')
$state =$('<div class="State">').appendTo $body w =$body.width()
h = $body.height() startTime = null totalTime = null class Car constructor: (@x0,@y0,@xt,@yt)-> if @x0? # Allow test case @disablerandom=true @x0 = @x0*100 @y0 = @y0*100 @xt = @xt*100 @yt = @yt*100 @radius = 50 @view =$('<div class="Car">').appendTo $body @reset() reset: -> @outside = false if not @disablerandom @x0 = Math.random() * w @y0 = Math.random() * h @xt = Math.random() * (w/2-@x0) @yt = Math.random() * (h/2-@y0) @radius = 5 + Math.random() * 100 checkForCollision?() @view.css width: @radius*2 height: @radius*2 marginLeft:-@radius marginTop:-@radius update: -> if @x > w or @x < 0 or @y>h or @y<0 then @outside = true @x = @x0 + @xt*totalTime @y = @y0 + @yt*totalTime @view.css left: @x @view.css top: h-@y class CollisionChecker constructor: (@a, @b)-> @mindist=0 @mintime=0 @checkForCollision() checkForCollision: -> @mintime = -(@a.x0*@a.xt - @a.xt*@b.x0 - (@a.x0 - @b.x0)*@b.xt + @a.y0*@a.yt - @a.yt*@b.y0 - (@a.y0 - @b.y0)*@b.yt) / (Math.pow(@a.xt,2) - 2*@a.xt*@b.xt + Math.pow(@b.xt,2) + Math.pow(@a.yt,2) - 2*@a.yt*@b.yt + Math.pow(@b.yt,2)) @mindist = Math.sqrt( Math.pow(@mintime*@a.xt - @mintime*@b.xt + @a.x0 - @b.x0, 2) + Math.pow(@mintime*@a.yt - @mintime*@b.yt + @a.y0 - @b.y0, 2) ) renderCounter: -> mintimeView = Math.round(@mintime*100)/100 mindistView = Math.round(@mindist*10)/10 minedgedistView = Math.round((@mindist-@a.radius-@b.radius)*10)/10 if @mintime <= 0 @mindist = Math.round(@mindist)$state
.css color: 'green'
.html """
Will never collide (diverging)<br>
Minimum center distance: #{mindistView}px<br>
Minimum edge distance: #{minedgedistView}px<br>
Time from start of min. dist.: #{mintimeView}s
"""
else
timeleft = Math.round((@mintime - totalTime)*100)/100
$state .css color: 'red' .html """ Will collide within #{timeleft}s<br> Minimum center distance: #{mindistView}px<br> Minimum edge distance: #{minedgedistView}px<br> Time from start of min. dist.: #{mintimeView}s """ else$state
.css color: '#990'
.html """
Will not collide, but reach minimum distance in #{timeleft}s<br>
Minimum center distance: #{mindistView}px<br>
Minimum edge distance: #{minedgedistView}px<br>
Time from start of min. dist.: #{mintimeView}s
"""

# Test case 1
#a = new Car(2,5,1,2/3)
#b = new Car(5,2,-2/3,4/3)

# Random
a = new Car()
b = new Car()
checker = new CollisionChecker a, b

a.view.css backgroundColor: 'red'
b.view.css backgroundColor: 'blue'

startTime = new Date().getTime()/1000.0
setInterval ->
totalTime = new Date().getTime()/1000.0 - startTime
a.update()
b.update()
checker.renderCounter()
if a.outside or b.outside
console.log 'reset'
startTime = new Date().getTime()/1000.0
w = $body.width() # Get viewport dimensions again in case of resize h =$body.height()
a.reset()
b.reset()
checker.checkForCollision()
, 10


## CSS (Stylus)

html
height 100%
body
position relative
background-color #ffe
height 100%

.Car
position absolute

.State
font-size 20px
margin-top 30px
margin-left 30px

• This is one awesome reply :O seriously thought thank you so much ^^ i was able to implement a pretty good avoidance algorithm based on ur math :) my AIs stoped crashing into each other – Paze Mar 27 '15 at 23:55
• No problem! I had fun with it :) – Supr Mar 28 '15 at 0:09
• You might want to look into simply creating polynomials using the position formulae for the outermost points in the collision box and the Pythagorean Theorem and then finding the discriminants of the resulting polynomials. If the discriminant of a polynomial is positive, then the quadratic has at least one x-intercept. Otherwise, it has no x-intercepts. Thus, if any of the discriminants for any two points, each on the perimeters of the collision boxes, is positive, then we can say a collision will occur at some point in time, assuming the two objects stay on their courses. – moonman239 May 13 '16 at 5:44

The basic idea is that you extend your car's collision box, based on the current velocity of the car. If this extension collides with a car or with car's extension box, you can assume that there will be a collision, so you must have the car that is the most 'behind' to avoid the collision.

There seem to be a nice article here. They use vectors, but you'd want to use boxes in your case.

You could approach the issue by evaluating delta position each frame and check if by moving another delta the collision would trigger.

prevPos = pos;
pos = newPos;
deltaPos = prevpos - pos

if(EnterCollision(pos+deltaPos))
//do stuff