Unicursal Mazes

I’ve been working on my javascript maze generator again, you can grab it here off github:

https://github.com/mdchaney/jsmaze

I added a couple of new algorithms to it for generating mazes: Prim’s algorithm and the “bacterial” algorithm.  Neither one is good for generating mazes, honestly, and my drunk-walk algorithm remains the best way.  Still looking at a possibility of adding another algorithm similar to the recursive backtracker that allows one to determine from where the “backtracking” will continue.

I became interested a few weeks ago in the concept of the unicursal maze, also known as a labyrinth.  This isn’t really a maze; it’s a space-filling curve that visits all areas of the space exactly one time with no branches.

Screen shot 2014-03-05 at 8.55.54 AM

Interestingly, I cannot find anything online about generating them except one.  That gentleman’s approach to generating them is to first generate a standard maze using any algorithm, then close the exit, and finally solve the maze leaving the “solution” in place as a set of walls.  That creates a unicursal maze, but a very specific kind where the entrance and exit are side-by-side.  Plus, it works because the solution will cut the rectangular cells into more rectangles as long as it goes to the middle of each cell.  Using another base such as hexagons or snub-square tiling will cause the new maze to have differently shaped cells.  It’s not a general algorithm.

So what is a general algorithm?  I don’t have a good answer, yet.  I was able to make a simple one from a recursive backtracker.  It’s actually remarkably simple.  First, I keep track of the number of cells that remain unfilled.  Then, I do a standard recursive backtracking algorithm with one modification.  If it runs into a dead end, it returns “false”.  If it gets to the end cell and there are still unfilled cells, it returns false.  After moving to a square if it returns “false” then it closes the wall back up and tries the next.  If all moves for a cell return false then we simply return false.

But there is one way to make it return “true”.  That is if it gets to the last cell and there are no remaining unfilled cells.  In that case it returns true.  And when that one returns true it simply unwinds the stack all the way back to the beginning and is done.

Ultimately it will try a lot of paths.  The number of tries that it requires grows exponentially with the size of the maze.  So a 7×5 works in a couple of seconds, and a 10×7 just doesn’t.  At least not in a 4 or 5 minutes that I’ve waited.

So that particular algorithm, for lack of a better term, sucks.  But it works and I think it’s a start.  One thing that I know is that we can avoid some dead ends and such by looking ahead a bit and trying to not move in such a way as to create a dead-end tunnel.  Thinking of a standard rectangular maze that would mean that if we took a right turn we would have to move at least two squares before turning right again.  Coming within one space of an outside wall would be a problem unless it’s the last run to the end cell.  Generalizing the algorithm to work on any graph is the key, and it’s a tough one.  I’ve added some comments to the maze generator, will be doing more as I get more ideas.

Maze.maze_styles.unicursal = function() {

   var end_cell = this.end_cell();
   var pieces_left = this.cells.length-1;

   function recursive_maze(cell,entry_wall,depth) {
      cell.depth=depth;
      cell.entry_wall=entry_wall;

      // Check if this is the end (yes, I'm aware of the
      // optimization).
      // Alternately, we could just say "if pieces_left is 
      // 0 then this cell is the end", maybe with an edge
      // check.
      if (cell == end_cell) {
         if (pieces_left == 0) {
            return true;
         } else {
            return false;
         }  
      }  

      // Now, go through the surrounding cells and recurse
      for (var k=0 ; k<cell.perm.length ; k++) {
         var wall_num = cell.perm[k];
         var neighbor = cell.walls[wall_num].neighbor(cell);
         if (neighbor && !neighbor.visited()) {
            pieces_left--;
            cell.walls[wall_num].open();
            var winner = arguments.callee(neighbor,cell.walls[wall_num],depth+1);
            if (winner) return true;
            pieces_left++
            cell.walls[wall_num].close();
         }
      }

      return false;
   }
   var success = recursive_maze(this.start_cell(),null,0);
   if (!success) {
      throw "Cannot create unicursal maze with these parameters."
   }
}

11 thoughts on “Unicursal Mazes

  1. I also have been searching for an algorithm for unicursal mazes. I also wanted a more general algorithm than those on line. The idea I came up with was to first generate a domino style arrangement (splitting the space up into random 2×1 units) because any path that can be morphed into a unicursal maze cannot contain an area that cannot be split into domino shaped area (except for a start or finish square). The path must enter one cell of the domino and exit the other. This eliminates a huge number of illegal possibilities before you start and should make your algorithm much faster.

  2. Thank you for your comments. You are correct, but the issue is that I’d like to generalize that concept since not all of my mazes are square.

  3. Each geometry has its own considerations, so I don’t think you can generalise in that way. For example a maze with hexagonal cells has no equivalent requirement for a legal unicursal maze. There a single cell can always be integrated into an existing path provided that any two of its neighbors are directly linked to each other. That is clearly not possible with square cells.

  4. Although, thinking about it, the domino shape is the “square” equivalent to the hexagon in that it can be added to an existing path if two adjacent neighbors are directly connected or it shares 2 wall with a single neighbor. (A hexagon can never share two walls with a neighbor but other shapes, such as in a circular maze might). So maybe a general strategy is possible.

  5. Any more thoughts on the packing algorithms since originally explored? I recently walked a unicursal labyrinth comprising concentric circles in Santa Fe… Seems to be a common layout for such a thing. Fun topic! Thanks in advance.

    1. Yeah, there are a couple of common layouts for unicursal labyrinths, which are usually made for meditation or prayer as people walk through them. I typically think about once a month about this problem and haven’t come up with another good solution. There is a pretty simple method of splitting a standard maze, but you end up with the entrance and exit side-by-side. There’s a way to modify the maze such that one tunnel goes around two edges, then after splitting you remove the outer half of that and have a unicursal maze with the entrance and exit at different places. However, it’s still cheating. The other algorithms that I’ve explored still work by randomly creating a maze and then reversing when it’s obvious that a unicursal maze may no longer be created from the starting piece. The issue there is that it usually gets too far along before making that determination, so the “fix” is to figure out how to make that determination earlier and still cheaply. For instance, if you have a tunnel that loops around and leaves a single square untouched we know that it can no longer be a unicursal maze. Making that determination early on is the trick. However, we might also be solving the wrong problem. Still not sure. There’s probably a PhD thesis in there somewhere.

  6. Yeah, I’m finding that analysis of some of the common layouts reveals their similarity… PhD topic indeed! I’m not sure if labyrinth seals in fluid dynamics are unicursal or just complex, but I’m sure it’s well studied. Thanks for fielding my question. I will post back if I discover anything interesting. Cheers, D

  7. I’m not above a little cheating!

    I’m one of the programmers behind Ink/Stitch, an open source machine embroidery design platform. I’d love to be able to add a feature that fills an arbitrary shape with a unicursal maze. One could then use that maze as the path for the sewing machine to follow, giving a really interesting effect on fabric.

    You’ve given me a lot to think about, thank you!

  8. It’s easy to draw unicursal mazes by hand on a rectangular grid. The key idea is that every unicursal maze consists of two distinct networks. Furthermore, each cell of such amaze can be represented by a hexadecimal number. A competent programmer could use this approach to generate mazes. Send me an email if you want more details.
    email etho3681@bigpond.net.au

  9. could try only turning on an odd number of moves in one direction in addition to the backtracking. this leaves an even number of empty spaces between current and past filled spaces. (assuming 0 as even)

    1. more details. untested.

      1. start moveCounter at 0
      2. create an empty stack
      3. pick a start cell and an end cell
      4. make start current
      5. pick an empty neighbor to current
      6. pushing current to stack and increment moveCounter
      7. make neighbor current
      8. check moveCounter:
      a. if moveCounter is odd, make previous corner turn available (if left was done, allow left again).
      b. if moveCounter is even, make the opposite of the previous corner turn available (if left was done, allow right).
      c. Straight is always available (and does not count as a corner turn).
      d. If only one direction inside and unvisited, make it available
      9. Choose an option resulting from step 8
      10. If going straight:
      a. Check 2 cells ahead, if outside or visited and the left and right neighbors are unvisited and inside, turn the same as last time.
      11. If stack length less than labyrinth size and end cell is neighboring, treat as visited.
      12. If a turn was made, remember it and set moveCounter to 1
      13. If stuck, pop the stack and try a different option
      14. Repeat from step 5 until all stack is equal to labyrinth size and end cell is in the last element of the stack.
      15. Iteratively carve the path by popping the stack and disabling walls in the way.

Leave a Reply to Dave Mear Cancel reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.