RTanque Collision Detection Improvements

Introduction

As of version 0.1.1, RTanque seems to have a few undesirable behaviors with collision detection.

One behavior is that shots disappear as soon as they're off the screen. This would be okay, except that tanks are allowed to be positioned to that their centers are on the edge of the screen. This means that a tank that's in the corner is effectively only one-quarter as large as a tank in the middle of the arena.

The fix for this is easy: Just allow shots to exist a little bit outside the arena. Then shots will be able to hit the part of the tank that's not visible on-screen.

However, there's another problem, related to the fact that RTanque uses discrete time intervals called "ticks." Instead of traveling continuously, moving shots (and moving tanks) warp to a short distance away once every tick. There's nothing inherently wrong with programming a game using ticks—in fact, you essentially have to do it that way, since a standard computer processor takes discrete instructions. But using discrete time units can create problems with collision detection if you aren't careful.

Let's say we have a stationary tank (represented by a blue circle), and a shot moving directly upwards (represented by an orange circle). The following situation can happen from one tick to the next:

At tick 117, a shot is directly below a tank;
at tick 118, the same shot is directly above that tank

If collision detection is programmed just to check whether the shot is inside the circle (as in RTanque 0.1.1), then these two objects will never register as having collided, even though they "should" have collided. (At least, they should have in Newtonian physics, where time is continuous.)

Therefore, I propose the following: Instead of simply checking whether a shot is inside a tank, RTanque should instead check whether the shot would have been inside the tank at any time during the last tick, using Newtonian physics and assuming all velocities constant over the last tick.

Since our time unit is so short, then assuming velocities to be constant won't be a big deal. To be precise: Since shots can't accelerate and tank acceleration is capped at 0.05 pixels per tick per tick, then assuming constant velocities introduces an error of at most 0.05 pixels in the tank's position, and no error in the shot's position. This will cause a shot to register as missing when it "should" have hit (or vice versa) only when it is within one pixel of doing so. (Even if the shot is within one pixel, this will occur at most 5% of the time.)

Proposed Collision Computation

Now, I will derive a test for collision detection which uses approximately Newtonian physics, as described above. In other words, WARNING: MATH AHEAD.

Suppose we have a shot with current position vector $\langle a, b \rangle$ and current velocity $\langle v, w \rangle$. Suppose also that we have a tank with current position vector $\langle h, k \rangle$ and current velocity $\langle p, q \rangle$. (For purposes of collision detection, a "tank" is a circle with radius 19 centered at its position.) Let us try to determine whether the shot entered the tank during the last tick.

Let $t$ be the number of ticks elapsed since the current time. If the velocities involved are constant, then the position of the shot at time $t$ is $\langle a, b \rangle + t \langle v, w \rangle$, which simplifies to $\langle a + tv, b + tw \rangle$; and the position of the tank at time $t$ is $\langle h, k \rangle + t \langle p, q \rangle$, which simplifies to $\langle h + tp, k + tq \rangle$. Now, the shot will be inside the tank at time $t$ just when it's no more than 19 pixels away from the tank's position; that is, when the following inequality is true:

\[ \| \langle a + tv, b + tw \rangle - \langle h + tp, k + tq \rangle \| \leq 19 \]

Since collision detection is run whenever $t$ is an integer, we need to check whether this condition was true at some time during the last tick. Since the shot is still there, it hadn't hit anything one tick ago; so the quantity $\langle a + tv, b + tw \rangle - \langle h + tp, k + tq \rangle$ was greater than 19 one tick ago. Thus, by the Intermediate Value Theorem, the length of $\langle a + tv, b + tw \rangle - \langle h + tp, k + tq \rangle$ can't have become less than 19 during the last tick unless it was also equal to 19 at some point during the last tick. So we may as well check whether the equation

\[ \| \langle a + tv, b + tw \rangle - \langle h + tp, k + tq \rangle \| = 19 \]

was true at some time during the last tick. In other words, we want to solve this equation for $t$, and then determine whether any of the solutions satisfy $-1 \leq t \leq 0$. Let's unpack this equation, using some properties of vectors and some algebra:

\[ \| \langle a + tv, b + tw \rangle - \langle h + tp, k + tq \rangle \| = 19 \]\[ \| \langle a + tv - h - tp, b + tw - k - tq \rangle \| = 19 \]\[ \sqrt{(a + tv - h - tp)^2 + (b + tw - k - tq)^2} = 19 \]\[ (a + tv - h - tp)^2 + (b + tw - k - tq)^2 = 19^2 \] \[ ((a - h) + t(v - p))^2 + ((b - k) + t(w - q))^2 = 19^2 \]

To aid readability and computation, let us set $\Delta x = a - h$, $\Delta y = b - k$, $\Delta v = v - p$, and $\Delta w = w - q$. (Note that each of these four quantities represents the difference between a characteristic of the shot and the corresponding characteristic of the tank.) Continuing with the algebra, we obtain

\[ (\Delta x + t \Delta v)^2 + (\Delta y + t \Delta w)^2 = 19^2 \] \[ (\Delta x)^2 + 2t\Delta x \Delta v + t^2(\Delta v)^2 + (\Delta y)^2 + 2t\Delta y \Delta w + t^2(\Delta w)^2 = 19^2 \]\[ [(\Delta v)^2 + (\Delta w)^2]t^2 + [2\Delta x \Delta v + 2\Delta y \Delta w]t + [(\Delta x)^2 + (\Delta y)^2 - 19^2] = 0 \] This is a quadratic equation in $t$, so we can solve it using the quadratic formula; the two solutions are \[ t = \frac{-2 \Delta x \Delta v - 2 \Delta y \Delta w \pm \sqrt{(2 \Delta x \Delta v + 2 \Delta y \Delta w)^2 - 4 [(\Delta v)^2 + (\Delta w)^2][(\Delta x)^2 + (\Delta y)^2 - 19^2]}} {2[(\Delta v)^2 + (\Delta w)^2]} \]

Therefore, to check whether the shot was ever in the tank during the last tick, we have a two-step process:

  1. Is the quantity under the square root negative? If so, then there is no real solution for $t$, so there was no collision
  2. Otherwise, is either solution between -1 and 0? If so, then the shot collided with the tank during the last tick; if not, then it didn't.

Finally, two special cases to consider: First, it's possible for $(\Delta v)^2 + (\Delta w)^2$ to be zero, making the formula above undefined. (This happens when the tank and the shot have the same velocity vector.) Second, if the shot has just been produced, then checking what happened for $-1 \leq t \leq 0$ doesn't make sense (and would cause a shot to immediately hit things slightly behind the tank that fired them). In either of these cases, we can just revert to the old behavior of checking whether the shot is inside the tank or not.

Code

I've made these two changes to the collision detection in the RTanque code, and uploaded them to my fork of RTanque on GitHub. So far, it appears to work fine. Feel free to email me at doug@dougbabcock.com if you have any comments.

Created 8 October 2013.
Last updated 8 October 2013.

HTML5 Powered Valid CSS!