Binary Search PIF

An optimized algorithm based on the binary search algorithm for the usual Play It Forward technique which runs in logarithmic time.

Preliminaries

First you should understand the Fast Play It Forward technique, which is both explained below and in the PIF page.

The first and only requirement is that the logs store the past positions of the enemy and his actual heading, which is the angle which the enemy is actually moving to (getHeadingRadians() <math> + \pi</math> when getVelocity() < 0, getHeadingRadians() otherwise). Let's suppose some state of a robot is defined by his position and his actual heading. For instance, a state can be thought as a vector (heading) fixed at a point (position) in a plane. Therefore, we can apply some transformations to it.

Let <math>r</math> be our current state in the field, <math>p</math> be the current state of the enemy and <math>q</math> be the position of the first scan of him to be played in our movie. There is some linear transformation <math>T</math> such that <math>Tp = q</math>. One possible transformation is a translation of the point (to bring both states to the same point) followed by a rotation of the vector (to make the vectors equal).

This means that if we play the movie forward, starting from <math>q</math>, and reach some state <math>q'</math>, then <math>T^{-1} q'</math> is the state of our enemy if we had played our movie forward starting from his current state instead of his past state. Notice that <math>T^{-1}</math> can be easily determined for our translation+rotation transformation.

Current locations and Recorded state.

Current locations rotated and projected onto Recorded state.

Moreover, we can apply the transformation to our current position too, so we can evaluate the bullet flight time correctly as well, as if we were in the past in the same situation as the current one. After that, we can do the inverse transformations and get the correct firing angle. This technique allows us to play our movie forward very fast in practice, because we avoid expensive trigonometric operations during the simulation. We only have these operations executed before and after the simulation. The number of iterations, though, is in the worst case equals to the bullet flight time. Can we do better than that?

The optimization

Let's fix some state <math>p</math> in the movie and its successor <math>p'</math>. Note that if there is a gap of time of size <math>t</math> between these two states, we can conclude the following:

• Between <math>p</math> and <math>p'</math>, the enemy has driven at most <math>8t</math> units;
• The wave has traveled some value between <math>11t</math> and <math>20t</math> (max power and min power, respectively) units.

This necessarily means that, every time we play the movie forward at least one tick, the distance between the enemy and the wave decreases by a positive amount (more specifically, greater than or equal to <math>11t - 8t = 3t</math>) if the wave has not passed the robot yet and increases by a positive amount (more specifically, greater than or equal to <math>11t - 8t = 3t</math>) otherwise. Note that the question "if I play the movie <math>x</math> ticks in the future, will the wave pass the robot?" is monotonic (if it eventually is true for some <math>x</math>, then it will keep being true for greater <math>x</math>). This is a classic kind of function which can be binary searched to find the first moment the question is true. That's exactly what we want, since we want "the minimum <math>x</math> such that the wave passed the robot".

The algorithm

We could then run a binary search on <math>x</math> and, if the question is TRUE for it, we know that the answer is less or equal than <math>x</math>, otherwise it is greater than <math>x</math>. It is a bit non-intuitive to binary search <math>x</math>, though, since we may have gaps in our movie (which is perfectly common in melee, for example). Another approach is to run the binary search on the scans of our movie, and the question becomes "if I play the movie <math>x</math> scans in the future, will the wave pass the robot?".

Notice that both approaches, though, assume that we can quickly access the <math>x</math>-th scan of our movie, otherwise we would have to access these scans in a inefficient way. One way to do this is to store the movies in a array instead of in a linked list, so you can have them directly accessed by their indices.

The first thing we have to do when binary searching is to determine the range of values our <math>x</math> can assume. We know that in this case it ranges from 0 to the max bullet flight time. Let <math>b</math> be the bullet speed and <math>d</math> be the distance of the enemy from the bullet source. A good upper bound for the real bullet flight time is <math>\lceil \frac{d}{b-8} \rceil</math>, which turns out to be a pretty good upper bound for the number of scans we have to play forward as well. The final pseudo-algorithm turns to be:

// movie is the sequence of scans to be "played". movie[i] is the i-th of these scans, starting from zero.
// r is my state (actual heading and position)
// q is the latest state of the enemy
// b is the bullet speed
procedure play(movie, r, q, b, fire_time):
  // find the transformation T and apply it to my state (project me into the past)
  r* := T(r)

  left := 0
  right := min(ceil(dist(r*, q) / (b - 8)), movie.size - 1)

  // movie_start is the time of the first scan of our movie
  movie_start := movie[0].time

  // extra_time is how many ticks old is the latest scan of our enemy, counting from the firing time
  extra_time := fire_time - q.time
  
  while left < right do
    mid := floor(left + right)
    x := movie[mid]
    traveled := (x.time - movie_start - extra_time) * b

    if distance(r, x) > traveled then
      left := mid + 1
    else
      right := mid
    end
  end

  // T-1 is the inverse transformation of T
  return T-1(movie[left])
end

The worst case number of iterations of this algorithm is in the order of <math>\log \frac{d}{b}</math>, which is way better than simulating tick-by-tick.

Interpolating

Note that even though we have gaps, we can use the outcome of this algorithm to interpolate the returned scan with the scan right before it to fill in any missing scan, as the monotonicity of the question is well-defined even in the continuous domain.

You can estimate what is the missing scan when the impact occurred by a simple linear interpolation of both scans, or you can even binary search again to find the perfect impact point, but the former solution is way cheaper and often give sufficiently good approximations.

Caveats

Since we are not simulating the process tick-by-tick, we cannot identify when a robot comes out of the field and goes in again. We are only able to identify if its final position is inside the field. We can add some heuristics to the binary search, though, but they will only be heuristics and in many pathological cases they won't be helpful.

See also

• PIF