Maze-Maker

1 collaborator

James Steiner (Author)

A NOTE ON THE PASSAGE OF TIME

THIS MODEL WAS ORIGINALLY WRITTEN FOR NETLOGO V 2 IN 2004 AND UPDATED FOR VERSION 6.4 IN 2024

I CAN NOT BELIEVE I HAVE BEEN PLAYING IN NETLOGO FOR 20 FREAKING YEARS.

--James, aka GregorTroll@gmail.com, aka TurtleZero

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.

Comments and Questions

Please start the discussion about this model! (You'll first need to log in.)

Click to Run Model

;;
;;  THE AMAZING MAZE MAKER
;;
;; Maze dimentions: explained
;; path-width  = 5 = # (path-width is [1,3,5,...] )
;; gap         = 3 = . (gap is [0,1,2...] )
;; screen-edge = 16
;;  -111111100000000000000000001111111
;;   654321098765432101234567890123456
;;     #####...#####...#####...#####
;;    #####...#####...#####...#####..._
;; A  []      ( edge +
;; B  [---]
;; C  [------]
;; D    ;;
;; A = Radius (patches from center to edge, center is 0)

globals [ depth         ;; measures the number of recursive calls
  max-depth     ;; holds the peak depth
  halt          ;; if set to 1, maze-building stops
  spacing       ;; the patch distance bewteen centers of maze corridors
  z-spacing     ;; 0 - spacing
  edge-vs-spacing-x
  edge-vs-spacing-y
  maze-edge-x   ;; like screen-edge for the maze
  maze-edge-y   ;;
  blocks-x       ;; the number of maze-blocks across
  blocks-y       ;; the number of maze-blocks down
  first-x       ;; marks the lower left corner.
  first-y      ;; ""
  room-count   ;; to total maze-blocks in the grid
  radius        ;; number of patches from the center patch.
  mark-color    ;; complements the gap-color. marks unused maze blocks
  tiles         ;; patches that are stepping points on the grid
]
breed [ pathmakers pathmaker ]
pathmakers-own [ stack ]

to push ; pathmaker pushes current coords onto stack, before turning
  set stack fput ( list xcor ycor ) stack
end 

to pop ; pathmaker pops previous turn point from stack
  let xy 0

  set xy item 0 stack
  set stack but-first stack
  setxy (item 0 xy) (item 1 xy)
end 

to setup
  ;; (for this model to work with NetLogo's new plotting features,
  ;; __clear-all-and-reset-ticks should be replaced with clear-all at
  ;; the beginning of your setup procedure and reset-ticks at the end
  ;; of the procedure.)
  clear-all
  reset-ticks
  ;; path-width is width of drawn maze path, in patches
  ;; radius should always work out to integer, but just in case...
  set radius int( ( path-width - 1 ) / 2 )
  set mark-color white

  ; spacing is distance 'tween centers of paths
  set spacing gap + path-width
  ; zero minus spacing

  set tiles patches with
  [    pxcor mod spacing = 0
    and pycor mod spacing = 0
    and abs pxcor + radius + 1 < max-pxcor
    and abs pycor + radius + 1 < max-pycor
  ]

  ; the total number of blocks in the maze
  set room-count count tiles

  mark-tiles

  set halt 0
  create-walkers
  ask pathmakers [ push ]
end 

to create-walkers
  if walkers >= 1 + room-count / 10
  [ set walkers 1 + room-count / 10 ]
  create-pathmakers walkers
  [ set shape "default"
    set size 50 / patch-size
    pick-spot
    while [ any? other pathmakers-here ]
    [ pick-spot ]
    set heading 0
    set color pen-color
    if random-orientation? [ set heading 90 * random 4 ]
    if not one-color?
    [ while
      [
        color = pen-color or
        color = mark-color or
        any? ((other pathmakers) with
          [
            color = [ color] of myself
        ])
      ]
      [ set color red - 2 + 10 * random 12 + 2 * random-float 3.0
      ]
    ]
    ask patches in-radius radius [ set pcolor [color] of myself ]
    set stack []
    push
  ]
end 

to pick-spot
  let spot 0

  set spot tiles with [ not any? pathmakers-here ]
  ifelse any? spot
  [ set spot one-of spot
    set xcor [pxcor] of spot
    set ycor [pycor] of spot
  ]
  [ die ]
end 

to mark-tiles
  ask tiles [ set pcolor mark-color ]
end 

to build-maze ;; pathmaker procedure
  let paths 0
  let target 0
  let left-right 0
  let straight 0
  let curve? 0
  let running 0
  let my-color 0


  if halt = 1 [ stop ]
  set depth depth + 1
  if depth > max-depth [ set max-depth depth ]

  ; make list of open directions to travel
  set paths find-open-paths
  ifelse not any? paths
  [ ifelse length stack > 0
    ; if there's no where to go, pop back to the location
    ; of the previous turn, and start again from there.
    [ pop ]
    [ stop ]
  ]
  [ ; there is somewhere to go, so...
    ; first, identify the patch that is straight ahead
    set straight patch-ahead spacing
    set left-right paths with [ self != straight ]
    ; check if I should go straight, or maybe curve?
    set curve? random-float 1.0 < curvyness
    ifelse ( curve? and any? left-right )
    or not is-open straight
    [ ; I should curve, or I can't go straight.
      ; so pick a direction, avoiding picking straight.
      set target one-of left-right
      ; mark the destination, to help prevent another
      ; pathmaker from trying to go there.
      ask target [ set pcolor [ color ] of myself ]
      ; add my current location to the list of
      ; places where I made a turn. I come back
      ; here, later.
      push
      ; turn to the new location
      set heading towards target
      ; go there!
      draw-move
    ]
    [ ; I'm supposed to go straight.
      ; so first I'll leave myself a note, so I
      ; remember that I'm going straight for a while.
      set running true
      ; While I'm running...
      while [ running ]
      [ ; mark my target patch
        ask straight [ set pcolor [color] of myself ]
        ; turn to face it
        set heading towards straight
        ; go there!
        draw-move
        ; identify the next patch
        set straight patch-at ( dx * spacing) ( dy * spacing )
        ; Am I still running?
        ; if I pick a number more than the curvyness factor,
        ; and the patch ahead is clear, I'm still running!
        set running ( random-float 1.0 >= curvyness and is-open straight )
      ]
    ]
  ]
  if length stack = 0 [ stop ]
end 

to-report find-open-paths
  let paths 0
  let path-list 0

  set paths (patches
    at-points
    (map [ [?1 ?2] -> (list (?1 * spacing ) (?2 * spacing) ) ] [ 0 0 1 -1 ] [ 1 -1 0 0 ])
  ) with [ pcolor = mark-color ]
  report paths
end 

to draw-move
  let my-color 0
  let start-spot 0

  set my-color color
  set start-spot patch-here
  ifelse radius > 0
  [ repeat spacing
    [ ask patches in-radius radius [ set pcolor my-color ] ; with [ pcolor != my-color ][ set pcolor my-color ]
      jump 1 ]
    ask patches in-radius radius [ set pcolor my-color ]
  ]
  [ repeat spacing
    [ jump 1
      set pcolor color
    ]
  ]
  ask start-spot [ ask patches in-radius radius [ set pcolor my-color - 2 ] ]
end 

to-report is-open [ a-patch ]
  report ([pcolor] of a-patch = mark-color)
end 

to setup-and-go
  setup
  display
  while [ any? pathmakers ]
  [ go ]
end 

to go
  ask pathmakers
  [ go-pathmaker
  ]
end 

to go-pathmaker
  ifelse length stack > 0
  [ build-maze ]
  [ die ]
end 

to randomize
  set walkers 1 + random 5
  set gap random 5
  set path-width 1 + 2 * random 5
  set curvyness random-float 1.0
  setup-and-go
  wait 1
  if halt = 1 [ stop ]
end

There is only one version of this model, created 11 months ago by James Steiner.

Attached files

File	Type	Description	Last updated
Maze-Maker.png	preview	Preview for 'Maze-Maker'	11 months ago, by James Steiner	Download

This model does not have any ancestors.

This model does not have any descendants.

NetLogo