Maze Algorithms (1997)

Maze Algorithms (1997)
astrolog.org

Although I guess you could have an infinitely large map and an algorithm that guaranteed connectivity. Infinite ways to fail to reach the goal. But I doubt there would be much practical benefit.

To actually answer your question it should be fairly easy to convert nearly any existing algorithm to cover an infinite area by simply tiling it. A common method to avoid boundary issues is to overlap the tiles slightly.

First, I'm not sure "perfect maze" is a good requirement - well placed loops make mazes more interesting. Second, "uniform" is a useless metric: generating all mazes with equal probability leads to the mazes being visibly uninteresting, with many short dead ends. Same goes for the other metrics.

Sean C Jackson makes some good mazes: https://www.seancjackson.com/

---

Inspired by the above, I'm in the process of creating a maze game for my kid: https://maze.tasuki.org/

So far I hand-crafted the mazes. The initial idea was to generate them, but I quickly found out that generating interesting mazes was hard. And generating interesting mazes in 2.5D with with weave and without walls is even harder.

So I'm practicing maze creation. My newer mazes are much better (and take me less time to create) than the first attempts. I think eventually I'll be able to write down the algorithm I use for maze creation.

> Infinite length Mazes: It's possible to create an infinitely long Maze (a finite number of columns by as many rows as you like) by only keeping part of the Maze in memory at a time and "scrolling" from one end to the other, discarding earlier rows while creating later rows.

> An easier way to make an infinite Maze is with Eller's or the Sidewinder algorithms, as they already make Mazes one row at time, so simply keep letting them add rows to the Maze forever.

My tiny obfuscated maze program at https://tromp.github.io/pearls.html#maze will print an infinitely long maze if you enter a negative height.