Mathematics In Greenfoot

This blog features a lot of content on applying mathematics in Greenfoot. You can see an index of all the interesting content here. Unfortunately I don’t think I will have time to follow through on my plan to collect all the content into an e-book (nor my plan to write some more content on probability), but all the existing content is here for free anyway. There’s also a few popular posts on XCOM which you can see below, but the majority of the site content was all the Greenfoot material, which I hope will continue to prove useful.

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!

Fruit Flies Like A Banana: Projectile Motion

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.

Doomed

Today’s trigonometry example comes from gaming history: the early days of what are now known as first-person shooters (FPS). But don’t worry, you don’t need to like or play FPS games to understand this post.

The first major FPS was Wolfenstein 3D, by id software. It used raycasting and texture mapping (both of which we’ve recently covered on this blog) to draw 3D graphics way before the existence of the specialised graphics cards we have today. Wolfenstein’s control scheme was quite simple. The up and down arrows moved you forward and back. The left and right arrows turned you. You could also hold down the Alt key, which would make the left and right arrows move you side-to-side, which came to be known as strafing. Strafing allowed you to more easily move into cover (as you could shoot an enemy, then sidestep behind cover, without having to turn away first).

Fast forward a year or two, and Doom was id software’s successor to Wolfenstein 3D. Graphically it was superior, and used cleverer algorithms underneath (which, if I’m honest, I never quite got my head around). Anyway, the interesting thing for this post is the control scheme. Doom allowed for more customisation of the controls, and introduced the now-ubiquitous idea of using the mouse to control movement, while using the keys to control forward/back and strafing.

Wonderfully, id software regularly release the source code of their old games as open-source. So here is the actual movement code from Doom:

if (gamekeydown[key_up]) 
    forward += forwardmove[speed]; //50
if (gamekeydown[key_down]) 
    forward -= forwardmove[speed]; //50
//...
if (gamekeydown[key_straferight]) 
     side += sidemove[speed]; //40
if (gamekeydown[key_strafeleft]) 
    side -= sidemove[speed]; //40

This works out the forwards and sideways movement, and later they use sine and cosine to translate this into movement at an angle — just as in our movement code (you can’t move at an angle without sine and cosine!).

There is an interesting issue with this movement code. You can use it to move in the obvious four directions — forwards (which I’m drawing as upwards), backwards, strafe-left or strafe-right — going slightly faster forward and back than strafing:

However, there is nothing stopping you pressing forwards and strafe-left or any other combination, giving a further four directions you can move (coloured red):

I’ve labelled the amount moved there as . What is the value of this distance? Well, it’s a simple case of Pythagoras. The two sides of the right-angled triangle in each case are 40 and 50, so Pythagoras tells us:

So you can actually move further diagonally than you can by simply moving forwards. In Doom, fast movement is an advantage: the faster you move, the harder you are to hit, and the quicker you can get away from monsters. So quite soon, people realised that when you move around in Doom, doing the obvious thing of moving forwards is slow: moving diagonally is much faster. This became known as strafe-running and was soon essential in competitive Doom matches.

It does mean that you need to face at an angle from the way you’re heading, making you slightly vulnerable to attack from the other side. And what angle is it that you need to run at? Well, that’s a case for inverse tangent:

Many later FPS games have “corrected” this oddity, by instead using the movement keys to decide which of the eight directions to head in, then moving the same amount no matter whether you’re going forwards or diagonally. But that original behaviour in Doom, coupled with basic geometry, added an extra dimension to Doom’s play.

Another Brick In The Wall

In our last post, we drew a 3D view of being in a maze-like grid of blocks. But all the walls were of single uniform colour, which is quite dull. The early 3D games that used our 3D technique, raycasting, almost immediately switched to using images for the walls rather than plain colours. These images were referred to as textures, and the technique for drawing them is known as texture mapping.

Texture mapping with raycasting is actually very simple. The idea is that each wall-block being drawn has an image on it. While drawing the wall-block pixel-by-pixel in 3D, texture mapping amounts to finding the corresponding pixel in the source image to use. We can label the face of each of the blocks in the world as having coordinates somewhere between (0, 0) and (1, 1):

The challenge is then for a given pixel, such as the red circle in the picture above, to find out which texture coordinates to use. These coordinates are typically labelled (u, v) to avoid confusion with other (x, y) coordinates. In raycasting, it’s quite easy to determine the (u, v). The u component is a matter of recording where exactly on the wall the ray hit. We already record the x and y coordinate of impact, and we know which face we hit. The u coordinate is just the fractional part of the appropriate x or y coordinate. If the ray hits the horizontal face of a block at (x, y) = 3.45, 6.00 then the u coordinate is 0.45.

As for the v coordinate: that is the relative height within the block we are currently drawing. In each column, we already know how tall the block appears. So the v coordinate is just a proportion of that total block height as we draw downwards.

Once we know the (u, v) coordinates, we just pick out the appropriate pixel from our texture image. If our texture is 256 by 256, and our (u, v) = (0.45, 0.29), then we use the pixel at (115, 74). (This is called nearest-neighbour texture mapping, and is fastest, but it can look a bit “jagged”. Most games now use some form of linear texture mapping that looks smoother)

Here’s the code:

            for (int wallY = 0; wallY <= 2 * height; wallY++)
            {
                double v = (double)wallY / (double)(2 * height);
                double u = r.getImageOffset();
                
                GreenfootImage texture = ((RaycastingWorld)getWorld()).getTextureFor(r.getX(), r.getY());
                
                Color c = texture.getColorAt((int)(u * (texture.getWidth() - 1)), (int)(v * (texture.getHeight() - 1)));
                
                int y = img.getHeight()/2 - height + wallY;
                if (y >= 0 && y < img.getHeight())
                {
                    img.setColorAt((int)column, y, c);
                }
            }

Here’s the texture:

And here’s a screenshot of what it looks like when used for texture-mapping:

You can play with the scenario yourself to see what it looks like as you turn round.