Mazes 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: Mazes.nlogo

WHAT IS IT?

This model shows how to get a simple reactive turtle agent to move around a maze. The model comes with three mazes - the empty maze (just outside walls), and two mazes that are schematic representations of real life mazes in the United Kingdom - the Hampton Court Palace maze, and the Chevening House Maze.


THE INTERFACE

The buttons in the Interface are defined as follows:
- setup: This will clear the environment and redraw the maze selected by the maze-being-searched chooser.

- go-once: This will get a single turtle agent to walk around the maze according to the behaviour selected in the turtle-behaviour chooser. This button will execute the walk turtle procedure once, not continuously.

- go-forever: This will get a single turtle agent to continuously walk around the maze according to the behaviour selected in the turtle-behaviour chooser.

The choosers, sliders and switch are defined as follows:

- maze-being-searched: This specifies the maze that is being searched. This is either the empty maze, the Hampton Court Palace maze, or the Chevening House maze.

- turtle-behaviour: This specifies the type of reactive behaviour the walker turtle agent exhibits. The types of behaviour is as follows:
"hand-on-the-wall": This is the classic maze wall following behaviour of keeping a specific hand, either left or right, on a wall at all times. The model randomly decides itself whether the left hand or right hand is chosen.
"Random Forward 0": In this behaviour, the walker turtle agent moves forward unless there is a wall ahead, then tries to turn left unless there is a wall to the left, then tries to turn right unless there is a wall to the right, then randomly turns left or right as a last resort.
"Random Forward 1": In this behaviour, the walker turtle agent moves around mostly in straight lines in random directions for a random distance, but if it encounters a wall, it will bang against it for a short while (much like a woodpecker banging against a tree or a fly against a window) before backing off a random distance and continuing on with its random wanderings.
"Random Forward 2": In this behaviour, the walker turtle agent wanders around in random directions using small steps.

- set-pen-down?: If set to On, this will draw the path of the walker turtle agent.

- left-cols, right-cols, above-rows, below-rows, entrance-cols: This sets the length and widths of the empty maze's side walls and entrance.

- col-patches-width, row-patches-width: This sets the width in patches for the columns and rows of the Hampton Court maze and Chevening House maze (i.e. the width between horizontal and vertical walls in these mazes).


HOW IT WORKS

It uses one ask patches command to set the patches blue that define the walls, and to set the remaining patches white. The code uses two procedures that are similar, setup-row and setup-col, to draw the walls in a horizontal row or vertical column respectively. These procedures take the row or column number as the first parameter, the colour that the walls are to be drawn with, and a list containing two-numbered range lists that define the segments where the walls are to be drawn in the row or column.

One turtle agent is created as the walker agent. It uses a simple proximity detector method (see the wall? reporter) to sense if there is a wall ahead at a specific angle and distance.


HOW TO USE IT

First select the maze using the maze-being-searched chooser, then select the behaviour of the turtle using the turtle-behaviour chooser. Then press the setup button, followed by either the go-once or go-forever buttons.

To get the turtle to draw its path, set the set-pen-down? switch to On.


WHAT IS ITS PURPOSE?

Its purpose is to show how a simple reactive agent can be effective (or not) at exploring a maze. The turtle has no cognitive abilities to recognize the situation it is in; e.g. that it is in a maze, that there is a goal it should try to reach, that it gets stuck at times, that there are alternative paths it can take at various points, or that it has travelled over the same point multiple times. The turtle agent simply reacts to the immediate situation it finds itself in using a simple proximity detector to sense a wall nearby.

The model also uses two virtual mazes that have a corresponding maze in real-life to demonstrate how virtual environments can mirror real-life environments but where the reflection can often be distorted in the process.


THINGS TO TRY

Try out the different behaviours on the different mazes by changing the values of the maze-being-searched and turtle-behaviour choosers. Try doing this as the turtle is moving around.

See what happens when you change the value of the sliders.

Try changing the Settings of the environment such as the Patch Size and the maximum and minimum x and y co-ordinates.


EXTENDING THE MODEL

Try adding your own behaviours to get the turtle agent to move around the maze.


NETLOGO FEATURES

The model uses the path-right-and-ahead reporter to allow the turtle agent to sense if there is a wall nearby.


RELATED MODELS

See the Empty Maze, Hampton Court Maze and Chevening House Maze models.


CREDITS AND REFERENCES

To refer to this model in publications, please use:

Teahan, W. J. (2010). Mazes NetLogo model.
Artificial Intelligence. Ventus Publishing Aps.


PROCEDURES

; Mazes model.
; 
; Gets turtles with simple reactive behaviours to search various mazes.
;
; Copyright 2010 William John Teahan. All Rights Reserved.

turtles-own [direction]  ;;  1 follows right-hand wall,
                         ;; -1 follows left-hand wall

breed [mazes maze]
mazes-own
[ start-x start-y start-width; co-ordinates where the search starts
  entrance-x entrance-y entrance-width
  goal-type goal-x goal-y goal-width] ; specifies where the exit or goal is
          
to setup
  ca ;; clear everything

      if (maze-being-searched = "Empty Maze")
          [setup-empty-maze
           create-mazes 1 [  
             set start-x 0
             set start-y (- below-rows - 5)
             set start-width 6
             set entrance-x (- entrance-cols) + 1
             set entrance-y (- below-rows)
             set entrance-width 2 * entrance-cols - 2
             set goal-type "Exit"
             set goal-x entrance-x
             set goal-y above-rows
             set goal-width entrance-width]]
      if (maze-being-searched = "Hampton Court Maze")
          [setup-hampton-court-maze
           create-mazes 1 [
             set start-x (col-patches-width / 2)
             set start-y (- row-patches-width * 7 - 1)
             set start-width row-patches-width + 2
             set entrance-x 0
             set entrance-y (- row-patches-width * 6)
             set entrance-width col-patches-width
             set goal-type "Centre"
             set goal-x 0
             set goal-y (- 2 * row-patches-width)
             set goal-width col-patches-width]]
      if (maze-being-searched = "Chevening House Maze")
          [setup-chevening-house-maze
           create-mazes 1 [
             set start-x (col-patches-width / 2)
             set start-y (- row-patches-width * 12)
             set start-width row-patches-width + 2
             set entrance-x 1
             set entrance-y (- row-patches-width * 11)
             set entrance-width col-patches-width - 2
             set goal-type "Centre"
             set goal-x 1
             set goal-y (- row-patches-width)
             set goal-width entrance-width]]

  create-turtles 1 [
      set size 5              ;; bigger turtles are easier to see
      set pen-size 2          ;; thicker lines are easier to see
      set color magenta
      
      ; move the turtle slowly to the entrance
      setxy [start-x] of maze 0 [start-y] of maze 0

      if set-pen-down?
          [ pen-down ]

      set heading 0 ; head north
      repeat ([start-width] of maze 0) [forward 1 wait 0.2]

      set direction 1
      if not (maze-being-searched = "Chevening House Maze")
        [ ; randomly turn left or right
          ifelse random 2 = 0
          [ set heading 90
            set direction 1 ]   ;; follow right hand wall
          [ set heading 270
            set direction -1]   ;; follow left hand wall
          forward 2
        ]
  ]
  
  ; close "door" once they are in
  ask patches
    [ let xpos ([entrance-x] of maze 0)
      if pxcor >= xpos and pxcor <= xpos + ([entrance-width] of maze 0) and
        pycor = ([entrance-y] of maze 0)
      [ set pcolor sky ]]
end

to setup-empty-maze
  ca ;; clear everything
  
  ask patches
  [
    set pcolor white ;; make background full of white patches
          
    if (pxcor >= (- left-cols - entrance-cols) and pxcor <= (- entrance-cols) and
        pycor = (- below-rows))
      [set pcolor blue] ;; draws bottom left horizontal wall in blue

    if (pxcor >= (entrance-cols) and pxcor <= (right-cols + entrance-cols) and
        pycor = (- below-rows))
      [set pcolor blue] ;; draws bottom right horizontal wall in blue

    if (pxcor >= (- left-cols - entrance-cols) and pxcor <= (- entrance-cols) and
        pycor = (above-rows))
      [set pcolor blue] ;; draws top left horizontal wall in blue

    if (pxcor >= (entrance-cols) and pxcor <= (right-cols + entrance-cols) and
        pycor = (above-rows))         
      [set pcolor blue] ;; draws top left horizontal wall in blue

    if (pxcor = (- left-cols - entrance-cols) and
        pycor >= (- below-rows) and pycor <= (above-rows))
      [set pcolor blue] ;; draws left vertical wall in blue
      
    if (pxcor = (right-cols + entrance-cols) and
        pycor >= (- below-rows) and pycor <= (above-rows))
      [set pcolor blue] ;; draws right vertical wall in blue
  ]
end
to setup-row [row colour segments]
  foreach segments
  [
      if pycor = row * row-patches-width and
        (pxcor >= col-patches-width * (item 0 ?)) and (pxcor <= col-patches-width * (item 1 ?))
          [set pcolor colour]
  ]
end

to setup-col [col colour segments]
  foreach segments
  [
      if pxcor = col * col-patches-width and
        (pycor >= row-patches-width * (item 0 ?)) and (pycor <= row-patches-width * (item 1 ?))
          [set pcolor colour]
  ]
end

to setup-hampton-court-maze
  ca ;; clear everything
  
  ask patches
  [
      if (pxcor >= min-pxcor and pxcor <= max-pxcor and
        pycor >= min-pycor and pycor <= max-pycor)
          [set pcolor white] ;; make background full of white patches
      
      setup-row  5 blue [[-9 10]]
      setup-row  4 blue [[-8 -5] [-3 -1] [0 3] [5 9]]
      setup-row  3 blue [[-7 -4] [-2 2] [4 8]]
      setup-row  2 blue [[-6 -1] [1 4] [5 7]]
      setup-row  1 blue [[-3 3] [8 9]]
      setup-row  0 blue [[-8 -7] [9 10]]
      setup-row -1 blue [[-9 -8]]
      setup-row -2 blue [[-8 -7] [-3 0] [1 3]]
      setup-row -3 blue [[-4 -1] [2 4] [6 8]]
      setup-row -4 blue [[-7 -1] [1 9]]
      setup-row -5 blue [[-8 10]]
      setup-row -6 blue [[-9 0] [1 10]]

      setup-col 10 blue [[-6 5]]
      setup-col  9 blue [[-4 -1] [1 4]]
      setup-col  8 blue [[-3 1] [2 3]]
      setup-col  7 blue [[-2 2]]
      setup-col  6 blue [[-4 1]]
      setup-col  5 blue [[-3 2]]
      setup-col  4 blue [[-3 2] [3 5]]
      setup-col  3 blue [[-2 1] [2 4]]
      setup-col  1 blue [[-4 -2]]
      setup-col  0 blue [[-5 -2] [1 3]]
      setup-col -1 blue [[-4 -3] [4 5]]                  
      setup-col -3 blue [[-2 1] [2 4]]
      setup-col -4 blue [[-3 2] [3 5]]
      setup-col -5 blue [[-4 1]]
      setup-col -6 blue [[-3 2]]
      setup-col -7 blue [[-4 -3] [-2 0] [1 3]]
      setup-col -8 blue [[-5 -2] [0 4]]
      setup-col -9 blue [[-6 5]]
  ]
end

to setup-chevening-house-maze
  ca ;; clear everything
  
  ask patches
  [
      if (pxcor >= min-pxcor and pxcor <= max-pxcor and
        pycor >= min-pycor and pycor <= max-pycor)
          [set pcolor white] ;; make background full of white patches
      
      setup-row  12 blue [[-11 12]]
      setup-row  11 blue [[-10 11]]
      setup-row  10 blue [[-9 10]]
      setup-row   9 blue [[-8 0] [1 9]]
      setup-row   8 blue [[-7 -1] [2 8]]
      setup-row   7 blue [[-6 0] [1 7]]
      setup-row   6 blue [[-5 0] [1 6]]
      setup-row   5 blue [[-4 -1] [2 5]]
      setup-row   4 blue [[-3 0] [1 4]]
      setup-row   3 blue [[-2 3]]
      setup-row   2 blue [[-1 2]]
      setup-row   1 blue [[-9 -5] [-4 -2] [3 5] [6 8] [10 11]]
      setup-row  -0 blue [[-9 -7] [3 5] [6 10]]
      setup-row  -1 blue [[-1 0] [1 2] [7 9]]
      setup-row  -2 blue [[-2 0] [1 3]]
      setup-row  -3 blue [[-3 -1] [1 4]]
      setup-row  -4 blue [[-4 -2] [2 5]]
      setup-row  -5 blue [[-5 -3] [2 6]]
      setup-row  -6 blue [[-6 -3] [1 7]]
      setup-row  -7 blue [[-7 -2] [0 8]]
      setup-row  -8 blue [[-8 1] [3 9]]
      setup-row  -9 blue [[-9 0] [3 10]]
      setup-row -10 blue [[-10 -1] [2 11]]
      setup-row -11 blue [[-11 0] [1 12]]

      setup-col  12 blue [[-11 12]]
      setup-col  11 blue [[-10 1] [2 11]]
      setup-col  10 blue [[-9 0] [1 10]]
      setup-col   9 blue [[-8 -1] [0 9]]
      setup-col   8 blue [[-7 -2] [1 8]]
      setup-col   7 blue [[-6 -1] [2 7]]
      setup-col   6 blue [[-5 0] [1 6]]
      setup-col   5 blue [[-4 0] [1 5]]
      setup-col   4 blue [[-3 -1] [2 4]]
      setup-col   3 blue [[-2 0] [1 3]]
      setup-col   2 blue [[-10 -7] [-1 2]]
      setup-col   1 blue [[-11 -8] [-6 -1] [4 6] [7 9]]
      setup-col   0 blue [[-11 -9] [-7 -1] [4 6] [7 9]]
      setup-col  -1 blue [[-8 -3] [-1 2]]
      setup-col  -2 blue [[-7 -4] [-2 0] [1 3]]
      setup-col  -3 blue [[-3 1] [2 4]]
      setup-col  -4 blue [[-4 0] [1 5]]
      setup-col  -5 blue [[-5 6]]
      setup-col  -6 blue [[-6 0] [2 7]]
      setup-col  -7 blue [[-7 0] [1 8]]
      setup-col  -8 blue [[-8 -1] [2 9]]
      setup-col  -9 blue [[-9 0] [1 10]]
      setup-col -10 blue [[-10 11]]
      setup-col -11 blue [[-11 12]]
  ]
end

to go
  ask turtle 1 [ walk ]
  tick
end

to walk  ;; turtle procedure
;; walk around the maze

  ifelse set-pen-down? [ pen-down ] [ pen-up ]

  if count neighbors4 with [pcolor = blue] = 4
     [ user-message "Trapped!"
       stop ]
  let xpos [goal-x] of maze 0  
  if xcor >= xpos and xcor <= xpos + [goal-width] of maze 0 and
     ycor = [goal-y] of maze 0 
     [ ifelse [goal-type] of maze 0 = "Exit"
       [ user-message "Found the exit!" ]
       [ user-message "Made it to the centre of the maze!" ]
       stop ]
     
  if (turtle-behaviour = "Hand On The Wall") [behaviour-wall-following]
  if (turtle-behaviour = "Random Forward 0") [behaviour-random-forward-0]
  if (turtle-behaviour = "Random Forward 1") [behaviour-random-forward-1]
  if (turtle-behaviour = "Random Forward 2") [behaviour-random-forward-2]
end

to-report wall? [angle dist]
  ;; note that angle may be positive or negative.  if angle is
  ;; positive, the turtle looks right.  if angle is negative,
  ;; the turtle looks left.
  let patch-color [pcolor] of patch-right-and-ahead angle dist
      
  report patch-color = blue or patch-color = sky ; blue if it is a wall, sky if it is the closed entrance
end

to behaviour-wall-following
; classic 'hand-on-the-wall' behaviour
  if not wall? (90 * direction) 1 and wall? (135 * direction) (sqrt 2)
     [ rt 90 * direction ]
  
  ;; wall straight ahead: turn left if necessary (sometimes more than once)
  while [wall? 0 1] [ lt 90 * direction]

  ;; move forward
  fd 1
end

to behaviour-random-forward-0
; moves forward unless there is a wall ahead, then tries to turn left unless there is a wall to the left,
; then tries to turn right unless there is a wall to the right, then randomly turns left or right as a last
; resort. 
  if wall? 0 1
    [ ifelse wall? 90 1
        [ lt 90 ]
        [ ifelse wall? 270 1
          [ rt 90 ]
          [ ifelse random 2 = 0 [lt 90] [rt 90] ]]]

  ;; move forward
  fd 1
end

to behaviour-random-forward-1
; moves around mostly in straight lines
  ifelse wall? 0 1
    [ bk 1 ]
 ;else
    [ let r random 20
      ifelse r = 0
        [ if not wall? 90 1 [rt 90 fd 1] ]
     ;else
        [ ifelse r = 1
            [ if not wall? 270 1 [lt 90 fd 1] ]
            [ let f random 5
              while [not wall? 0 1 and f > 0]
                [ fd 1
                  set f f - 1]]]]
end

to behaviour-random-forward-2
; moves around in random small steps
  let r random 3
  ifelse r = 0
    [ if not wall? 90 1 [rt 90 fd 1] ]
    [ ifelse r = 1
        [ if not wall? 270 1 [lt 90 fd 1] ]
        [ if not wall? 0 1 [fd 1] ]]
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).  Mazes NetLogo model.
;   Artificial Intelligence. Ventus Publishing Aps.
;