Learning and Applying Mathematics using Computing

Checkpoint!

In a recent post, we had a bus racing around a track. A nice finishing touch would be to add a facility to measure lap-times. But how can you measure when someone has completed a lap? The first step is to mark out a finish line, and find out when they cross that line. The second step is to add lots of similar lines (checkpoints) around the map, to avoid the player being able to just drive backwards and forwards across the finish line to complete their laps! This final post of our racing scenario features more equations than usual, as we reach completion of our bus-racing scenario.

Crossing the Line

In our last post, we looked at how to define finite lines. Our finish line (and checkpoints) will be finite lines that stretch across the track. We can also represent a bus’s travel in a given frame as a finite line (from the point it began the frame at, to the point it ends the frame at). Thus, if we have a way to determine if two finite lines cross, we can work out if (the centre of) the bus crossed the finish/checkpoint line this frame, i.e. check if the red and black lines cross in this diagram:

The way to determine if two finite lines cross is first to work out if the infinite versions of the lines would cross, then work out if the crossing point is within the finite range of the lines that we’re interested in.

Crossing Place

Let’s get to the maths. We have a checkpoint line which goes from (xCheckStart, yCheckStart) to (xCheckEnd, yCheckEnd), which we can express in the following form:

\begin{pmatrix} \text{x} \\ \text{y} \end{pmatrix} = \begin{pmatrix} \text{xCheckStart} \\ \text{yCheckStart} \end{pmatrix} + \text{checkDist} \times   \begin{pmatrix} \text{xCheckEnd} - \text{xCheckStart} \\ \text{yCheckEnd} - \text{yCheckStart} \end{pmatrix}

We also have the bus’s motion in an identical form:

\begin{pmatrix} \text{x} \\ \text{y} \end{pmatrix} = \begin{pmatrix} \text{xBusStart} \\ \text{yBusStart} \end{pmatrix} + \text{busDist} \times   \begin{pmatrix} \text{xBusEnd} - \text{xBusStart} \\ \text{yBusEnd} - \text{yBusStart} \end{pmatrix}

Each of these expressions defines an (x, y) point on the respective lines. Finding out whether the lines cross is the same as checking if there is an (x, y) point that lies on both lines. For this, we set the line equations equal to each other:

\begin{pmatrix} \text{xCheckStart} \\ \text{yCheckStart} \end{pmatrix} + \text{checkDist} \times   \begin{pmatrix} \text{xCheckEnd} - \text{xCheckStart} \\ \text{yCheckEnd} - \text{yCheckStart} \end{pmatrix} =\\ \begin{pmatrix} \text{xBusStart} \\ \text{yBusStart} \end{pmatrix} + \text{busDist} \times   \begin{pmatrix} \text{xBusEnd} - \text{xBusStart} \\ \text{yBusEnd} - \text{yBusStart} \end{pmatrix}

A Little Help From Our Friends

To make these equations a bit shorter, I’m going to introduce some helper variables:

\text{xCheck} = \text{xCheckEnd} - \text{xCheckStart}
\text{yCheck} = \text{yCheckEnd} - \text{yCheckStart}
\text{xBus} = \text{xBusEnd} - \text{xBusStart}
\text{yBus} = \text{yBusEnd} - \text{yBusStart}

This makes our equation a bit shorter:

\begin{pmatrix} \text{xCheckStart} \\ \text{yCheckStart} \end{pmatrix} + \text{checkDist} \times   \begin{pmatrix} \text{xCheck} \\ \text{yCheck} \end{pmatrix} = \begin{pmatrix} \text{xBusStart} \\ \text{yBusStart} \end{pmatrix} + \text{busDist} \times   \begin{pmatrix} \text{xBus} \\ \text{yBus} \end{pmatrix}

The next thing to do is split the equations out into the X and Y parts. You are always allowed to do this with vector equations:

1.~~\text{xCheckStart} + \text{checkDist} \times   \text{xCheck} = \text{xBusStart} + \text{busDist} \times   \text{xBus}
2.~~\text{yCheckStart} + \text{checkDist} \times   \text{yCheck} = \text{yBusStart} + \text{busDist} \times   \text{yBus}

This looks like a lot of variables, but there’s actually two classes of variables involved here. One is variables that we will know the value of (the checkpoint start and end, bus start and end), but which will be different each time, so we represent them with variables — in programming terms, these are like parameters to a method to solve the problem. The other class is variables that we need to work out: these are busDist and checkDist, which are the distances along the two lines. In programming terms, these will be the result variables (like the ones you might return from a method).

Solving The Equations

What we need to do here is solve some simultaneous equations (which you may remember from maths class), but our task is made more difficult by having variables as coefficients rather than numbers. I’m going to whizz through, to avoid making this post interminably long. First, let’s get the checkDists on one side:

1.~~\text{checkDist} \times   \text{xCheck} = \text{xBusStart} - \text{xCheckStart} + \text{busDist} \times   \text{xBus}
2.~~\text{checkDist} \times   \text{yCheck} = \text{yBusStart} - \text{yCheckStart} + \text{busDist} \times   \text{yBus}

Now let’s multiply the equations by yCheck and xCheck respectively, to get the same thing on the left-hand side of both equations:

1.~~\text{checkDist} \times   \text{xCheck} \times \text{yCheck} = \text{yCheck} \times (\text{xBusStart} - \text{xCheckStart}) + \text{busDist} \times   \text{xBus} \times \text{yCheck}
2.~~\text{checkDist} \times   \text{xCheck} \times \text{yCheck} = \text{xCheck} \times (\text{yBusStart} - \text{yCheckStart}) + \text{busDist} \times   \text{yBus} \times \text{xCheck}

Now that we have the same thing on both left-hand sides, we know that the two right-hand sides should be equal to each other:

\text{yCheck} \times (\text{xBusStart} - \text{xCheckStart}) + \text{busDist} \times   \text{xBus} \times \text{yCheck} = \text{xCheck} \times (\text{yBusStart} - \text{yCheckStart}) + \text{busDist} \times   \text{yBus} \times \text{xCheck}

Now we can gather all the busDist on one side:

\text{busDist} \times   \text{xBus} \times \text{yCheck} - \text{busDist} \times   \text{yBus} \times \text{xCheck} = \text{xCheck} \times (\text{yBusStart} - \text{yCheckStart}) - \text{yCheck} \times (\text{xBusStart} - \text{xCheckStart})

Factorise:

\text{busDist} \times   (\text{xBus} \times \text{yCheck} - \text{yBus} \times \text{xCheck}) = \text{xCheck} \times (\text{yBusStart} - \text{yCheckStart}) - \text{yCheck} \times (\text{xBusStart} - \text{xCheckStart})

Divide:

\text{busDist} = \frac{\text{xCheck} \times (\text{yBusStart} - \text{yCheckStart}) - \text{yCheck} \times (\text{xBusStart} - \text{xCheckStart})}{  \text{xBus} \times \text{yCheck} - \text{yBus} \times \text{xCheck}}

The solution for checkDist, using similar logic, is as follows:

\text{checkDist} = \frac{\text{xBus} \times (\text{yCheckStart} - \text{yBusStart}) - \text{yBus} \times (\text{xCheckStart} - \text{xBusStart})}{  \text{xCheck} \times \text{yBus} - \text{yCheck} \times \text{xBus}}

Notice that one divisor is simply the negation of the other. If this divisor is zero (which would lead to a division by zero) it means that the direction of the lines is parallel. For our bus and checkpoint example, we can just count this as not-crossing. In all other cases, we plug in the numbers to get values for busDist and checkDist. If both numbers are between 0 and 1 inclusive, then the bus has crossed the checkpoint line this frame. (If checkDist is outside the 0–1 range, it means you’ve gone to one side of the ends of the checkpoint line. If busDist is less than 0, it means the checkpoint is already behind you, and if busDist is greater than 1, it means the checkpoint is still ahead of you.)
To give you an idea of how directly that translates into code, here’s the relevant section:

        double xCheck = checkpoint[1][0] - checkpoint[0][0];
        double yCheck = checkpoint[1][1] - checkpoint[0][1];
        
        double xBus = endX - startX;
        double yBus = endY - startY;
        
        double denom = xBus * yCheck - yBus * xCheck;
        
        if (denom == 0)
            return; //Parallel lines
        
        double busDist = (xCheck * (startY - checkpoint[0][1]) - yCheck * (startX - checkpoint[0][0])) / denom;
        double checkDist = (xBus * (checkpoint[0][1] - startY) - yBus * (checkpoint[0][0] - startX)) / -denom;
        
        if (busDist >= 0 && busDist <= 1 && checkDist >= 0 && checkDist <= 1)
        {

The maths we used to solve this was not complex in itself, it was just laborious and featured a lot of variables. Now you can have a play with the scenario, and try and set a fast laptime! If you’re logged in to the Greenfoot website, your high score will be recorded at the end of the fifth lap.

Advertisements

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s