How to create mazes on the hyperbolic plane?

Solution 1:

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.

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.

Solution 2:

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.

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.)

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.)