Manhattan Distance

An alternative distance formula

After making the last post regarding the Pythagorean Theorem and it’s usage as a distance calculation algorithm for use in games, I thought I would take a quick aside from my intended next topic of trigonometry to discuss an alternative method for calculating the distance between two points, which is not as accurate (depending on your needs), but also requires less computational work. For some applications it might actually give you a better result. It’s called the Manhattan Distance Formula.

The Manhattan distance formula, also known as the Taxi distance formula for reasons that are about to become obvious when I explain it, is based on the idea that in a city with a rectangular grid of blocks and streets, a taxi cab travelling between points A and B, travelling along the grid, will drive the same distance regardless of what streets are taken to the destination, due to having to keep to the intersections. Of course, this doesn’t hold true if your taxi driver is sneaky and drives in the wrong direction, but you get the idea.

Why the Manhattan distance formula? Was Manhattan the first place to think of creating streets in a grid arrangement? Maybe! I’m not much of a historian.

Manhattan Distance

Manhattan or “Taxi” Distance

As seen in this crude diagram (please excuse it, I didn’t have time to build it to scale or to paint it), regardless of the three paths taken that follow the edges of the grid, the total distance traveled is 10:

5 + 5
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
3 + 2 + 1 + 1 + 1 + 2

Using the regular distance formula, the actual distance between the two points is actually 7.07, which mathematically proves the axiom that the shortest distance between two points is a straight line.

The actual formula for this is:

\left|\Delta x\right| + \left|\Delta y\right|

This is the sum of the absolute values of the changes in the X and Y coordinates. You might remember it from last week’s post about the Pythagorean Theorem; in that case, this is how we determined what the two sides of the triangle were.

We use the absolute value here because distance is always 0 or positive (something enforced in the Pythagorean theorem by the fact that the square of a negative number is always positive). This ensures that the distance as calculated from A to B is the same as that from B to A.

Why would you use this as a distance calculation?

I can think of at least this many off the top of my head:

  • It’s faster to calculate than the true distance because you don’t have to take a square root of anything.
  • If your game doesn’t allow for movement diagonally (e.g. it’s tile based and all movement is restricted to tile by tile), it might be a more accurate distance representation.

Depending on how many items there are in that list, I’m either impressed with myself for thinking of so many, or I was lazy and didn’t come back and flesh the list out more before I posted this.

In any case, this is also a handy thing to have in your back pocket. Use it for calculating rough distance estimates or your ACTUAL distances as circumstances warrant.

And now, back to our regularly scheduled path. Assuming something shiny doesn’t cross my path and distract me again.