Detect if two objects are going to collide

Question

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.

Answer 1

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
      if @mindist <= a.radius + b.radius
        $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
  border-radius 200px

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

Answer 2

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.

Answer 3

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