Learning and Applying Mathematics using Computing

This post is about wrapping coordinates so that when you go off one side of the world, you come back on the opposite side, or: one use of modular arithmetic.

A feature that used to be quite prevalent in 2D games was a “wrapped” world: when you reached the right-hand side of the world, instead of stopping or bouncing off, you would appear on the left-hand side (and vice versa). The top and the bottom of the world would usually operate in a similar way. Asteroids is a classic example, but various other arcade and strategy (Settlers, Civ, etc) games have used the same mechanism.

The Simple Method

The simple way to implement world-wrapping is to check if the location you are trying to move to is beyond the bounds of the world: if it is, then move to the opposite border of the world.

In Greenfoot, we must be careful about how to implement this, because Greenfoot already prevents your location from going outside the world. So if you try to implement world-wrapping along these lines:

setLocation(getX() - 5, getY()); // Move 5 units left
if (getX() < 0)
    ...

The above won’t work: the setLocation method will already have prevented you moving beyond x=0, so getX() will never be negative.

Instead this check must be done before you tell Greenfoot to set the location. The easiest way to do this is to override (i.e. replace) the setLocation method to add in this check, before calling the original setLocation method. Here’s the code for wrapping just the x coordinate:

    public void setLocation(int x, int y)
    {
        if (x >= getWorld().getWidth())
        {
            x = 0;
        }
        if (x < 0)
        {
            x = getWorld().getWidth() - 1;
        }
        
        super.setLocation(x, y);
    }

The first if-statement checks if the desired X coordinate is greater than or equal to the world width (say, 640). If it is, it is moved to the opposite side: x=0. The second if-statement checks if the desired X coordinate is negative, and if it is, it is moved to the maximum X coordinate: world-width minus one (e.g. 639). Finally, we pass the potentially-adjusted coordinates to the original setLocation method.

The logic for the Y coordinates is identical, but using the world height instead of width. I’ve uploaded the Greenfoot scenario with simple X and Y wrapping implemented for you to have a play, or to download and view the source.

The More Accurate Method

There is a small issue with our previous method. Let’s say you have a small, 20-wide world, and you are at position (14, 2), heading exactly right at 5 units per frame. You’ll move to (19, 2) — no problem. Then the next frame after that, you’ll try to move to (24, 2), and then the above code will kick in and you’ll get placed at (0, 2). Here’s a diagram of that:

From this diagram, the problem may not be totally obvious. But since our world is wrapped, it should be as if the left-hand edge is directly next to the right-hand edge. When we draw it like that, we can see the problem:

From this diagram, you can see that in effect we only moved 1 unit rather than 5. So every time you cross the world boundary, you have a “slow frame” where you don’t move as far. This is not very noticeable with low speeds, but it can become noticeable with higher speeds, or if you have multiple actors in formation. If we were at (19, 2), we should have moved to (4, 2). Similarly, if we were at (18, 2), we should have moved to (3, 2), and so on. You’ll notice the pattern is that we are subtracting 20 (the world width) from the coordinate we would normally move to. So (19, 2) should move to (24, 2), but we instead move to (4, 2). You can also see that the logic works the other way: (4, 2) should move to (-1, 2) if they are moving 5 units left, but instead they move to (19, 2). So in that case we add on the world width. Let’s set this down in code:

    public void setLocation(int x, int y)
    {
        int width = getWorld().getWidth();
        int height = getWorld().getHeight();
        
        if (x >= width)
        {
            x -= width;
        }
        if (x < 0)
        {
            x += width;
        }

        if (y >= height)
        {
            y -= height;
        }
        if (y < 0)
        {
            y += height;
        }
        
        super.setLocation(x, y);
    }

You can go have a play with this improved version. And as a quick exercise: this code isn’t completely foolproof. See if you can work out why not and figure out the simplest fix, before you take a look at the source code (which does have the foolproof answer).

The Technical Term

This wrapping of coordinates is an example of modular arithmetic (a quick overview is available on Simple Wikipedia). Other examples of modular arithmetic include hours on the 24-hour clock: after 23 you go back to 0, or degrees: after 359 degrees you go back to 0 degrees. And in fact, if you know a little about computer arithmetic, you’ll know that addition and subtraction on many finite integer types in computing resemble modular arithmetic: for example, if you try to add 1 to a byte value of 127 in Java, you’ll get -128. There are several more uses of modular arithmetic in computing, and I will come back to some of them in future.

As a final note, some of you may know that Java has a “modulo” operator — but that operator is not very useful for solving the problem in this post. I leave it to you as an exercise to figure out why not. (Why not try modifying my code to use the modulo operator?)

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