Weave Mazes: Your Take?

Posted by Jamis on February 28, 2011 @ 09:34 AM

Later this week I’m going to post an article about how you might implement “weave mazes”, like this one:

weave maze

This is a maze where some of the passages “weave” over or under other passages. It’s a type of 3D maze, but very constrained (mostly for esthetic reasons):

  • Passages may only move under or over each other when they are perpendicular to each other.
  • A passage may not terminate (dead-end) either under or over another passage.
  • Passages may not change direction either over or under another passage.

Before I post my implementation, though, I wanted to get you thinking: how would you implement a weave maze?

Posted in Under the Hood

Comments

Have something to add? Click here to leave a comment.

28 Feb 2011

1. Anoymous Cow said...

If you used the recursive backtracker, you could apply those 3 rules above to decide if you can continue, instead of just terminating (and starting the back track) on the single “walls all around” dead-end condition. You may want to use a random chance for enabling these rules, as the maze may never branch much if it can always go over itself.

In terms of storage you need only include the extra two states of a crossing passage, either up/down on top of left/right, or vice a versa.

01 Mar 2011

2. Robin Houston said...

A more interesting (or at any rate more difficult) question: how would you generate a weave maze uniformly at random – so that every possible weave maze is generated with equal probability?

3. Robin Houston said...

PS. I don’t know the answer! It may be that there is no sensibly-efficient algorithm.

4. Jamis said...

@Anonymous, that’s pretty much the approach I used in Theseus, and which I’ll be describing later this week. Way to ruin the surprise! ;)

@Robin, that is definitely an interesting question. I don’t dare touch it, though, since intuition is pretty useless when dealing with uniform spanning tree algorithms. :) If you ever do figure something out, though, I’d be very interested.

02 Mar 2011

5. KevBurnsJr said...

One way I might implement a weave maze is by extending the maze+xml media type with a “level” or “z” cell attribute and writing an application which reads a maze from a text file (matrix of .-+|) and exposes the appropriate XML representations as a web service. http://amundsen.com/media-types/maze/ http://amundsen.com/blog/archives/1091

1
2
3
4
5
6
7
8
9
10
11
.+ +-+ +-+ +-+-+ +-+ +-+---+ +-----+ +-+
 | | | | |   |   | |   |   | |     | |
 +---+ | +---|---+ +-+ | +---|-----|---+
 | |   |     |       | | | | |     | | |
 | +---+ +---+-+ +---+ | +-+ +---+---+ |
 |       |     | |     |         | |   |
 +-+ +-+-+---* | | +-* +-----+ *-+ +---+
   |   |       | | |         |   |      
 +-----|-+ +---+ +-|---------|-* | +---+
 
 #...

6. Mike Amundsen said...

As KevBurnsJr mentioned, I implemented a simple “perfect square” generator and host those mazes on a public server: http://amundsen.com/examples/mazes/2d/ using the maze+xml media type.

Seems trivial to render a “weave” maze using that media type. My current internal storage of mazes is simply a set of “rooms” w/ “doors” (see dump here: http://amundsen.com/examples/mazes/2d/five-by-five/).

If someone wanted to build a weave maze and pass me a version w/ this internal rendering format (1s and 0s for rooms), i’d be happy to host the maze so folks could work on clients to run against it.