weave mazes! only w/ growing tree algorithm currently

jamis · Mar 4, 2011 · f4f365e · f4f365e
1 parent a164868
commit f4f365e
Show file tree

Hide file tree

Showing 13 changed files with 83 additions and 27 deletions.
diff --git a/examples/css/mazes.css b/examples/css/mazes.css
@@ -39,11 +39,20 @@
 .maze .grid.padded .row > div { border: none; padding: 0px; position: relative; background: #ccc; }
 
 .maze .grid.padded div.in div.c,
+.maze .grid.padded div.in.n.u div.wp,
+.maze .grid.padded div.in.n.u div.ep,
+.maze .grid.padded div.in.w.u div.sp,
+.maze .grid.padded div.in.w.u div.np,
 .maze .grid.padded div.in.n div.np,
 .maze .grid.padded div.in.s div.sp,
 .maze .grid.padded div.in.e div.ep,
 .maze .grid.padded div.in.w div.wp { background: #fff; }
+
 .maze .grid.padded div.f div.c,
+.maze .grid.padded div.f.n.u div.wp,
+.maze .grid.padded div.f.n.u div.ep,
+.maze .grid.padded div.f.w.u div.sp,
+.maze .grid.padded div.f.w.u div.np,
 .maze .grid.padded div.f.n div.np,
 .maze .grid.padded div.f.s div.sp,
 .maze .grid.padded div.f.e div.ep,
@@ -72,8 +81,12 @@
 .maze .grid.padded div.wp,
 .maze .grid.padded div.ep { padding-top: 1px; padding-bottom: 1px; }
 
+.maze .grid.padded div.n.u div.ep,
+.maze .grid.padded div.n.u div.wp,
 .maze .grid.padded div.e div.ep,
 .maze .grid.padded div.w div.wp { border-top: 1px solid black; border-bottom: 1px solid black; padding-top: 0px; padding-bottom: 0px; }
+.maze .grid.padded div.w.u div.np,
+.maze .grid.padded div.w.u div.sp,
 .maze .grid.padded div.n div.np,
 .maze .grid.padded div.s div.sp { border-left: 1px solid black; border-right: 1px solid black; padding-left: 0; padding-right: 0; }
 

diff --git a/examples/padding.html b/examples/padding.html
@@ -55,8 +55,8 @@ <h1>Growing Tree Algorithm</h1>
     }
   </script>
   <div class="row">
-    <script type="text/javascript">Maze.createWidget("GrowingTree", 5, 5, { "class": "small", "watch": false, "padded": true, input: growingTreeInput });</script>
-    <script type="text/javascript">Maze.createWidget("GrowingTree", 15, 15, { "class": "medium", "watch": false, "padded": true, id: "growtree_bigger", interval: 25, input: growingTreeInput });</script>
+    <script type="text/javascript">Maze.createWidget("GrowingTree", 5, 5, { "class": "small", "watch": false, "weave": true, "padded": true, input: growingTreeInput });</script>
+    <script type="text/javascript">Maze.createWidget("GrowingTree", 15, 15, { "class": "medium", "watch": false, "weave": true, "padded": true, id: "growtree_bigger", interval: 25, input: growingTreeInput });</script>
   </div>
 </body>
 </html>
diff --git a/src/algorithms/aldous_broder.coffee b/src/algorithms/aldous_broder.coffee
@@ -7,7 +7,7 @@ http://github.com/jamis/csmazes
 ###
 
 class Maze.Algorithms.AldousBroder extends Maze.Algorithm
-  IN: 0x10
+  IN: 0x1000
 
   constructor: (maze, options) ->
     super

diff --git a/src/algorithms/backtracker.coffee b/src/algorithms/backtracker.coffee
@@ -7,8 +7,8 @@ http://github.com/jamis/csmazes
 ###
 
 class Maze.Algorithms.RecursiveBacktracker extends Maze.Algorithm
-  IN:    0x10
-  STACK: 0x20
+  IN:    0x1000
+  STACK: 0x2000
 
   START: 1
   RUN:   2

diff --git a/src/algorithms/binary_tree.coffee b/src/algorithms/binary_tree.coffee
@@ -7,7 +7,7 @@ http://github.com/jamis/csmazes
 ###
 
 class Maze.Algorithms.BinaryTree extends Maze.Algorithm
-  IN: 0x10
+  IN: 0x1000
 
   constructor: (maze, options) ->
     super

diff --git a/src/algorithms/eller.coffee b/src/algorithms/eller.coffee
@@ -7,7 +7,7 @@ http://github.com/jamis/csmazes
 ###
 
 class Maze.Algorithms.Eller extends Maze.Algorithm
-  IN:         0x20
+  IN:         0x1000
 
   HORIZONTAL: 0
   VERTICAL:   1

diff --git a/src/algorithms/growing_tree.coffee b/src/algorithms/growing_tree.coffee
@@ -7,7 +7,7 @@ http://github.com/jamis/csmazes
 ###
 
 class Maze.Algorithms.GrowingTree extends Maze.Algorithm
-  QUEUE: 0x10
+  QUEUE: 0x1000
 
   constructor: (maze, options) ->
     super
@@ -20,12 +20,13 @@ class Maze.Algorithms.GrowingTree extends Maze.Algorithm
   enqueue: (x, y) ->
     @maze.carve x, y, @QUEUE
     @cells.push x: x, y: y
-    @updateAt x, y
 
   nextCell: -> @script.nextIndex(@cells.length)
 
   startStep: ->
-    @enqueue @rand.nextInteger(@maze.width), @rand.nextInteger(@maze.height)
+    [x, y] = [@rand.nextInteger(@maze.width), @rand.nextInteger(@maze.height)]
+    @enqueue x, y
+    @updateAt x, y
     @state = 1
 
   runStep: ->
@@ -36,13 +37,18 @@ class Maze.Algorithms.GrowingTree extends Maze.Algorithm
       nx = cell.x + Maze.Direction.dx[direction]
       ny = cell.y + Maze.Direction.dy[direction]
 
-      if @maze.isValid(nx, ny) && @maze.isBlank(nx, ny)
-        @maze.carve cell.x, cell.y, direction
-        @maze.carve nx, ny, Maze.Direction.opposite[direction]
-        @enqueue nx, ny
-        @updateAt cell.x, cell.y
-        @updateAt nx, ny
-        return
+      if @maze.isValid(nx, ny)
+        if @maze.isBlank(nx, ny)
+          @maze.carve cell.x, cell.y, direction
+          @maze.carve nx, ny, Maze.Direction.opposite[direction]
+          @enqueue nx, ny
+          @updateAt cell.x, cell.y
+          @updateAt nx, ny
+          return
+
+        else if @canWeave(direction, nx, ny)
+          @performWeave(direction, cell.x, cell.y, (toX, toY) => @enqueue(toX, toY))
+          return
 
     @cells.splice(index, 1)
     @maze.uncarve cell.x, cell.y, @QUEUE

diff --git a/src/algorithms/hunt_and_kill.coffee b/src/algorithms/hunt_and_kill.coffee
@@ -7,7 +7,7 @@ http://github.com/jamis/csmazes
 ###
 
 class Maze.Algorithms.HuntAndKill extends Maze.Algorithm
-  IN: 0x10
+  IN: 0x1000
 
   constructor: (maze, options) ->
     super

diff --git a/src/algorithms/prim.coffee b/src/algorithms/prim.coffee
@@ -7,8 +7,8 @@ http://github.com/jamis/csmazes
 ###
 
 class Maze.Algorithms.Prim extends Maze.Algorithm
-  IN:       0x10
-  FRONTIER: 0x20
+  IN:       0x1000
+  FRONTIER: 0x2000
 
   START:    1
   EXPAND:   2

diff --git a/src/algorithms/sidewinder.coffee b/src/algorithms/sidewinder.coffee
@@ -7,7 +7,7 @@ http://github.com/jamis/csmazes
 ###
 
 class Maze.Algorithms.Sidewinder extends Maze.Algorithm
-  IN: 0x10
+  IN: 0x1000
 
   constructor: (maze, options) ->
     super

diff --git a/src/algorithms/wilson.coffee b/src/algorithms/wilson.coffee
@@ -7,7 +7,7 @@ http://github.com/jamis/csmazes
 ###
 
 class Maze.Algorithms.Wilson extends Maze.Algorithm
-  IN: 0x10
+  IN: 0x1000
 
   constructor: (maze, options) ->
     super

diff --git a/src/maze.coffee b/src/maze.coffee
@@ -11,6 +11,7 @@ class Maze
     options ?= {}
     @grid = new Maze.Grid(@width, @height)
     @rand = options.rng || new MersenneTwister(options.seed)
+    @isWeave = options.weave
 
     unless @rand.randomElement?
       @rand.randomElement = (list) -> list[@nextInteger(list.length)]
@@ -40,11 +41,13 @@ class Maze
   isWest: (x, y) -> @grid.isMarked(x, y, Maze.Direction.W)
   isNorth: (x, y) -> @grid.isMarked(x, y, Maze.Direction.N)
   isSouth: (x, y) -> @grid.isMarked(x, y, Maze.Direction.S)
+  isUnder: (x, y) -> @grid.isMarked(x, y, Maze.Direction.U)
   isValid: (x, y) -> 0 <= x < @width and 0 <= y < @height
   carve: (x, y, dir) -> @grid.mark(x, y, dir)
   uncarve: (x, y, dir) -> @grid.clear(x, y, dir)
   isSet: (x, y, dir) -> @grid.isMarked(x, y, dir)
   isBlank: (x, y) -> @grid.at(x, y) == 0
+  isPerpendicular: (x, y, dir) -> (@grid.at(x, y) & Maze.Direction.Mask) == Maze.Direction.cross[dir]
 
 Maze.Algorithms = {}
 
@@ -61,15 +64,48 @@ class Maze.Algorithm
   updateAt: (x, y) -> @updateCallback(@maze, x, y)
   eventAt: (x, y) -> @eventCallback(@maze, x, y)
 
+  canWeave: (dir, thruX, thruY) ->
+    if @maze.isWeave && @maze.isPerpendicular(thruX, thruY, dir)
+      nx = thruX + Maze.Direction.dx[dir]
+      ny = thruY + Maze.Direction.dy[dir]
+      @maze.isValid(nx, ny) && @maze.isBlank(nx, ny)
+
+  performWeave: (dir, fromX, fromY, callback) ->
+    thruX = fromX + Maze.Direction.dx[dir]
+    thruY = fromY + Maze.Direction.dy[dir]
+    toX = thruX + Maze.Direction.dx[dir]
+    toY = thruY + Maze.Direction.dy[dir]
+
+    @maze.carve(fromX, fromY, dir)
+    @maze.carve(toX, toY, Maze.Direction.opposite[dir])
+
+    if @rand.nextBoolean()
+      @maze.carve(thruX, thruY, Maze.Direction.U)
+    else if @maze.isNorth(thruX, thruY)
+      @maze.uncarve(thruX, thruY, Maze.Direction.N|Maze.Direction.S)
+      @maze.carve(thruX, thruY, Maze.Direction.E|Maze.Direction.W|Maze.Direction.U)
+    else
+      @maze.uncarve(thruX, thruY, Maze.Direction.E|Maze.Direction.W)
+      @maze.carve(thruX, thruY, Maze.Direction.N|Maze.Direction.S|Maze.Direction.U)
+
+    callback(toX, toY) if callback
+
+    @updateAt fromX, fromY
+    @updateAt thruX, thruY
+    @updateAt toX, toY
+
 Maze.Direction =
-  N: 1
-  S: 2
-  E: 4
-  W: 8
+  N: 0x01
+  S: 0x02
+  E: 0x04
+  W: 0x08
+  U: 0x10
+  Mask: (0x01|0x02|0x04|0x08|0x10)
   List: [1, 2, 4, 8]
   dx: { 1: 0, 2: 0, 4: 1, 8: -1 }
   dy: { 1: -1, 2: 1, 4: 0, 8: 0 }
   opposite: { 1: 2, 2: 1, 4: 8, 8: 4 }
+  cross: { 1: 4|8, 2: 4|8, 4: 1|2, 8: 1|2 }
 
 class Maze.Grid
   constructor: (@width, @height) ->

diff --git a/src/widget.coffee b/src/widget.coffee
@@ -14,6 +14,7 @@ Maze.createWidget = (algorithm, width, height, options) ->
     classes.push "w" if maze.isWest(x, y)
     classes.push "s" if maze.isSouth(x, y)
     classes.push "n" if maze.isNorth(x, y)
+    classes.push "u" if maze.isUnder(x, y)
 
   ACTIONS =
     AldousBroder: (maze, x, y, classes) ->
@@ -163,7 +164,7 @@ Maze.createWidget = (algorithm, width, height, options) ->
     else
       value = options.input
 
-    @maze = new Maze(width, height, Maze.Algorithms[algorithm], seed: options.seed, rng: options.rng, input: value)
+    @maze = new Maze(width, height, Maze.Algorithms[algorithm], seed: options.seed, rng: options.rng, input: value, weave: options.weave)
     @maze.element = this
     @maze.onUpdate(updateCallback)
     @maze.onEvent(eventCallback)