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.
;