Learning and Applying Mathematics using Computing

In our last post, we saw how to do collision detection between bullets (modelled as an exact point) and asteroids (modelled as a circle). In this post we are going to upgrade our spaceship, and equip it with a laser for breaking up asteroids. This is going to involve a bit of equation re-arranging.

Space Lasers

A laser is a straight line projecting from the front of the spaceship. To do collision detection between the laser and the asteroid, we need to check whether a line intersects a circle. For that, we return to the mathematical representation of a line, representing our laser line as:

\begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} \text{spaceshipX} \\ \text{spaceshipY} \end{pmatrix} + \text{scalar} \times \begin{pmatrix} \text{dirX} \\ \text{dirY} \end{pmatrix}

We know from last time that the way to check if a particular point intersects a circle is to check the distance against the radius:

\sqrt{(x - \text{centreX})^2 + (y - \text{centreY})^2} \leq \text{radius}

To find out if any point on the line is inside the circle, we can actually subsitute our line equation into the circle equation, like so:

\sqrt{(\text{spaceshipX} + (\text{scalar}\times\text{dirX}) - \text{centreX})^2 + (\text{spaceshipY} + (\text{scalar}\times\text{dirY}) - \text{centreY})^2} \leq \text{radius}

This will tell us if any point on the line is inside the circle. In fact, for collision detection, all we need to check is if the line hits the outside of the circle. If the line touches the circle at all, we know that they intersect. Mathematically, we can change that less-than-or-equal-to into an equals (this will come in handy later on):

\sqrt{(\text{spaceshipX} + (\text{scalar}\times\text{dirX}) - \text{centreX})^2 + (\text{spaceshipY} + (\text{scalar}\times\text{dirY}) - \text{centreY})^2} = \text{radius}

The only unknown in that equation is \text{scalar}, so we need to rearrange for that — we can start by squaring both sides, because we know both sides will be positive:

(\text{spaceshipX} + (\text{scalar}\times\text{dirX}) - \text{centreX})^2 + (\text{spaceshipY} + (\text{scalar}\times\text{dirY}) - \text{centreY})^2 = \text{radius}^2

Let’s define a couple of helper variables to trim that down:

\text{distX} = \text{spaceshipX} - \text{centreX}
\text{distY} = \text{spaceshipY} - \text{centreY}

That gives us:

(\text{distX} + (\text{scalar}\times\text{dirX}))^2 + (\text{distY} + (\text{scalar}\times\text{dirY}))^2 = \text{radius}^2

\text{distX}^2 + (2\times\text{distX}\times\text{scalar}\times\text{dirX}) + (\text{scalar}^2\times\text{dirX}^2) + \text{distY}^2 + (2\times\text{distY}\times\text{scalar}\times\text{dirY}) + (\text{scalar}^2\times\text{dirY}^2) = \text{radius}^2

(\text{dirX}^2 + \text{dirY}^2) \times \text{scalar}^2 + ((2\times\text{distX}\times\text{dirX}) + (2\times\text{distY}\times\text{dirY}))\times\text{scalar} + \text{distX}^2 + \text{distY}^2 - \text{radius}^2 = 0

Phew! Now what we have is a quadratic equation, which we can solve using the standard quadratic formula. The quadratic formula tells us that any equation of the form ax^2 + bx + c can be rearranged to:

x = \displaystyle\frac{-b \pm \sqrt{b^2 - 4ac}}{2a}

And in fact, we don’t care what the value of x is, we just want to know if the equation has a solution: if it has a solution, the line touches the circle — if there is no solution, that’s because the line doesn’t touch the circle. The part which tells us whether there is a solution is the b^2 - 4 \times a \times c part — if this is 0 or higher (and thus can be square-rooted) then there is a solution, but if it’s negative then there’s no solution. From above, we have that:

x = \text{scalar}
a = \text{dirX}^2 + \text{dirY}^2
b = (2\times\text{distX}\times\text{dirX}) + (2\times\text{distY}\times\text{dirY})
c = \text{distX}^2 + \text{distY}^2 - \text{radius}^2

And thus our code for collision detection between the laser and the asteroid is:

        double dirX = Math.cos(Math.toRadians(getRotation()));
        double dirY = Math.sin(Math.toRadians(getRotation()));
        for (Asteroid asteroid : (List<Asteroid>)getWorld().getObjects(Asteroid.class))
            double distX = getX() - asteroid.getX();
            double distY = getY() - asteroid.getY();
            double a = dirX * dirX + dirY * dirY;
            double b = 2 * distX * dirX + 2 * distY * dirY;
            double c = distX * distX + distY * distY - asteroid.getRadius() * asteroid.getRadius();
            if (b * b - 4 * a * c >= 0)
                if (asteroid.hit(30))

And do you know what — it works! You can have a play live on the Greenfoot site.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s