Chevening House Maze with Coloured Islands NetLogo Model

Produced for the book "Exercises for Artificial Intelligence - Volume 1: Agent-Oriented Systems";

Author: W. J. Teahan; Publisher: Ventus Publishing Aps, Denmark.

powered by NetLogo

view/download model file: Chevening-House-Maze-with-Coloured-Islands.nlogo

WHAT IS IT?

This model is a modification of the Chevening House Maze model where the user can incrementally colour the islands in the maze.

The model draws a schematic of the Chevening House maze in the United Kingdom. The entrance is at the middle bottom of the maze, and the goal is to get to the centre. The maze has been designed to specifically thwart the hand-on-the-wall behaviour for reaching the centre. In this case, the centre occurs on an "island" which is not directly connected to the outside walls.


THE INTERFACE

The setup-chevening-maze button will redraw the maze.

The colour-an-island button will colour one of the islands in the maze that has not already been coloured.

The sliders are defined as follows:
- row-patches-width : the width between horizontal walls in the maze;
- col-patches-width : the width between vertical walls in the maze.

The islands-coloured-in-the-maze monitor keeps a running total of the number of islands that have been coloured so far. This number is incremented each time the colour-an-island button is pressed.


HOW IT WORKS

The maze is drawn using 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.

The colouring algorithm uses a recursive procedure to fan out from a single initial blue patch selected at random. It does this by colouring all the patch's neighbours, then all the neighbours' neighbours, and so on, until there are no more neighbours that are still blue.


HOW TO USE IT

To have the model draw the maze, press the setup-chevening-maze button.

To colour one of the islands in the maze, press the colour-an-island maze. Keep on pressing this button until all the islands have been coloured. How many islands were there?


WHAT IS ITS PURPOSE?

Its purpose is to show that the Chevening House maze is a multiply-connected maze i.e. that the centre of the maze cannot be reached using the hand-on-the-wall behaviour since the centre is within an island.


THINGS TO TRY

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.

Try slowing down the speed during the colouring of each island. Some of the patches, often the ones at right-angled corners, remain uncoloured for a while but get coloured latter on. Why does this happen?


EXTENDING THE MODEL

Try adding a turtle agent to move around the maze.

How efficient is the colouring algorithm? Is there a more efficient way to perform the colouring?


RELATED MODELS

See the Empty Maze and Hampton Court Maze models.


CREDITS AND REFERENCES

To refer to this model in publications, please use:

Teahan, W. J. (2010). Chevening House Maze with Coloured Islands NetLogo model.
Exercises for Artificial Intelligence. Ventus Publishing Aps.


PROCEDURES

; Chevening House Maze model
; 
; Draws a schematic map of the Chevening House Maze. Allows the user to colour islands in the maze.

; Copyright 2010 William John Teahan. All Rights Reserved.

globals
[
  the-colour                 ; This is the current colour being used to colour an island inthe maze.
  number-of-coloured-islands ; This is the number of islands that have been coloured so far. 
]
        
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-chevening-house-maze
  ca ;; clear everything
  
  set the-colour 115 ; this is the colour for the first island chosen to be coloured
  set number-of-coloured-islands 0

  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-report islands-coloured-in-the-maze
  report number-of-coloured-islands
end

to colour-an-island
; Colours one of the "islands" in the Chevening House Maze.

  if (count patches with [pcolor = blue] = 0)
    [ user-message "The maze has now been coloured."
      stop
    ]
  ask one-of patches with [pcolor = blue]
  [
    colour-this-island self the-colour
    set the-colour the-colour + 20 ; change the colour
    if (the-colour = blue)
      [ set the-colour the-colour + 10 ] ; change the colour again so that it is different to blue
  ]
  
  set number-of-coloured-islands number-of-coloured-islands + 1
end

to colour-this-island [this-patch colour]
; Colours one of the "islands" in the Chevening House Maze using the colour.
; It fans out from the patch this-patch in a recursive manner.

  ask this-patch
  [
    ask neighbors with [pcolor = blue]
    [
      if (pcolor = blue)
        [
          set pcolor colour
          colour-this-island self colour
        ]
    ]
  ]
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).  Chevening House Maze with Coloured Islands NetLogo model.
;   Artificial Intelligence. Ventus Publishing Aps.
;