Manhattan distance measures the walk between two points when you can only move along a grid: the gap across plus the gap up.
Strategy
Direct computation
One formula over the coordinates, worked out in a single step.
- Measure: take the gap across and the gap up and down.
- Drop the sign: absolute value, so direction cannot subtract from the total.
- Add: the two gaps together are the distance.
Move the blue point with the arrows. The path stays on the grid lines, and the distance is always the blocks across plus the blocks up, whatever route you take.
Purpose
Measure how far apart two points are when travel is locked to the grid.
Input
Two Point values, each holding a whole-number X and Y.
Output
The distance in blocks, as an int.
Constraints
- Movement runs along the grid lines. A diagonal shortcut makes this the wrong measure.
- Coordinates are whole numbers here. Floats work the same way with
math.Abs. - The arithmetic stays in integers, so comparing two distances is exact.
How Manhattan distance works
It is named after the street layout. To get from one corner of Manhattan to another you walk so many blocks across and so many blocks up, and no shortcut through the buildings is available. The distance is just those two counts added together.
It turns up wherever movement is locked to a grid: tile-based games, chip layout, pixel work, and as a cheap stand-in for straight-line distance when you only need to compare which of two things is closer.
The bars mean absolute value, which throws away the minus sign. Going four blocks left is the same walk as four blocks right, so the direction cannot be allowed to subtract from the total.
What the formula needs
| Name | Type | What it is for |
|---|---|---|
| Point | struct{ X, Y int } | One position on the grid. |
| a, b | Point | The two positions you are measuring between. |
| abs | func(int) int | Drops the minus sign, so direction stops mattering. |
| dx | int | How far apart the two points are left to right. |
| dy | int | How far apart they are up and down. |
Walk through it
1 Start with two points
A small struct holding an across value and an up value is enough.
type Point struct{ X, Y int }
a := Point{X: 1, Y: 2}
b := Point{X: 5, Y: 5}2 Write a helper that drops the minus sign
Go has no built-in absolute value for integers. math.Abs works on float64 only, so for whole numbers you write three lines.
func abs(n int) int {
if n < 0 {
return -n
}
return n
}3 Measure the gap across
Subtract one X from the other, then strip the sign.
dx := abs(a.X - b.X) // abs(1-5) = 44 Measure the gap up and down
The same again with the Y values.
dy := abs(a.Y - b.Y) // abs(2-5) = 35 Add the two gaps together
Four blocks across plus three blocks up is a seven block walk, whichever order you take the turns in.
return dx + dy // 76 Find the closest of several points
With the measurement in hand, picking the nearest of several points is one pass keeping the smallest so far.
best, bestD := others[0], Manhattan(from, others[0])
for _, p := range others[1:] {
if d := Manhattan(from, p); d < bestD {
best, bestD = p, d
}
}The whole program
Put it together and you can measure between two points, and pick the nearest of a set.
package main
import "fmt"
type Point struct{ X, Y int }
func abs(n int) int {
if n < 0 {
return -n
}
return n
}
// Manhattan is the grid walk between a and b: across, then up.
func Manhattan(a, b Point) int {
return abs(a.X-b.X) + abs(a.Y-b.Y)
}
// Nearest returns the closest point to from, and how far it is.
func Nearest(from Point, others []Point) (Point, int) {
best, bestD := others[0], Manhattan(from, others[0])
for _, p := range others[1:] {
if d := Manhattan(from, p); d < bestD {
best, bestD = p, d
}
}
return best, bestD
}
func main() {
a := Point{X: 1, Y: 2}
b := Point{X: 5, Y: 5}
fmt.Println(Manhattan(a, b))
fmt.Println(Manhattan(b, a))
fmt.Println(Manhattan(a, a))
depots := []Point{{6, 1}, {2, 4}, {5, 5}}
p, d := Nearest(a, depots)
fmt.Printf("nearest %v at %d blocks\n", p, d)
}$ go run main.go
7
7
0
nearest {2 4} at 3 blocks