If you have to create the maze:
- Without boundaries
- Generated uniformly
- Generated from a seed
It is unfortunately impossible without risking an endless loop, but most times it is good enough to create a really large maze.
Daedalus has lots of features and implements all the algorithms on this page.
To generate a really big maze in Daedalus, start the program -> press File -> run script -> Worlds largest maze -> click Ok -> press i.
From Daedalus features: (beware the rabbit hole)
World's Largest Maze: This script has the option to use different algorithms to generate the parts of the Maze being viewed, which are nested cell fractal, binary tree, recursive division, unicursal Labyrinth, classical Labyrinth, and Hilbert curve Labyrinth.
Mazes created here are enormous, and measure at least a billion passages on each side. Visiting one cell per second, it would take over 31 years just to walk from one side of the Maze to the opposite side, and that’s assuming no walls are in your way. Wall following to actually solve the Maze will take on average 31 billion years
Wall following a maze this large on a regular computer, would take over 100 years. Exceeding the lifetime of a person, I would say this is "big enough".
Nested Fractal: This creates a fractal Maze, which is composed of smaller Mazes connected together. Each cell of an outer Maze contains an inner Maze nested inside of it, where this Maze nesting process can be repeated multiple times.
Consider a 10^9 by 10^9 passage Maze, or a 10x10 Maze nested with 9 levels total. If we want at least a 100x100 section around us, we only need to create the 100x100 passage submaze at the lowest level, and the seven 10x10 Mazes it's nested within, to know exactly where the walls lie within a 100x100 section. To ensure the Maze remains consistent and never changes as you move around, have a formula to determine a random number seed for each coordinate at each nesting level.
The nested fractal maze has an obvious texture, where you can see the maze is split up into "blocks"
This is the closest i have come to an infinite maze, and it should be possible to extend this by adding randomization to the edges of the lowest level to break the "blocky" texture.
From Daedalus features:
Binary Tree: The algorithm creates Mazes with the special property that each cell has a passage that leads either up or left, but never both or neither. This creates a biased texture, where one can always easily travel diagonally up and to the left without hitting barriers or having to make choices. Moving down and to the right is when the Maze becomes a challenge, so the Maze is hard to solve but easy to solve backwards. The Maze forms a binary tree, with the upper left corner the root, where each node or cell has one or two children, and one unique parent which is the cell above or to the left of it.
Recursive Division: The algorithm creates a Maze by adding walls, where the area within the Maze is divided by a randomly positioned horizontal or vertical wall with a passage opening within it. Each subarea is then recursively divided with more walls until all areas are filled.
Every time we subdivide, we only have to subdivide the part of the maze we are in.
The images are from World's Largest Maze in Daedalus, (the subjectively best) open-source maze generation program, written in C++, and it even has its own scripting language. If you want a more detailed explanation of the algorithms, you can also check out the source code. The images above are colored based on the distance you have to walk to another cell. Black cells can't be reached without exiting the viewport.
