Weave Mazes: Your Take?
28 February 2011 —
A challenge is given, urging the reader to consider how a maze might be created in which passages weave over and under each other. A subsequent article is foreshadowed
—
1-minute read
Later this week I’m going to post an article about how you might implement “weave mazes”, like this one:
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?
Reader Comments
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.
28 Feb 2011
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?
1 Mar 2011
PS. I don’t know the answer! It may be that there is no sensibly-efficient algorithm.
1 Mar 2011
@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.
1 Mar 2011
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
2 Mar 2011
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.
2 Mar 2011