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.