Sidewinder Maze

From Procedural Generation Algorithms
Jump to: navigation, search

Uniqueness of the Algorithm

The Sidewinder Algorithm is another algorithm like Eller's Algorithm or Binary Tree Maze that doesn't require the entire maze in memory at once. As such it can also infinitely generate a maze. The Sidewinder Algorithm also creates a northward bias, so there will not be dead ends while traveling north.[1] Daedalus[2] was used to generate 500 mazes with the Sidewinder Algorithm and the results were averaged. The results can be seen in the table below.

Average Stats of 500 mazes generated by Daedalus 3.1[2]
Trait Percent of Maze
Dead Ends 27.36%
Straightaways 23.52%
Turns 24.37%
Junctions 22.14%
Crossroads 2.61%

Psuedo Algorithm

  1. Start at the NE cell
  2. Add the current cell to the run set
  3. Randomly chose to continue east, or stop
  4. If you continue east
    • Remove the edge between the current cell and the cell to the east. The is the current cell now.
    • Go to 2
  5. Else
    • Choose a cell in the run set and remove an edge to the north
    • Remove all cells from the run set
    • The next cell in the row becomes the current cell
    • Go to 2.
  6. Continue until all rows are complete

Psuedo Algorithm derived from Jamis Buck's algorithm discription[1]

Further Explaination

The implementation of the Sidewinder Algorithm is more complex than the Binary Tree Algorithm, but not by a large margin. The algorithm generates a maze one row at a time from top to bottom. At each step through the row it decides randomly to stop or continue. Each time it stops it randomly picks a cell since the last stop and connects it to the next row. This continues until the maze is complete.[1] The main body of the algorithm is in the highlighted lines in the implementation below.

Algorithm Implementation

Algorithm Implemented by Jamis Buck[1] in Ruby

 1 # --------------------------------------------------------------------
 2 # An implementation of the Sidewinder algorithm for maze generation.
 3 # This algorithm is kind of a cross between the trivial Binary Tree
 4 # algorithm, and Eller's algorithm. Like the Binary Tree algorithm,
 5 # the result is biased (but not as heavily).
 6 #
 7 # Because the Sidewinder algorithm only needs to consider the current
 8 # row, it can be used (like the Binary Tree and Eller's algorithms)
 9 # to generate infinitely large mazes.
10 # --------------------------------------------------------------------
11 
12 # --------------------------------------------------------------------
13 # 1. Allow the maze to be customized via command-line parameters
14 # --------------------------------------------------------------------
15 
16 width  = (ARGV[0] || 10).to_i
17 height = (ARGV[1] || width).to_i
18 weight = (ARGV[2] || 2).to_i
19 seed   = (ARGV[3] || rand(0xFFFF_FFFF)).to_i
20 
21 srand(seed)
22 
23 # --------------------------------------------------------------------
24 # 2. Set up constants to aid with describing the passage directions
25 # --------------------------------------------------------------------
26 
27 N, S, E, W = 1, 2, 4, 8
28 
29 # --------------------------------------------------------------------
30 # 3. Data structures to assist the algorithm
31 # --------------------------------------------------------------------
32 
33 grid = Array.new(height) { Array.new(width, 0) }
34 
35 # --------------------------------------------------------------------
36 # 4. A simple routine to emit the maze as ASCII
37 # --------------------------------------------------------------------
38 
39 def display_maze(grid)
40   print "\e[H" # move to upper-left
41   puts " " + "_" * (grid[0].length * 2 - 1)
42   grid.each_with_index do |row, y|
43     print "|"
44     row.each_with_index do |cell, x|
45       if cell == 0 && y+1 < grid.length && grid[y+1][x] == 0
46         print " "
47       else
48         print((cell & S != 0) ? " " : "_")
49       end
50 
51       if cell == 0 && x+1 < row.length && row[x+1] == 0
52         print((y+1 < grid.length && (grid[y+1][x] == 0 || grid[y+1][x+1] == 0)) ? " " : "_")
53       elsif cell & E != 0
54         print(((cell | row[x+1]) & S != 0) ? " " : "_")
55       else
56         print "|"
57       end
58     end
59     puts
60   end
61 end
62 
63 # --------------------------------------------------------------------
64 # 5. Sidewinder algorithm
65 # --------------------------------------------------------------------
66 
67 print "\e[2J" # clear the screen
68 
69 height.times do |y|
70   run_start = 0
71   width.times do |x|
72     display_maze(grid)
73     sleep 0.02
74 
75     if y > 0 && (x+1 == width || rand(weight) == 0)
76       cell = run_start + rand(x - run_start + 1)
77       grid[y][cell] |= N
78       grid[y-1][cell] |= S
79       run_start = x+1
80     elsif x+1 < width
81       grid[y][x] |= E
82       grid[y][x+1] |= W
83     end
84   end
85 end
86 
87 display_maze(grid)
88 
89 # --------------------------------------------------------------------
90 # 6. Show the parameters used to build this maze, for repeatability
91 # --------------------------------------------------------------------
92 
93 puts "#{$0} #{width} #{height} #{seed}"

References

  1. 1.0 1.1 1.2 1.3 Buck, J. (2011). Maze Generation: Sidewinder Algorithm. The Buckblog. Retrieved April 10, 2016, from http://weblog.jamisbuck.org/2011/2/3/maze-generation-sidewinder-algorithm.html
  2. 2.0 2.1 Pullen, W. (2015). Daedalus [Computer software]. http://www.astrolog.org/labyrnth/daedalus.htm