Learning and Applying Mathematics using Computing

Archive for the ‘Geometry’ Category

Flight Music

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!

Advertisements

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.

Making Your Balls Bounce

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.

Bouncing Off The Walls, More Productively

In a previous post we saw one way to bounce a ball off walls, by using angles and rotation. In maths, there are often several ways to approach a problem, with different techniques that can be used to achieve the same result. In this post, I’m going to solve the same problem of bouncing off the walls, but using a different technique: the dot product.

Rethinking Bouncing

One way to think about bouncing off a wall is that the angle gets reflected around the surface normal (the dotted line), as we saw last time:

Another way to think about the bouncing is that the velocity parallel to the surface (perpendicular to the normal) is maintained, and the velocity perpendicular to the surface (parallel to the normal) is reversed. This can be seen in the diagram below — the coloured vectors on the left are equivalent to the sum of their dotted/dashed counterparts on the right, where the component parallel to the surface is kept constant, but the component perpendicular to the surface is reversed:

Implementing this for horizontal or vertical walls is easy, but how do you do this when the normal is at an arbitrary angle, such as the jaws of the pocket?

The Dot Product

What we need to do is be able to split a vector into two components: one being the distance in the direction along the normal, the other being the distance along a vector perpendicular to the normal. The easiest way to do this is to use something called the dot product. The dot product of two vectors refers to multiplying the X components together, and the Y components together:

\begin{pmatrix} \text{aX} \\ \text{aY} \end{pmatrix} \cdot \begin{pmatrix} \text{bX} \\ \text{bY} \end{pmatrix} = \text{aX} \times \text{bX} + \text{aY} \times \text{bY}

By itself, this is of no use, but the dot product has an important theorem attached to it:

\textbf{a} \cdot \textbf{b} = |\textbf{a}| \times |\textbf{b}| \times \cos(\text{angle})

(where \textbf{a} and \textbf{b} are vectors, \text{angle} is the angle between them, and |\textbf{a}| is the length of the vector, which can be calculated using Pythagoras.) The reason this is useful is that if you have two vectors, calculating what is known as the “projection” of one on to another looks like this:

The distance along the new vector is \text{dist} = |\textbf{a}| \times cos(\text{angle}), which from rearranging the dot product result, we know to be:

\displaystyle\frac{\textbf{a} \cdot \textbf{b}}{|\textbf{b}|} = |\textbf{a}| \times \cos(\text{angle}) = \text{dist}

So, we can add a method to calculate the distance along a particular vector, using \displaystyle\frac{\textbf{a} \cdot \textbf{b}}{|\textbf{b}|}:

    private double distAlong(double x, double y, double xAlong, double yAlong)
    {
        return (x * xAlong + y * yAlong) / Math.hypot(xAlong, yAlong);
        
    }

Get Bouncing

Our aim in this post is to bounce off walls. So we can use that distAlong method to calculate the distance along the normal, and reverse it. But we also need to calculate the distance along a vector perpendicular to the normal (parallel to the wall). How can we calculate a vector that’s perpendicular to the normal? It turns out that in 2D there’s a really quick, simple way to rotate a vector 90 degrees: swap the X and Y components and negate one of them (challenge for you: why/how does this work?). That gives our final code for doing the bouncing:

                double normalX = w.getNormalX((int)newX, (int)newY, b.getRadius());
                double normalY = w.getNormalY((int)newX, (int)newY, b.getRadius());
                double distPerpWall = distAlong(vx, vy, normalX, normalY);
                double distParWall = distAlong(vx, vy, normalY, -normalX);
                
                //Bounce:
                distPerpWall = -distPerpWall;
                
                vx = distParWall * normalY + distPerpWall * normalX;
                vy = distParWall * -normalX + distPerpWall * normalY;

As a reminder of what that code is doing, here’s a final diagram. First (1), we calculate the normal (the black dashed line, below). Then (2) we split the incoming velocity, vx and vy, into the distance perpendicular to the wall (the orange dashed arrow, below) and the distance parallel to the wall (the orange dotted arrow, below). Next (3) we flip the direction of the dashed arrow to get the resulting blue arrows describing the velocity after the bounce, and (4) we convert the sum of those two vectors back into the new velocity, which we store back into vx and vy:

I haven’t bothered to upload the new scenario, because it behaves identically to the previous scenario! Next post we will finally implement collisions between the balls (which will again use the dot product), and then I will upload the final scenario featuring this code and the ball collision code.

Rack ‘Em Up

In recent posts, we’ve been building a pool game. One aspect of pool that we need to implement is positioning the balls for the start. There are fifteen balls to line up in a tightly packed triangle. But to actually put down this triangle in a program, we need to know the exact coordinates of the balls! And it turns out, this needs some maths too.

Rows

You can think of the triangle of balls as being a series of rows, each with one ball more than the last:

Each ball in a left-hand row has two balls behind it in the right-hand row. The gap between the balls on the right must align with the centre of the ball on the left (the dotted line below), and the balls nestle so close that the distance between each pair must be the same (the solid line below):

We can now start labelling the distances on this diagram. If the balls exactly touched then the distance between the two centres would be two times the ball radius. But due to the way our collision detection will work, it’s best if the balls don’t completely touch, but instead have a small gap. So we’ll define \text{radiusPlus} to be slightly bigger than the ball radius, which will give us this gap. Then:

So we know the vertical distances between the centres. All we need now is the horizontal distance (i.e. the length of the dashed line above). This is actually just a case for Pythagoras:

\text{horizDist}^2 + \text{radiusPlus}^2 = (2 \times \text{radiusPlus})^2
\text{horizDist}^2 + \text{radiusPlus}^2 = 4 \times \text{radiusPlus}^2
\text{horizDist}^2  = 3 \times \text{radiusPlus}^2
\text{horizDist}  = \sqrt{3} \times \text{radiusPlus}

Here’s the code:

        final int radiusPlus = 25 + 2; //radius + 2
        for (int row = 0; row < 5; row++)
        {
            int startY = 300 - row * radiusPlus; // Each row starts radiusPlus further up
            int x = 500 + (int)(row * (Math.sqrt(3) * (double)radiusPlus));
            for (int ball = 0; ball < row + 1; ball++)
            {
                addObject(new PoolBall(Color.RED), x, startY + ball * (2 * radiusPlus));
                // Each ball in a row is 2*radiusPlus further down ^^
            }
        }

This gives the finished layout:

I haven’t uploaded the scenario because it’s only the small bit of code above that has been added. Next time we’ll look at adding collision detection and collision resolution.