The other day, game designer/Martleteer/shaman king William Workman talked to me about a cool project he was working on involving an infinite maze. Now, I'm selling his work short here - there's a hell of a lot more to it than corridors - but naturally, my buzzing robot brain really latched onto that idea. So, let's do it - infinite mazes.

(cut to the chase here)

There's some really hip algorithms for generating mazes in a finite space. Here, go check this out. Neat, right? Now, the thorny issue here is the infinite thing. For the most part, those algorithms rely on traversing each of a finite set of nodes, but obviously, we can't do that here. It's like, say you were doing a depth-first search, but the tree had no bottom. You'd never see the end, right?

It's a shame too, because those algorithms are fairly lovely. Hm. Well, how about this - what if we break our infinite space up into chunks with finite dimensions? Even if we have an infinite number of these chunks, each chunk is, by itself, perfectly manageable. We can feed the finite chunk space into one of our maze algorithms and, in that local region, have a perfect maze. So, what do we do with the chunks? Well, we could just stitch 'em together.

Hey, this is just simple enough to work, right?

A bit of terminology then. A "chunk" is a discrete part of the maze. By itself, a chunk is a perfect maze generated by one of our finite maze algorithms.

"Chunk data" represents the essence of a chunk - namely, its position in the maze and a random seed. This seed is important - with it, a mazing-building algorithm ("builder") can perfectly reproduce a chunk.

Finally, a "cell" is the most basic building block of the maze. It is a square region in space bounded by walls which may or may not open to the cell's four adjacent neighbours. A chunk is composed of cells. If you're considering the chunk maze as a graph, the center of the cell is a node and the paths through its walls to adjacent cells are the edges.

Pictured above is a cell open to its neighbours to the north, east, and west. All pretty simple, right?

Anyway, with that established, the actual generation of the maze is pretty simple. We check if the chunks the player can see have been created. If they haven't, create them. Creating them here is pretty straightforward:

1. If no chunk data exists, create some with a new random seed.
2. Feed the chunk data to a builder which, after seeding with the chunk's seed, will spit out the actual chunk, complete with its cells.
3. Give that to a reifier which actually places walls and things in the game world.

Then, when chunks can no longer be seen by the player, remove their walls and things from the world so we don't waste memory on them. Memory being a big deal here (infinite mazes potentially taking up a buttload of memory), we don't even store the chunks themselves, just the seeds we need to recreate them.

Really, the only thing left to talk about is the connection of chunks, but, at least as I implemented it, it's not particularly interesting. All I'm doing is punching a hole right through some pair of adjacent cells in neighbouring chunks. Boom. The perfect mazes are joined into one super maze.

Okay, it's actually kind of suck. With the current implementation, you're guaranteed exactly one connection in each of the four directions into a chunk, which makes things a little too regular. However, you could mix it up a bit by having randomly having more or less walls.

Let's wrap up. I'm kind of cheating because these chunks are guaranteed to have cycles. Sucks to your mama, it's still a dang maze and not bad for a day's worth of work. What is cool about the chunk approach is that you could sort of extend it to higher levels - make each chunk a cell in a higher-order maze-of-mazes. So, thinking out loud, that's neat.

Anyway, source is here, demo is here.