Learning and Applying Mathematics using Computing

End of Season One

I started the sinepost blog about eight months ago, and since then I’ve written around thirty-five posts — more than one a week. I’ve primarily focused on geometry (and a little mechanics), building games that use mathematical concepts and techniques. I’ve covered most of the topics that I initially wanted to cover, so now seems like a good time for me to have a break from regular updates. It’s been a little tough at times to keep up the pace alongside my full-time job!

My hope is to now spend a few months compiling (and improving) the best of the geometry material together into a single e-book. I don’t know how long it will take, but watch out for an update around Christmas time. In the mean-time, there’s the archives for you to look at. Thanks for reading!

As well as being useful for working with triangles, the sine function can also be used for generating sounds. If you take an ever increasing number and pass it to the sine function, you get back this graph:

If you treat this as a sound wave, then you get a dull tone that we recognise as an electronic beep, since it’s used so often by electronic devices. Here’s an example of a sine wave on youtube.

We saw in our last post that for our monkeys-throwing-bananas game, we can work out how long the banana will be in flight for. We can use this information to construct a sound that’s exactly as long as the time the banana will spend in the air:

double lengthInSecs = timePerFrame  * (impactTime - 5);
short[] soundWave = new short[(int)(lengthInSecs * 44000.0)];

The sound will play at 44000 samples per second, so we need to multiply the number of seconds by 44000 to get the number of samples. The length of the sound in seconds will be the time it takes to execute one frame in Greenfoot, multiplied by the number of frames before impact (“impactTime”, above — which we saw how to calculate last post). I subtract 5 frames off the total, to make sure that the sound is finished before we need to play the impact sound.

Just playing a simple sine wave for the sound of the flight is dull and incongruous. We can greatly improve the suitability of the sound if we vary the frequency of the sine wave during the flight. If we change the frequency in proportion to the height of the banana, we get a sound that starts low, increases in pitch as the banana reaches the apex of its flight, then decreases again as it comes back down. This creates a more familiar flight sound (such as you hear in cartoons). The gist is something like this — the sine wave gets more frequent (the peaks get closer together, horizontally), the higher the projectile is in the air:

What this means is that instead of using a steadily-increasing number to feed to the sine wave function, you increase the number faster when the banana is higher. Here’s some code that does just that, using the height calculation from our previous post:

        double a = 0;
        for (int i = 0; i < soundWave.length; i++)
            // t is the frame number:
            double t = (double)i / (timePerFrame * 44000.0);

            a += 0.25 + (t * vy - 0.5 * g * t * (t - 1)) / 3200.0;
            soundWave[i] = (short)(8000 * Math.sin(a));

There are three constants in this code that I fiddled with until they sounded right (literally!). The 0.25 and the 3200 on the middle line of the loop adjust the amount that the height of the projectile affects the frequency of the sine wave. The 8000 in the last line is simply the volume of the sound (the height of the sine wave).

You can play with the finished game (including a couple of simple AI players) over on the Greenfoot site. Don’t forget to listen to the flight sounds!

Take Aim

In our last post, we implemented projectile motion as the start of a game involving monkeys throwing bananas. We saw that projectile motion always follows the same parabolic pattern, which will look something like this:

Since the projectile follows a straightforward motion pattern, we can actually predict, mathematically, where the projectile will land. To do this, let’s work out where the projectile will be, a certain number of frames after it has launched, given an initial velocity of h horizontally, and v vertically, with gravity set to some value g.

Horizontal Position

Recall that our horizontally velocity stayed constant — the banana moves the same horizontal distance each frame: h

The distance that the projectile will have moved horizontally is therefore very simple:

  • After 0 frames: 0
  • After 1 frame: h
  • After 2 frames: h + h = 2 \times h
  • After 3 frames: \text h + h + h = 3 \times h

It’s not hard to see that in general, the horizontal position after a given number of frames, f, will be:

\text{horizDist} = f \times h

Vertical Position

The vertical position of the projectile is more complex. The distance it moves (initially v) reduces by g each frame:

So, here’s the distance the projectile will have moved after the first few frames:

  • After 0 frames: 0
  • After 1 frame: v
  • After 2 frames: v + (v-g) = 2 \times v - g
  • After 3 frames: v + (v-g) + (v-g-g) = 3 \times v - g \times (1 + 2)
  • After 4 frames: v + (v-g) + (v-g-g) + (v-g-g-g) = 4 \times v - g \times (1 + 2 + 3)

So the overall pattern is that the position will be:

\text{vertDist} = f \times v - g \times \displaystyle\sum_{i=1}^{f-1} i

The last part describes the sum of the numbers from 1 up to f - 1 — that’s the (1+2+3) part from our pattern above. This need to sum up the numbers is the classic example for summation (wikipedia currently has it as its example for summation), and has the well-known result in mathematics that summing the numbers from 1 to n is equal to \frac{1}{2} \times n \times (n + 1), which we can use here (n being f - 1):

\text{vertDist} = f \times v - g \times \frac{1}{2} \times (f - 1) \times f

Predicting the landing

So we now have formulae for the horizontal and vertical distance of the projectile (in our case, a banana). The question we want to answer is: where will the banana land? For this, we use the fact that in our game, the banana only lands when the vertical distance reaches zero again (i.e. when the banana returns to ground level), so we can use that to work out how many frames it will be in flight for. Then, once we know the number of frames before it lands, we can then work out how far it will have gone horizontally. So we need to solve for when vertical distance is zero:

0 = \text{vertDist}
0 = f \times v - g \times \frac{1}{2} \times (f - 1) \times f
0 = f \times v - \frac{g}{2} \times (f^2 - f)
0 = f \times v - (\frac{g}{2} \times f^2 - \frac{g}{2} \times f)
0 = (v + \frac{g}{2}) \times f - \frac{g}{2} \times f^2

What we have here is a quadratic for f, which we can solve with the usual quadratic formula, where:

a = -\frac{g}{2}
b = v + \frac{g}{2}
c = 0

This gives our next step, by filling in the quadratic formula:

f = \displaystyle\frac{-(v + \frac{g}{2}) \pm \sqrt{(v + \frac{g}{2})^2 - 0}}{2 * -\frac{g}{2}}

f = \displaystyle\frac{-(v + \frac{g}{2}) \pm (v + \frac{g}{2})}{-g}

f = \textbf{either~~} 0 \textbf{~~or~~} \displaystyle\frac{-2 \times (v + \frac{g}{2})}{-g}

f = \textbf{either~~} 0 \textbf{~~or~~} \displaystyle\frac{2 \times v + g}{g}

f = \textbf{either~~} 0 \textbf{~~or~~} 2 \times \displaystyle\frac{v}{g} + 1

Now, the solution where = 0 refers to when the banana is launched, so we can ignore that solution. We want the other solution, which says that the banana will land after 2 \times \frac{v}{g} + 1 frames. In our example above, the banana was launched with v = 5, g = 1, so we can predict correctly that it lands after 2 \times \frac{5}{1} + 1 = 11 frames.

The advantage of doing all this maths is that our code ends up nice and simple for calculating the horizontal impact of the banana:

        double vx = Player.getVelX(radianAngle, forceFactor);
        double vy = Player.getVelY(radianAngle, forceFactor);
        double impactTime = 2.0 * (vy / ProjectileWorld.GRAVITY) - 1;
        double impactX = player.getX() + impactTime * vx;

I’ve added this to the scenario so that you can have a play. You can see that the cross on the ground moves as you aim, and once you fire, it correctly predicts where the banana will land. Having the visible target makes our scenario a bit too easy for human players, but the calculation will be useful in future posts.

Simple projectiles have been popular in games for a long time. Angry Birds recently combined it with collision physics to great success, but long ago, games like Worms and (my personal favourite) Scorched Earth were using projectiles as their central game mechanic. A projectile, for the purpose of this post, refers to an object that is launched through the air with a certain initial velocity, but after launch the motion is only affected by gravity, which makes the projectile follow a curve through the air known as a parabola:

The Game

Our next game will involve monkeys throwing bananas at each other. The monkeys will stand still, and our bananas will act like simple projectiles.

To implement a projectile, we must first give the projectile an initial X and Y motion — in our case, that’s decided by where the player clicks to launch a banana. The projectile then keeps its horizontal (X) motion constant — it’s always flying sideways at the same speed. What varies is its vertical (Y) motion. It starts off being a high velocity upwards. Then, each frame, the vertical velocity is reduced by gravity, until it tips past zero and the velocity becomes negative, heading downwards. Let’s illustrate this.

First, the banana is thrown, with an initial velocity — it is moving 5 squares upwards and 2 squares sideways each frame:

We will set gravity to be one square reduction in velocity per frame. So the second frame, the banana still moves 2 squares sideways — its horizontal velocity is never altered — but only four squares upwards:

The same happens in the next few frames — same sideways velocity, but upwards velocity is reduced by one square each frame, until it reaches zero:

So the vertical velocity has been 5, then 4, 3, 2, 1 and now 0 squares upwards. The pattern doesn’t alter just because the banana reached its peak — the next frame it becomes -1:

Then it becomes -2, -3, -4 and -5, until the banana hits the ground:

So in summary: you can see that the banana in the diagram starts off with an upwards velocity of five. Each turn the velocity is reduced by one, and the effect this has is to reduce the banana’s velocity to zero, then make it increasingly negative. These two simple components — high initial upwards velocity, then constant reduction each frame — give the flight this parabola.

The code to implement the banana’s flight is very short:

    private void fly()
        velY -= ProjectileWorld.GRAVITY;
        moveTo(curX + velX, curY - velY);

I take positive Y velocity to be upwards, so I subtract the effect of gravity, but then because Greenfoot has Y going downwards, I must subtract the upwards velocity for everything to work out. You can see how this works by playing with the example scenario on the Greenfoot website.

In this post, we will finally complete our pool game. We’ve already seen how to detect collisions between balls: we just need to check if two circles are overlapping. We’ve also seen how to resolve a collision when bouncing a ball off a wall (i.e. one moving object and one stationary). The final piece of the puzzle is just to put it all together in the case of two moving balls.

Bouncy Balls

The principle behind collision resolution for pool balls is as follows. You have a situation where two balls are colliding, and you know their velocities (step 1 in the diagram below). You separate out each ball’s velocity (the solid blue and green arrows in step 1, below) into two perpendicular components: the component heading towards the other ball (the dotted blue and green arrows in step 2) and the component that is perpendicular to the other ball (the dashed blue and green arrows in step 2).

This is the same principle as we used when colliding with a wall. The difference here is that while you still leave alone the components that are parallel, instead of reversing each ball’s component that heads towards the other ball, you swap the components between the two balls (as we move from step 2 to step 3), then finally recombine the velocities for each ball to leave the result (step 4):

This means that the code we need is actually only a small modification on the previous code for wall collision:

                double towardsThem = distAlong(b.getMoveX(), b.getMoveY(), distX, distY);
                double towardsMe = distAlong(c.getMoveX(), c.getMoveY(), distX, distY);
                double myOrtho = distAlong(b.getMoveX(), b.getMoveY(), distY, -distX);
                double theirOrtho = distAlong(c.getMoveX(), c.getMoveY(), distY, -distX);

                b.setMove(towardsMe * distX + myOrtho * distY,
                          towardsMe * distY + myOrtho * -distX);
                c.setMove(towardsThem * distX + theirOrtho * distY,
                          towardsThem * distY + theirOrtho * -distX);

You can have a play with the relevant scenario over on the Greenfoot site.

Programming Challenge Task

The scenario needs a bit more work to make a finished game: interface polish, a second player (with two types of balls, and a black 8-ball) and scoring. Feel free to take the code and finish off the game.

Mathematical Challenge Task

The collision resolution is not as precise as it could be. Because it uses the destination position at the end of the frame for resolving the collision, two balls which move towards each quickly can potentially bounce off at a strange angle. This could be fixed by modelling a ball’s position as:

\begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} \text{startX} \\ \text{startY} \end{pmatrix} + t \times \begin{pmatrix} \text{moveX} \\ \text{moveY} \end{pmatrix}

Where t varies from 0 (at the start of the frame) to 1 (at the end). You can then find at which value of t the two balls collide (building on the circle collision work), and use these positions of the exact collision when resolving the collision. If you feel like a challenge, have a go at using that idea to improve the collision mechanism.