Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm interested in building maze-like structures on the [5, 4] tiling of the hyperbolic plane, where by maze-like I mean something akin to a spanning tree of the underlying lattice: a subgraph of the lattice that's still connected (every cell can reach every other cell) but with a sort of 'distance multiplier' effect where from any given cell in the lattice, there are likely to be cells that are nearby in the original tiling with a long 'shortest path' through the subgraph to reach that point. (This is an admittedly imprecise notion, but I doubt there are explicit results on this sort of thing anyway). I could use any of the standard maze-generation algorithms, but they involve a 'prepass' that holds the entire lattice graph in memory and so aren't really practical for infinite (or functionally infinite) lattices; I'm looking for something that can generate walls (or equivalently, cut edges from the underlying graph) in a 'local' fashion without needing to look explicitly at the global structure.

If I were on the plane, then there are relatively straightforward ways of doing this: for instance, for each cell, place a wall randomly on either that cell's south or east edge. With probability 1 this will create a spanning tree of the plane - it's not a 'random' spanning tree (in particular, of course, it's impossible for any cell to have both its south and east sides 'walled', which I imagine happens with probability 0 for a random spanning tree of the plane) but it's a tree, even so. For instance, here are two $5\times 5$ grids of cells with their east or south sides randomly walled:

rectangular maze another rectangular maze

Similarly, if the generation process uses a 3-sided coin with equal probabilities of drawing a south wall, east wall or no wall, then the resulting grids aren't spanning trees (there can exist multiple disjoint paths between nodes), but they still clearly have the sort of distance multiplication I'm looking for:

a looser rectangular maze another loose rectangular maze

Unfortunately, these techniques don't work as well for the hyperbolic grid I'm interested in; getting a canonical notion of outward edges is a bit more challenging, and the 'maziness' of the result is much harder to control. Does anyone know of a scheme similar to the coin-flipping techniques with only local information generated/used that can be applied to arbitrary regular tilings?

share|improve this question

1 Answer 1

up vote 8 down vote accepted
+150

Your method for the Euclidean square grid introduces an asymmetry between southeast and northwest that leads to two crucial features:

  • From each point, there's a wall going either north or west. These walls form infinite contiguous obstructions towards the Northwest; their course, starting from any given point, is a random walk whose direction converges towards Northwest. Thus, at every point, regardless of what happens southeast of it, the plane northwest of the point is divided into two halves, and you have to go back southeast past the point to get from one half to the other.

  • On the other hand, towards the southeast, every square is open towards either south or east. Thus, from every square you can take an infinite random walk towards the Southeast. If you start in two different places, these infinite random walks will meet with probability $1$, which is why the whole thing is a spanning tree with probability $1$.

To transfer this idea to the hyperbolic plane, we need to introduce a similar asymmetry. We can do this by singling out a point and distinguishing between steps that lead towards or away from the point. Whereas in the Euclidean case we could swap the roles of southeast and northwest, in the hyperbolic case the method will only work one way. If we let the contiguous walls run towards the chosen point and the contiguous paths run away from it, the paths will diverge more quickly than they randomly fluctuate towards each other, and there will generally not be paths between all sites. However, if we let the contiguous walls run away from the chosen point and the contiguous paths run towards it, then all sites are guaranteed to be connected, and the contiguous walls will force connections between nearby sites on opposite sides to go all the way "inward" to where the wall starts.

Here's an image of a maze on the $[5,4]$ tiling of the hyperbolic plane created in this manner, visualized using the Poincaré disk model. The straight segments, which lead neither away nor towards the centre, are all walled, except for the innermost ones. For the arced segments, each tile "owns" the ones that lead towards the centre from that tile, i.e., the ones for which the tile is in the interior of the circle of which the segment is an arc. For each tile, exactly one of the segments it owns is open, chosen randomly with uniform distribution, and the others are walled.

hyperbolic maze

I'll create some more images later of how the maze looks if we place the centre of the disk on a different point (i.e. not the one used as a centre for the construction of the maze). Let me know if you'd like me to post the code I used to create this.

share|improve this answer
2  
I'm interested in the code, even if the others might not be. :) –  J. M. Nov 19 '11 at 16:06
    
I'd also love to see the code! This is somewhat more... outward-directed than I'd have hoped, but I think that's an inevitability of the process. –  Steven Stadnicki Nov 25 '11 at 7:59
1  
It seems that there are never any places where three or more walls come together here. So in the OP's Euclidean example, the walls and passages both form connected trees with probability 1, whereas here the passages are always connected (and not only probabilistically so) but the walls never are. –  Henning Makholm Jan 7 '12 at 21:51
    
I'm interested in the code as well. –  Ryan Muller Jul 7 at 21:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.