Manhattan Distance NetLogo Model
Produced for the book series "Artificial Intelligence";
Author: W. J. Teahan; Publisher: Ventus Publishing Aps, Denmark.
powered by NetLogo
view/download model file: Manhattan-Distance.nlogo
WHAT IS IT?
This model shows how Manhattan distance is calculated. This is compared with Euclidean distance in the model.
WHAT IS ITS PURPOSE?
The purpose of this model is to highlight via basic animation techniques the fundamental differences in the two different distance calculations.
HOW IT WORKS
Two point agents are used to designate the start and end points. A walker agent is used to go between the two points. This is done either in a direct line to illustrate what the Euclidean distance metric is based upon. Or for the Manhattan distance metric, it is done through any of the paths that avoid crossing into the Manhattan "skyscrapers" represented by the blue boxes in the environment. In other words, the paths can only go down either an avenue (roads that run north/south) or street (roads that run west/east).
HOW TO USE IT
First press Setup to reset the agents and environment. Then press the plot-euclidean-distance button if you wish to show the path the Euclidean distance metric (shown in the Euclidean Distance monitor) is based upon. Or press the plot-manhattan-distance button if you wish to plot one of the paths the Manhattan distance metric (shown in the Manhattan Distance monitor) is based upon. Pressing this button again will plot a different path, but with the same value shown in the monitor.
THE INTERFACE
The model's Interface buttons are defined as follows:
- Setup: This resets the model.
- plot-euclidean-distance: This draws the straight line path for which the Euclidean distance calculation is based upon.
- plot-manhattan-distance: This draws one of the paths for which the Manhattan distance calculation is based upon.
The model's Interface monitors are defined as follows:
- Euclidean Distance: This is the Euclidean distance between the two points.
- Manhattan Distance: This is the Manhattan distance between the two points.
THINGS TO NOTICE
Notice that Euclidean distance is always less than Manhattan distance. Why?
Both Euclidean distance and Manhattan distance are admissible heuristics if used for an informed search algorithm such as greedy search or A* search. Why?
THINGS TO TRY
Keep plotting the different Manhattan paths by repeatedly pressing the plot-manhattan-distance button. A visually appealing pattern will emerge. Some of the paths will take longer to appear, however. Why?
EXTENDING THE MODEL
Consider how to visualise the distance calculations in 3 or more dimensions.
RELATED MODELS
See the Searching Mazes, Missionaries and Cannibals and Searching for Kevin Bacon models to see where these distance metrics become useful as heuristic functions in various informed search algorithms.
CREDITS AND REFERENCES
This model was created by William John Teahan.
To refer to this model in publications, please use:
Manhattan Distance NetLogo model.
Teahan, W. J. (2010). Artificial Intelligence. Ventus Publishing Aps.
PROCEDURES
; Manhattan Distance model.
;
; Shows the difference between Euclidean and Manhattan distance.
;
; Copyright 2010 William John Teahan. All Rights Reserved.
;
breed [ points point ]
breed [ walkers walker ]
globals
[ start-x start-y
goal-x goal-y ]
to setup
clear-all
; creates colour, size and random location of single walker
create-walkers 1
[
set color red
set shape "person"
setxy (- max-pxcor + 1) (- max-pycor + 1)
set size 1
]
draw-obstacles
set start-x (- max-pxcor + 1)
set start-y (- max-pycor + 1)
set goal-x (max-pxcor - 1)
set goal-y (max-pycor - 1)
create-points 1 [ draw-point start-x start-y ]
create-points 1 [ draw-point goal-x goal-y ]
end
to draw-obstacles
ask patches with [pxcor mod 2 = 0 and
pycor mod 2 = 0]
[ set pcolor blue ]
ask patches with [count neighbors != 8]
[ set pcolor blue ]
end
to draw-point [x y]
set color white
set shape "circle"
setxy x y
set size 1
end
to-report euclidean-distance [x y x1 y1]
;; reports the euclidean distance between points (x,y) and (x1,y1)
report sqrt ((x1 - x) ^ 2 + (y1 - y) ^ 2)
end
to-report report-euclidean-distance
report euclidean-distance start-x start-y goal-x goal-y
end
to plot-euclidean-distance
type "Euclidean Distance: "
ask walker 0
[ set color red
pen-down
setxy start-x start-y
setxy goal-x goal-y ]
type "sqrt ("
type goal-x - start-x
type " ^ 2 + "
type goal-y - start-y
type " ^ 2) = "
print report-euclidean-distance
end
to-report manhattan-distance [x y x1 y1]
report abs (x1 - x) + abs (y1 - y)
end
to-report report-manhattan-distance
report manhattan-distance start-x start-y goal-x goal-y
end
to plot-manhattan-distance
type "Manhattan Distance: "
ask walker 0
[ set color one-of [ white yellow sky lime magenta orange turquoise pink ]
pen-up
setxy start-x start-y
pen-down
let x start-x
let y start-y
let dir 0 ; 0 if moving in y direction, 1 if in x direction
let dist 0
let total-dist 0
let first-time 1
let p-dir -1 ; previous direction
while [x != goal-x or y != goal-y]
[
ifelse (x = goal-x)
[ set y y + 2
set dir 0 ]
[ ifelse (y = goal-y)
[ set x x + 2
set dir 1 ]
[ ifelse (random 2 = 0)
[ set x x + 2
set dir 1 ]
[ set y y + 2
set dir 0 ]
]
]
set total-dist total-dist + 2
setxy x y
ifelse (p-dir = -1)
[ set p-dir dir
set dist 2 ]
[ ifelse (p-dir = dir) ; changed direction?
[ set dist dist + 2 ]
[ ; changed direction
ifelse (first-time = 1)
[ set first-time 0 ]
[ type " + " ]
type dist
set dist 2
set p-dir dir
]
]
]
if (first-time = 0)
[ type " + " ]
type dist type " = "
print total-dist
]
end
;
; Copyright 2010 by William John Teahan. All rights reserved.
;
; Permission to use, modify or redistribute this model is hereby granted,
; provided that both of the following requirements are followed:
; a) this copyright notice is included.
; b) this model will not be redistributed for profit without permission
; from William John Teahan.
; Contact William John Teahan for appropriate licenses for redistribution for
; profit.
;
; To refer to this model in publications, please use:
;
; Teahan, W. J. (2010). Manhattan Distance NetLogo model.
; Artificial Intelligence. Ventus Publishing Aps.
;