Learning and Applying Mathematics using Computing

We saw very early on in this blog how to make an actor aim for a target location. One way to use this is for enemies chasing you in games, or things like commanding units in strategy games. But what if the world is based on a small number of squares (like a chess-board), where movement is only allowed horizontally and vertically, not diagonally?

Distance

How far away is the wombat from the leaf (in terms of grid squares)?

If you’ve been reading this blog for a while, your answer is hopefully to reach for Pythagoras, and perhaps come up with \sqrt{6^2 + 3^2} = \sqrt{45} = 6.71 (\text{to 2dp}). This is true, but traditionally in Greenfoot, wombats are only allowed to move horizontally or vertically into adjacent squares. The diagonal distance is not helpful in this situation, because it doesn’t tell you how far the wombat has to move to reach the leaf.

Shortest Route

To measure how far the wombat is from the leaf, let’s first find the shortest path (least squares) that the wombat has to move to reach the leaf. Here’s a likely candidate path:

If you count the arrows, you’ll find the wombat has to move 9 squares. To know how to calculate this distance automatically, here’s the key insight. How long is this alternative route for the wombat to take to the leaf?

If you count the arrows, you’ll find it’s the same distance: 9 squares! If you look at the two routes, you’ll see that they actually feature the same number of vertical moves and horizontal moves as each other. It’s just that the latter route rearranges them to do clump all the vertical moves together and all the horizontal moves together. So having seen that the latter route is the same distance, we just need to calculate the distance for that. And this becomes easy: it’s the number of vertical moves necessary (which is the vertical distance between them) plus the number of horizontal moves necessary (which is the horizontal distance between them). So the distance in our case is 6 + 3 = 9, and in general is:

\text{manhattanDistance}(xA, yA, xB, yB) = \text{abs}(xA - xB) + \text{abs}(yA - yB)

The abs function stands for absolute, which makes the given number positive (i.e. -3 becomes 3, 4 stays as 4, 0 stays as 0). This distance that we’ve described is called the Manhattan distance, so-called because Manhattan is laid out in US-style city blocks. Since you can’t “cut across” city blocks in Manhattan, the distance you have to walk between two destinations is not the straight-line distance, it’s the Manhattan distance.

First We Take Manhattan

From the second route diagram above, it is quite easy to formulate an algorithm to help the wombat to the leaf.

if (getX() < leaf.getX())
    setLocation(getX() + 1, getY());
else if (getX() > leaf.getX())
    setLocation(getX() - 1, getY());
/* if we get here, we must have the same X coordinate as the leaf */
else if (getY() < leaf.getY())
    setLocation(getX(), getY() + 1);
else if (getY() > leaf.getY())
    setLocation(getX(), getY() -1);
else
    Greenfoot.stop();

We can actually simplify this code by co-opting a common mathematical method, signum. This is short for sign (of) number: if the number is negative it returns -1, if the number is zero it returns zero, and if the number is positive it returns 1. If you apply this to a distance, you find out which way to head!

int xDir = (int)Math.signum(leaf.getX() - getX());
int yDir = (int)Math.signum(leaf.getY() - getY());
if (xDir != 0)
    setLocation(getX() + xDir, getY());
else if (yDir != 0)
    setLocation(getX(), getY() + yDir);
else
    Greenfoot.stop();

And Then We Take Berlin

The above routing code is fine, and we’ve seen that this simple route is as short as any other. But it still looks a bit funny when we run it; the wombat walks in two straight lines, but doesn’t look much like it’s heading towards the leaf:

One way to fix this is to re-introduce Pythagoras to help us. At each step, the wombat may have two choices to make (while still using the shortest route): move down or move right. We make the choice between the two by choosing the direction that will reduce the straight-line diagonal distance (as measured by Pythagoras) the most. This makes the wombat take what looks more like the shortest route:

Here’s the code:

        int xDir = (int)Math.signum(leaf.getX() - getX());
        int yDir = (int)Math.signum(leaf.getY() - getY());
        if (xDir == 0 && yDir == 0) //We're there
            Greenfoot.stop();
        else if (xDir == 0) // Move in yDir
            setLocation(getX(), getY() + yDir);
        else if (yDir == 0) // Move in xDir
            setLocation(getX() + xDir, getY());
        else // A choice
        {
            double xDirDist = Math.hypot(leaf.getX() - (getX() + xDir), leaf.getY() - getY());
            double yDirDist = Math.hypot(leaf.getX() - getX(), leaf.getY() - (getY() + yDir));
            if (xDirDist < yDirDist)
                setLocation(getX() + xDir, getY());
            else
                setLocation(getX(), getY() + yDir);
        }

That concludes our first look at Manhattan distance, which will come in handy again in the future when we deal with grid-based scenarios.

Advertisements

Comments on: "First We Take Manhattan" (2)

  1. David Murphy said:

    6^2 + 3^2 = 45 not 42, unless I am misunderstanding something, but I ran the numbers in a spreadsheet to be sure.

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