Intro
The simulator is an important part of how I’ve approached writing my AI for the Fantastic Bits contest (and many others). Being able to simulate what will happen after throwing, when moving in a direction or when casting a spell gives your AI the ability to (sometimes inaccurately) see into the future. This gives your AI much better capabilities for planning ahead. So before my post-mortem, I would like to discuss how to approach detecting collisions between two moving circles and resolving these collisions. This is one of the hardest parts of writing a simulator for games like Fantastic Bits and Coders Strike Back. In this post, I will discuss collisions between two circles. Two circles are colliding when the distance between their center points is less than the sum of their radii, which you can see here:
You can detect when a collision between two circles will happen by figuring out when the distance between their center points reaches the sum of their radii.
Prelude
Let
We can describe the position of both center points after time using the equation from the Movement section:
What we wish to know is when both points are at a distance of from eachother:
Equation Using Components
Now we can decompose these into their components:
We can square both sides to get rid of that pesky square root:
Then:
Grouping terms:
Written differently:
Now, we can use the discriminant method to solve this quadratic equation:
Where:
When we’ve solved for , we can get 0, 1 or 2 solutions, we have to pick the minimal one, because we want the earliest collision.
If is positive, there are 2 solutions:
If is 0, there is 1 solution, but it can be described by the equation above because will be 0.
If is negative, there are no solutions, this means the circles will never overlap. In other words, no collision.
Because we know will always be positive, since it is composed of the sum of two squares and is positive iff there is a collision, we can change this to:
Doing this will give you the smallest time when the circle perimeters will overlap, if they will ever.
Equation Using Dot Products
Thank you sethorizer for enlightening me about this!
An alternative (and I think cleaner) way to solve this is to observe the , and equations and see that these can be rewritten as dot products:
You can also derive this dot product form another way:
Which you can solve as a quadratic equation.
Pseudocode
Function arguments
dp: vec2 =
dv: vec2 =
radius_sum: float =
With dot products
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func circle_collision_time(dp: vec2, dv: vec2, radius_sum: float) -> float
let radius_sum_squared = radius_sum.pow(2)
let a = dv.dot(dv)
let b = 2 * dv.dot(dp)
let c = dp.dot(dp) - radius_sum_squared
if b >= 0 # They're moving away from eachother.
return null
end
if c <= 0 # They're already colliding.
return 0
end
let d = b.pow(2) - 4 * a * c
if d < 0 # No solution to the equation, no collision.
# They're moving towards eachother but will not collide.
return null
end
return (-b - sqrt(d)) / (2 * a)
end
With components
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func circle_collision_time(dp: vec2, dv: vec2, radius_sum: float) -> float
let radius_sum_squared = radius_sum.pow(2)
let a = dv.x.pow(2) + dv.y.pow(2)
let b = 2 * (dp.x * dv.x + dp.y * dv.y)
let c = dp.x.pow(2) + dp.y.pow(2)
if b >= 0 # They're moving away from eachother.
return null
end
if c <= 0 # They're already colliding.
return 0
end
let d = b.pow(2) - 4 * a * c
if d < 0 # No solution to the equation, no collision.
# They're moving towards eachother but will not collide.
return null
end
return (-b - sqrt(d)) / (2 * a)
end
Possible Improvements
Not using pow
It’s usually faster to explicitly do a*a instead of a.pow(2). Some compilers will optimize
this away, while others will leave the slower operation.
