Is there a maze generation algorithm that includes loops and "bridges" (non planar graph)? The wiki page lists a number of algorithms for generating a maze such as Prim's algorithm and Kruskal's algorithm. It also mentions two algorithms to make "better" mazes that are uniform spanning trees. This is only for "flat" 2d mazes (I think the term is planar graph).
Is there an algorithm to generate similarly "nice" mazes that also have loops and "bridges" (where a path can cross itself -- not a planar graph)?
Example below. A loop in blue, and a "bridge" in red.

image source: http://www.seancjackson.com/downloads-02
 A: Some quick graph theory. You can make a flat 2D maze by beginning with a grid graph (make a 2D grid of points, then draw lines connecting each point to the (up to) four points that neighbor it) and then obtaining a spanning tree for that graph. Here, a “spanning tree” refers to a way of selecting a subset of the lines such that for any two points, there is exactly one path from the first point to the second that doesn’t involve retracing your steps. The algorithms you listed above (Kruskal’s algorithm and Prim’s algorithm) find spanning trees, though other algorithms exist as well that do this.
If I’ve interpreted your question correctly, you’re asking how to generalize this in two ways:

*

*You want to introduce a notion of altitude into the maze so that bridges are possible.

*You want to allow for closed loops.

To achieve (1), we can change the graph we’re starting with so that instead of beginning with a 2D grid of points, we begin with a 3D grid of points. This now allows us to move up and down between the layers. You might consider making the connections between layers run at 45° angles so that they act like staircases. Running any of the spanning tree algorithms on this new 3D grid will then give you what you’re looking for.
To achieve (2), you can add in loops by taking the result of one of the spanning tree algorithms and then adding some of the lines it didn’t select back into the maze. Each added line will necessarily close a loop. If you want the loops to specifically involve bridges, you could add those lines between points at different levels, which will force the loops to require going up and back down again.
Hope this helps!
