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