26
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Which grid are you using? $\endgroup$ – PyRulez Apr 7 '17 at 13:46
  • $\begingroup$ You could use a graph theory based method. $\endgroup$ – PyRulez Jan 18 '18 at 21:45
  • $\begingroup$ @PyRulez Those are exactly the methods I mean by 'the standard maze generation algorithms'; while they're abstractly the best, they don't really work for the specific situation I was looking at for the reasons I give (they require holding the maze in memory). $\endgroup$ – Steven Stadnicki Jan 18 '18 at 22:36
  • $\begingroup$ You can use Kruskal's algorithm in a "lazy" way with an infinite grid? $\endgroup$ – PyRulez Jan 18 '18 at 22:58
17
+150
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ I'm interested in the code, even if the others might not be. :) $\endgroup$ – J. M. isn't a mathematician Nov 19 '11 at 16:06
  • $\begingroup$ 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. $\endgroup$ – Steven Stadnicki Nov 25 '11 at 7:59
  • 3
    $\begingroup$ 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. $\endgroup$ – hmakholm left over Monica Jan 7 '12 at 21:51
  • 1
    $\begingroup$ I'm interested in the code as well. $\endgroup$ – Ryan Kennedy Jul 7 '14 at 21:15
2
$\begingroup$

Mazes can be created in the hyperbolic plane very easily: you only need to ensure that the starting and goal points are both reachable from infinite regions, and connect the cells randomly with high enough probability, and it is guaranteed that the maze is solvable. I am not sure whether this is exactly what Steven Stadnicki wants, but it does generate interesting mazes. I am using this in HyperRogue -- the idea is the easiest to explain with the Princess Quest maze.

enter image description here

This is the periodic pattern used, consisting of heptagonal rooms (which have seven gates) and infinite tree-like corridors. Gates are randomly opened or closed; if they are closed, they can be opened by stepping on nearby green plates (which may not exist, or may exist on the other side). You typically start 100 steps away in the 12 o'clock direction, and your goal is to free the Princess by stepping on the green plate (at 7 o'clock on the picture).

It is guaranteed that it is possible to free the Princess:

  • the opening plate always appears in a corridor, so its connected component is infinite (and similarly for the starting point),
  • if you consider the obstacle (i.e., the Princess's prison and all the other heptagonal rooms which you have to circumvent while trying to reach her), it has a tree structure: to circumvent the given heptagonal room $H$, you may need to also circumvent each of the 6 heptagonal rooms adjacent to $H$ (6 because we are not including the parent). The probability that a given room has child rooms depends on the probabilities of open/closed gates and opening plates occuring. This probability is high enough to make the maze interesting, but low enough to ensure that the obtained branching process generates a finite tree with probability 1. (Hyperbolic geometry is important in this argument -- otherwise there would be cycles in the obstacle graph; well, I guess it could be adjusted to Euclidean geometry, but the situation is much more complicated, and the generated mazes are less interesting IMO.)

enter image description here

This is the Yendor Quest in Hell: you have to reach a cell 100 steps away, to find the key to unlock the purple Orb of Yendor. This construction of obstacles is very simple (just pick some tiles randomly as the centers of "big stars", and all the tiles adjacent to them are impassable), but a similar reasoning guarantees that it generates a solvable maze. (HyperRogue does not guarantee that the starting/key regions are infinite, because it is extremely unlikely anyway that they are finite, but it would be easy to guarantee this.)

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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