Hello Codeforces!
As promised almost three years ago, I have finally found the time and scope to write about using CP techniques outside CP itself.
My first post is about a use case of binary search in video games. Unfortunately, the post is written in MDX (with videos and custom elements that Codeforces doesn't support), so I have to post a link if you want to read the whole post.
You can find it here: Continuous Collision Detection in Video Games using Binary Search
Here is a summary.
The Problem
In a standard game loop, objects "teleport" from position $$$(x, y)$$$ to $$$(x + \Delta x, y + \Delta y)$$$ in a single frame.
If a wall is thin enough, a fast-moving bullet can start on one side and end on the other in a single frame, completely skipping the collision check. This well-known bug is called tunneling.
To fix this, we need to check the swept volume — the continuous volume the object occupies during its movement from time $$$t_0$$$ to $$$t_1$$$.
The problem is that we need to find the exact time of impact $$$t \in [t_0, t_1]$$$ where the object first touches the wall.
The Solution: Binary Search on Time
Let's define a function $$$f(t)$$$ such that:
- $$$f(t) = 1$$$ if the object's swept volume from $$$t_0$$$ to $$$t$$$ intersects the obstacle.
- $$$f(t) = 0$$$ otherwise.
Claim: If there is a collision in the swept volume during $$$[t_0, t]$$$, there will also be a collision in any later time interval $$$[t_0, t']$$$ where $$$t' \geq t$$$. This can be proven formally, but the intuition is simple.
Since the function is monotonic, we can Binary Search on the time $$$t$$$ to find the first moment of collision.
double find_collision_time(double t0, double t1, Object obstacle) {
// Handle t0 separately - in case we are already colliding
if (check_collision(t0, t0, obstacle)) return t0;
// Handle (t0, t1]
const double eps = clamp((t1 - t0) / this->speed, 1e-6, 1e-3);
const int maxIterations = 1 + ceil(log2((t1 - t0) / eps));
for (int i = 0; (i < maxIterations) && ((t1 - t0) > eps); ++i) {
double mid = (t0 + t1) / 2.;
if (check_collision(t0, mid, obstacle)) {
t1 = mid;
} else {
t0 = mid;
}
}
return t1;
}
The time complexity is $$$O(\log ((t_1 - t_0) / \epsilon))$$$ which becomes $$$O(\log S)$$$ when $$$\epsilon \approx 1 / S$$$.
Thanks for reading! Let me know if you use binary search for anything else.
