Learning and Applying Mathematics using Computing

Archive for the ‘Trigonometry’ Category

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.

Bouncing Off The Walls

In this post we will continue building our pool game. One of the aspects of a pool game that we will need is the ability for the balls to bounce off the edges/cushions of the table (which I’ll refer to as walls).

Simple Bouncing

If a wall is horizontal or vertical, there is a very simple way to implement bouncing off it, which many programmers figure out quite quickly. If you want to bounce off a horizontal wall (e.g. top or bottom of the screen), simply reverse your Y velocity. If you want to bounce off a vertical wall (e.g. left or right edge) then reverse your X velocity. These are actually two specific cases of the more general problem of bouncing off an arbitrarily-angled wall.

Any Which Way But Loose

The basic principle when bouncing is that the angle at which you hit the wall (orange line) should be mirrored when you bounce off (blue line):

The dotted line protruding perpendicularly from the wall, which acts as the mirror, is called the surface “normal”. Let’s rotate the wall and incoming angle and work out what the outgoing angle should be:

So, we have the incoming angle (which is calculated using the start of the incoming orange line, at the top left). We will assume we have the angle of the normal. What we want to know is the outgoing angle. If we label the gap between the incoming/outgoing as “diff”, then it’s fairly clear that:

\text{outgoing} = \text{normal} - \text{diff}

So, how do we work out diff? Well, we can calculate the angle at the end of the incoming arrow quite simply: it’s 180 degrees away from incoming. Then we can see by looking at the point of impact that:

\text{diff} = (180 + \text{incoming}) - \text{normal}

So overall, expanding this out:

\text{outgoing} = 2 \times \text{normal} - 180 - \text{incoming}

It’s a simple matter to implement straight-line walls that perform this collision resolution by bouncing balls using the normal angle:

        for (Wall w : (List<Wall>)getObjects(Wall.class))
        {
        
            if (w.intersectsCircle((int)newX, (int)newY, b.getRadius()))
            {
                double angle = Math.toDegrees(Math.atan2(vy, vx));
                int normalAngle = w.getNormalAngle((int)newX, (int)newY, b.getRadius());
                angle = 2 * normalAngle - 180 - angle;
                double mag = 0.9 * Math.hypot(vx, vy);
                
                vx = Math.cos(Math.toRadians(angle)) * mag;
                vy = Math.sin(Math.toRadians(angle)) * mag;
            }
        }

Jaws

The cushions on a pool table are not solely straight-lines, however. Next to the pockets, you have rounded sections: the jaws. I’m going to conceive of these sections as quarter-circles, as that makes the maths more straightforward. So we might have a situation like this, where the ball should bounce off the jaws:

We can use the same calculation for resolving bounces as before — we just need a surface normal angle. Well, the surface normal for a circle is actually trivial: it always points away from the centre of the circle, you just have to work out where you hit the edge. So using our previous diagram, the normal angle is just the angle pointing from the centre of the jaw quarter-circle towards the centre of the ball:

Pocketed

I’ve added some pockets to the scenario using some very simple maths: a ball goes in the pocket if its centre is over the pocket (not merely if part of the ball is over the pocket). You can have a play with the live scenario on the Greenfoot site — the cue ball heads towards the mouse when you click it. I may need to adjust the size of the pockets though, it may end up a bit hard to pocket anything!

Pooled Knowledge

In this post we’re going to start work on a pool game. Pool is quite a nice example for a game, because really it’s a two-dimensional game. The balls are always (trick shots aside!) on the table, so you can create the game as a 2D game viewed from above.

One of the key aspects of implementing a pool game is to detect when the balls collide with each other and make them bounce accordingly. When viewed in 2D, from above, the balls are simply circles. So in this post we’ll look at how to detect when two circles collide with each other.

The Shortest Path

Detecting whether circles collide is quite simple, but makes use of a crucial observation: if two circles collide at all, then they will collide along the line between their two centres.

To help you understand this, I’ve put together a little Greenfoot scenario. There are two circles, one stationary and one that you move around with the mouse. A line is drawn between their two centres. Move them around, and notice that you can’t make the circles touch without them overlapping along the line between the two centres.

So then, let’s consider that line between the two centres of two circles, which (as ever) can be viewed as the hypotenuse of a right-angled triangle formed by the X and Y axes:

We can work out the total length of the line between the centres using Pythagoras: we just calculate the X distance and Y distance between the centres using subtraction, then Pythagoras gives us the distance. So once we have the distance, how do we work out if the circles overlap? Well, we just need a little logic: if the distance between the two centres is smaller than the sum of the radiuses, the circles must be overlapping — as above. If, on the other hand, the distance is greater than the sum of the radiuses, the circles can’t be overlapping — as below:

(If the distance equals the sum, the circles are only just touching: whether you count this as a collision is a matter of preference).

The earlier scenario displays all the numbers I’ve been referring to, in the top right, so you can have a play if you want, over on the Greenfoot site. Next time we’ll start working on the actual pool scenario.