Almost exactly 4 years ago,¹ I wrote a blog post about making an infinite maze. You can read it. In fact, you should, because I’m going to assume you know what’s in it.

In that post, I talked about how you needed something to bridge a maze in finite space to one in infinite space. A shape to the infinite structure where you can determine each supercell’s exits in constant time.²

First, let me clarify the type of infinity I’m talking about, as this actually changes the shape of the problem.

I’m talking an infinite plane. That means that every 2D pair of numbers is on this plane. Defined by this:³

$$\mathbb{R}^2 = { (x, y) \mid x, y \in \mathbb{R} }$$

There’s also an infinite quadrant. That means that one corner is fixed, say (0,0), and the rest continue off into infinity. Defined by this:

$$\mathbb{R}^2_{\geq 0} = { (x, y) \mid x \geq 0, y \geq 0 }$$

If I were fine with an infinite quadrant, my infinitely nested maze approach would work. That’s something I don’t think I considered back in 2022. But, then again, if someone were to say “hey, this world goes on forever, but don’t go too far to the left or down,” it wouldn’t feel like it actually went on forever, right?

I’m talking about the cool infinite 2D plane. The thing that really feels infinite.

Evaluating Other Bridges

Back to that Uzumaki

Alright, let’s refresh our memory on the first one. It was a bidirectional square spiral.⁴ Here’s a visualization of how it looks in 2D space.

My first thought had been a unidirectional square spiral, but I dismissed it as generally inferior, as I wanted the player to be able to go in the wrong direction forever. This isn’t a property that will hold with all the bridges that I propose, but it is something that I generally think is desirable in a maze.

Here’s the boring square spiral.

It is, of course, also possible to have the maze spiral out in four directions. This one has the unfortunate characteristic of looking like a swastika,⁵ and little advantage other than slightly more complexity at (0, 0).⁶

Perhaps less intuitively, you can also make a tridirectional spiral. It’s only moderately more interesting at the source. Once you get past three or so units from origin, they all look the same.

Breaking up the Problem

All of my approaches have involved handling the entire 2D plane space in one algorithm. However, we could also partition the space into halves or quads and have different algorithms that each wind back in on themselves to completely cover the plane. This is maybe slightly less interesting if you have a rough idea of what quadrant of the maze you’re in and where the destination is, as you’d know you’d need to cross the origin, but if you know the whole shape of the maze, they’re all boring in their own ways.

Let’s explore some of these. We can trivially either break this up into normal axis-aligned quadrants or rotated 45 degree axes.

I don’t know that any of these are really strictly better than my bidirectional spiral. Once you get out far enough, they’re basically the same.

The nice thing about splitting things up this way is that it works generally. If you have any pattern that fills up a quadrant from its corner, you can make it fill the plane. Each quadrant gets its own copy and you connect the four corners of the origin, making sure not to form a loop.

Four different trees connected by three connections remains one tree.

There are two ways of connecting these. The first, like above, is to connect them around the origin like a pinwheel. The second is to mirror them across axes.

Fractal Trees

One of the problems with my infinite bridges is that they don’t really have branching. Where the spirals have choice, it’s just at the origin node. It’s not very interesting. Is there a way to make it so the user has choice in constant time?

It turns out, yes. It’s with a simple tree structure called a ruler function. For each cell , count the number of trailing zeroes. Whichever coordinate has fewer zeroes, or, in the case of a tie, the larger number has a neighbor in that direction towards zero.

This results in a series of highways that all lead toward the origin. It’s less than ideal in some ways because there’s always a knowable way to get to the origin, and because a close coordinate usually means the path to get to it is short, but it offers a good amount of choices if the user is unaware of where to go (often three or four).

Binary Trees

One of the most efficient maze generation algorithms is the binary tree maze. Basically, for each node, you flip a coin. If it’s heads, you connect to the north. If it’s tails, you connect to the east. Nodes on the north edge are connected east and west, and nodes on the east edge are connected north and south. You don’t need to hold anything in memory, and your performance is $O(1)$.

Because of this, it’s tempting to treat this as the infinite bridge, especially since this pattern would be the first actually random pattern we discovered for the bridge. It’s so simple—just flip a coin at every node.

There’s a couple problems with this approach. First, you actually need a source of randomness. That isn’t so bad; we can just hash the coordinate value. That operation gets slow as you get farther away, so we can modulo the coordinate value and then hash that. That will necessarily introduce periodicity into the top-level maze, but the submazes being random makes it so that isn’t a dealbreaker for me.

My concern there was that by limiting the size of the period space, it’s possible that grooves (e.g. horizontal, vertical, or diagonal lines) could run across the entire period, causing my maze to be disconnected, making it no longer a “maze” at all.

However, this concern was misguided. There’s not a chance that a full plane binary tree could be disconnected. It’s guaranteed that it will be.

The reason for this wasn’t obvious (to me, at least), but on thinking through it, it’s more obvious. For my perfect maze, I need everything to be connected and for there to be no loops. This means that within a period, I need it to connect to both the periods north and to the east (if it connects to one but not the other, the pattern only connects in that direction ever). That’s fine, it could happen. However, it’s not enough that it both connects to each directions—those connections need to connect to each other within the period, and binary trees actually make that impossible.

Furthermore, if we break the binary tree constraint of “either north or east” to make those connections connect to each other, they will necessarily form a loop. The reason for this is, once again, non-obvious.

Our periodic grid can be folded into a torus (it loops in both the X and the Y). Each configuration of our period will repeat in at least one direction (if nothing else, the northeast node must connect north or east, connecting it to either vertically or horizontally). However, because each cell can only connect to one of those (they can only have one child), they can only connect north, east, or northeast. Anything else would require two children (a crossroad). While a northeastern direction might cause the torus to be fully connected (since the period crosses the same tiles), it would cause our infinite grid to be disconnected.

Well, you may say, you introduced this problem by introducing the period in the first place. That’s theoretically true. A true random (assuming that we did not need to have reproducibility as we could keep it all in memory) would make this work. Since we do need this to be reproducible, we need something we can use to get a reproducible results—some sort of hashing function.

As we’ve seen above, a periodic one is a nonstarter. However, a hashing function being aperiodic does not guarantee that the tree will be connected. As an example, Thue-Morse (computing the parity of the bits) will give us our coin flip, it’s aperiodic, and from looking at it, it’s easy to see that it’s obviously disconnected. Is there probably some aperiodic hash that would give us what we wanted? Probably. Am I sure of that? No, and I want to guarantee that I am generating a perfect infinite maze, so even our complete binary tree is out.

However, we do know that if you go back to our original binary tree maze, that will be completely connected, even if submazes within it are periodic. This is guaranteed because there’s an unbroken corridor that runs along two edges of it. This can be used to generate an infinite quadrant, and we can use the folding trick from earlier to turn our infinite quadrant into an infinite plane.

This gets us nice-looking branching, but the bias in the maze generation⁷ is relevant to its use as a top-level infinite bridge. Thankfully for the binary tree approach, most other maze generation algorithms do not give us any guarantees in infinite space, making it a strong contender as an infinite bridge.

Return to Hilbert

In my previous post, I was skeptical that a Hilbert curve would work for this. Part of it was due to it being a space-filling curve, and not thinking it was transferrable, and partly because as it iterates, it changes the orientation of all of the segments (what was up is right, right is up, left is down, down is left).

That is true, but it restores itself every other time. If you just look at every other step of the Hilbert curve iteration, it looks like it’s growing outward. If you don’t display it within a fixed space, but instead keep the line lengths constant, you get a curve growing out from the origin to infinity.

So all we need to do is find a function that can convert (X, Y) coordinates to an index on the curve and convert (idx - 1) and (idx + 1) back into coordinates. Thankfully, Wikipedia had an implementation.⁹

Now, I think it is technically true that a Hilbert curve cannot fill an infinite plane, but it can fill an infinite quadrant. And, as we’ve seen with the binary tree, if you have something that works on a quadrant, we can make it work on an infinite plane.

However, due to how it’s joined, I think it still remains a curve (although perhaps not a Hilbert curve) when mirrored into a halfplane (there are no branches), but once the halfplane is reflected, it is no longer a curve as it introduces a branch. In my case, I join the origin of Q1 to Q2, Q2 to Q3, and Q3 to Q4, leaving Q4 unconnected from Q1 to avoid a loop.

While it lacks branches aside from the origin, it has some properties that are nice. It never goes in one direction for too long, and it’s not easily apparent where you’re going if you know where you are. It does lack branches, which limits it somewhat, but it makes a nice infinite bridge.

However, since it has multiplication and division, it gets slower much faster than other algorithms. The time it takes to run (like all of these algorithms) is dependent on how many bits it takes to represent the number. If you want to see it chug, just toss in a really big number, zoom out, and try scrolling.

Peano curve is also doable using this approach. Moore curve isn’t because it loops. I suspect most (if not all) curves that start at a corner, don’t loop, and can convert back and forth between index and coordinate can be mapped in such a way.

Revisiting Nested Mazes

Coincidentally, it occurred to me when I was writing out the algorithm for the quadrant spiral math that since I realized that my nested maze algorithm works for an infinite quadrant, and I have a way of taking a quadrant pattern and trivially bridging it into four different conditions… I solved this problem. It’s literally just a Gordian knot that I can cut by saying “yeah it crosses this line at (0, 0)”.

Also, it occurred to me that I actually was changing the shape of the problem by placing the lines where infinite boundaries cross at $X = 0$ and $Y = 0$. If I centered the mazes around the origin instead of placing the corner there, the places where infinitely many boundaries cross are at infinity. And since, as I’ve discovered, the performance of my infinite bridges are not $O(1)$, but (usually) $O(\log n)$, these boundaries aren’t necessarily the limiting factor that I thought.

For a completely arbitrary comparison, I pushed the maze to $10^{983196}$.¹⁰ Keep in mind that this is just one-off runs, which means that it might be entirely wrong.

They all end up taking roughly the same amount of time.¹¹ It’s not fast, but $10^{983196}$ is a large number.¹² However, once you get that far out there, the pathological border crossing case for infinitely nested mazes is there and I’m not sure how long it will take.

Which to Use

When I made THIS MAZE HATES YOU, I used a three-nested set of 25x25 mazes with a bidirectional spiral on top. This isn’t ideal for a few different reasons. First of all, 25x25 is a pretty small maze size. Not really apparent to the user except at the beginning of the game (when they’re looking down), but I suspect 128x128 would have been pretty snappy as well.

I’d chosen 25x25 to keep the mesh size I was generating down, but if I were doing it again I’d try to decouple mesh size from maze size. Then, I’d do the infinitely nested maze centered on the origin.

The End Product

Well, nothing this time. I just had a relization while revisiting my previous post and it led me down a few different rabbit holes with a few different realizations.

Appendix

Visualization Troubles

Getting these visualizations to render correctly in arbitrarily large space isn’t easy. These visualizations operate under the same rough constraints that a game engine does—it’s using floating point for the display.¹³

If you’re familiar with this class of issues, the failures will be obvious.

I was testing this with my bidirectional spirals, since it’s obvious what it should look like in any given direction (just regularly spaced straight lines).

First, going out far enough, there were gaps in the lines. This is standard floating point precision stuff. Second, if I went out even farther, the browser would hang. This is another sign that it’s operating on both 32-bit and 64-bit floating point.

The reason for this is because there are a finite number of values that a finite number of bits can possibly represent. In order to represent a larger range of values, once you get big enough, it loses precision in the 1s digit. This has the unfortunate consequence that for floating point, the following can be true: x + 1 === x. This will happen sooner for 32-bit floating point than 64-bit, which was why I was seeing it hit the rendering (32-bit) before the draw loop (64-bit).

The fix for this is simple: while the function operating on the coordinates needs to know their real values, the draw loop doesn’t. It can just pretend the coordinates are all around (0, 0), and I can just add in the offset before it goes to my function.

However, you guessed it: while my spirals are mostly tolerant of floating point discrepancies, the points where x was roughly equal to y would accumulate errors at big enough numbers. My grid operates on integers, and JavaScript has a convenient mechanism for handling arbitrarily-sized integers: BigInt. It constrains the amount of operations that you can act on, but it can represent arbitrarily large numbers.¹⁴

However, the binary tree implementation uses a hashing function that uses Math.sin().¹⁵ That cannot take in a BigInt, so we need to convert it to some number. Well, $2^{32}$ should work fine, I thought, and it did, mostly.

But I was testing out big numbers, and I found that if I put in the coordinates (30000000000​000000000​000000000000​000000000000000000​0000000000000000000000000, 0), adding another zero to the end didn’t matter. It was also the case if it ended with some non-zero digits like 315 and I added a zero to the middle. This seemed wrong, but wrong in a way that didn’t feel like floating point error—that doesn’t tend to fail on adding orders of magnitude until you get to really big numbers, at which point it goes to Infinity, which this didn’t feel like.

It turns out, however, that once you get past $10^{32}$, any additional 0 will modulo to the same number, as $10^{32}$ is a multiple of $2^{32}$ (since $10^{32} = 2^{32} \cdot 5^{32}$, which is obvious when you consider that $10 = 2 \cdot 5$). Now, this wouldn’t be a problem in a maze (a period of $2^{32}$ at the top level would not be noticeable), but it is a problem with the visualization where I’d expect people to just add zeroes until it breaks. Swapping this out with a Mersenne prime, $2^{31} - 1$, removes this repetition around multiples of 10.¹⁶

With all that together, I tested to past $10^{534659}$ without any artifacting. The rendering starts to get pretty slow at around that point, but that’s due to having to perform math on values that are around 27,000 64-bit values long. This does mean that my constant time algorithms aren’t really constant, but actually around $O(\log n)$ (where $n$ is the larger coordinate). Ones that use hashing can speed up the work greatly (they’re genuinely periodic, so the values that need to be passed in are modulos of their full values), but I don’t care to do optimization for you sickos that want to paste huge numbers in there.