NetLogo User Community Models

(back to the NetLogo User Community Models)

Download If clicking does not initiate a download, try right clicking or control clicking and choosing "Save" or "Download".(The run link is disabled for this model because it was made in a version prior to NetLogo 6.0, which NetLogo Web requires.)

WHAT IS IT?

This model builds single-path or multi-path mazes with no cross-overs.

With one walker, the maze is traversable, and any point on the maze can be reached from any other point.

If more than one "walker" is active, then multiple mazes are drawn nestled in each other. Each individual maze is traversable, but the different mazes are not connected.

HOW IT WORKS

A recursive subroutine is used to implement the maze-drawing. Each walker starts at a random location, then wanders the field. With every step, the location is pushed onto the stack. When a dead-end is reached, the walker pops back to the previous turn location, and continues, until no open space remains.

To implement multiple walkers, allow the "curvyness" to be controlled, and reduce stack length for straight runs, the maze procedure has become somewhat complicated, and its basic operation hard to discern. Here is a simplified version to illustrate the basic operation:

to go
ask turtles
[ empty-stack
push
build-maze
die
]
end

to build-maze
ifelse any-open-routes
[ push-location-to-stack
draw-while-moving-to-open-route
build-maze
]
[ if stack-not-empty
[ pop-from-stack
build-maze
]
]
end

HOW TO USE IT

Click "Setup and Build-Maze" to get things started.
Click Setup to see how the maze looks before it starts drawing
Then click Build-Maze to start the maze drawing

OR, click ...forever varying. This will setup and build the maze defined by the sliders, then randomize things and build a different maze, forever. Fun to watch.

Walkers controls the number of walkers drawing the maze.

Path-width controls the width of the path, in patches.
It's an integer diameter, with a center patch, so it is always odd.

Gap controls the gap between paths.

Curviness controls the tendency to go in a straight line.
If curvyness is 0, the walker will not turn unless a wall is hit. If curvyness is 1, the walker will randomly choose a direction from the 3 directions available.

Random-Orientation controls the initial direction of the walkers. If off, walkers all start out going up.

One-color controls walker coloring. If off, the walkers are assigned random colors from an attractive palette. If on, the selected pen-color is used for all walkers.

Pen-color, Gap-Color are self-explanitory.

THINGS TO NOTICE

How does the number of walkers affect how long it takes to fill the maze?
Why do you think that is?
How does the number of walkers affect the way the maze looks?

Usually we think of the path drawn by the walkers as the maze path, and the background as the "walls" of the maze. But what happens if the width is narrow, and the gap is wide? What qualities does the maze have if we think of the drawn path as "walls" and the gaps as "corridors"? Is this maze traversable?

THINGS TO TRY

Try different numbers of walkers
Try different path-width and gap sizes
Change screen-edge-x and -y to 50 (or some other largish size), patch size to 2, walkers 10 or more. While the maze is building, slide the curviness slider back and forth, to create curvy areas and straight areas inside the maze.
Try a maze with a gap of 0.
Try a large maze with gap 0, width 1, and many walkers. The maze looks like the irregular edges of a country or city map.

EXTENDING THE MODEL

Create a subroutine to have a turtle (mouse?) traverse the maze(s). For a single-patch path-width and gap, this is fairly easy, but might be harder for other gaps and widths.

Would a non-recursive routine work better, faster, etc? Would a non-recursive method be easier, or harder to implement?

NETLOGO FEATURES

This model takes advantage of netlogo's support for recursion.
One challenge of implementing multiple walkers was the tendency of the walkers to step on each other. Since the model uses recursion, using "without-interruption" was not an option, as that would make the first walker complete the maze by itself, on it's first "turn". Early versions of the model used several tactics, including ethernet-style collision avoidance (if other turtles near, wait a while). The problem was that marking the space as taken was among the last things the walker did, so that another walker could also mistake the space for available. The solution turned out to be simple: The moment a walker determines that a space is open, it marks the space, then does the additional steps required to draw the path to the space. This seems to have eliminated the problem of walker collisions.

CREDITS AND REFERENCES

~~~~~~~~~~~~~~~~~~~~~~
This model was inspired by the memory of a game written in BASIC for the commodore VIC-20 and published in Compute's Gazette magazine in the early 80's. I remember the game was a simple maze game, but it had a nifty maze-generator routine that my father helped me reverse-engineer and use to create other more-interesting games of my own. I remembered the gist of the algorithm, and wondered how it would work out in NetLogo. Here it is, and more.

COPYRIGHT & LICENSE
This work is Copyright © 2004 James P. Steiner.
This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/1.0/ or send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.