add "Houston's algorithm" as an example of how to implement a hybrid …

…algorithm
jamis · Jan 21, 2011 · 7a233e8 · 7a233e8
1 parent 80a7860
commit 7a233e8
Show file tree

Hide file tree

Showing 3 changed files with 61 additions and 0 deletions.
diff --git a/examples/maze.html b/examples/maze.html
@@ -11,6 +11,7 @@
   <script src="../lib/algorithms/division.js" type="text/javascript"></script>
   <script src="../lib/algorithms/eller.js" type="text/javascript"></script>
   <script src="../lib/algorithms/growing_tree.js" type="text/javascript"></script>
+  <script src="../lib/algorithms/houston.js" type="text/javascript"></script>
   <script src="../lib/algorithms/hunt_and_kill.js" type="text/javascript"></script>
   <script src="../lib/algorithms/kruskal.js" type="text/javascript"></script>
   <script src="../lib/algorithms/prim.js" type="text/javascript"></script>
@@ -131,6 +132,14 @@ <h1>Wilson's Algorithm</h1>
   </div>
   <hr />
 
+  <h1>Houston's Algorithm</h1>
+  <div class="row">
+    <script type="text/javascript">Maze.createWidget("Houston", 5, 5, { "class": "small" });</script>
+    <script type="text/javascript">Maze.createWidget("Houston", 15, 15, { "class": "medium", id: "houston_bigger", interval: 25 });</script>
+    <script type="text/javascript">Maze.createWidget("Houston", 30, 30, { "class": "large", id: "houston_biggest", interval: 10 });</script>
+  </div>
+  <hr />
+
   <h1>"Hunt and Kill" Algorithm</h1>
   <div class="row">
     <script type="text/javascript">Maze.createWidget("HuntAndKill", 5, 5, { "class": "small" });</script>

diff --git a/src/algorithms/houston.coffee b/src/algorithms/houston.coffee
@@ -0,0 +1,46 @@
+###
+Author: Jamis Buck <jamis@jamisbuck.org>
+License: Public domain, baby. Knock yourself out.
+
+The original CoffeeScript sources are always available on GitHub:
+http://github.com/jamis/csmazes
+###
+
+# This hybrid algorithm was described to me by Robin Houston. It
+# begins with the Aldous-Broder algorithm, to fill out the grid,
+# and then switches to Wilson's after the grid is about 1/3
+# populated.
+#
+# This gives you better performance than either algorithm by itself,
+# and still ensures that the resulting maze is a uniform spanning
+# tree.
+class Maze.Algorithms.Houston extends Maze.Algorithm
+  constructor: (maze, options) ->
+    super
+    @options = options
+    @worker = new Maze.Algorithms.AldousBroder(maze, options)
+    @threshold = 2 * @maze.width * @maze.height / 3
+
+  isCurrent: (x, y) -> @worker.isCurrent(x, y)
+  isVisited: (x, y) -> @worker.isVisited(x, y)
+
+  step: ->
+    if @worker.remaining < @threshold
+      # kind of messy, need to tell the callback listener that
+      # current cell is no longer current, since the algorithm
+      # is changing.
+      [x, y] = [@worker.x, @worker.y]
+      delete @worker.x
+      delete @worker.y
+      @callback @maze, x, y
+
+      # switch to wilsons and redefine the step method so it
+      # no longer watches the threshold.
+      wilsons = new Maze.Algorithms.Wilson(@maze, @options)
+      wilsons.state = 1
+      wilsons.remaining = @worker.remaining
+
+      @worker = wilsons
+      @step = -> @worker.step()
+
+    @worker.step()
diff --git a/src/widget.coffee b/src/widget.coffee
@@ -65,6 +65,12 @@ Maze.createWidget = (algorithm, width, height, options) ->
       else if maze.algorithm.isVisited(x, y)
         classes.push "f"
 
+    Houston: (maze, x, y, classes) ->
+      if maze.algorithm.worker.isVisited?
+        ACTIONS.Wilson(maze, x, y, classes)
+      else
+        ACTIONS.AldousBroder(maze, x, y, classes)
+
     default: (maze, x, y, classes) ->
       unless maze.isBlank(x, y)
         classes.push "in"