Are there also algorithms for (incremental) generation of infinite mazes?
> 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.
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.
I do know of an algorithm with 'nesting' that generate mazes but results in very long walls and thus does not feel random.
What do you mean by "infinity" exactly? 2^64? 2^128? Any arbitrary bigint? Periodic boundary condition?
Why perfect mazes - does that really matter? Are these supposed to be human solvable or is this some sort of abstract art? Anything human solvable requires at least one path of (very) finite length from start to finish.
Overlapping tiles and doing nothing else produces multiple paths. It's the quick and easy solution if the goal is practicality of implementation and human oriented puzzles.
If you insist on a perfect maze an obvious solution is 2^64, a periodic boundary condition, and a space partitioning tree with many children per node (ie n >>> 2). Connectivity is determined at each level. Long uniform walls can be reduced or even eliminated by warping block boundaries in various ways; among other things, you could potentially use the maze solution at each level to assign node membership for the next level.
The requirements I've come up with are:
1. Distribution of path length for any two points of a fixed taxicab distance should be some kind of long-tail distribution.
2. In general, the path between any two nearby points should often stray far outside the smallest box that contains both of those two points. Of course, this won't apply to nearby points in the same corridor. I'm not sure how best to state this formally.
3. It should be possible to calculate the exits for any cell in O(log(N)) time where N = abs(sum of the coordinates).
And the most hazy requirement of all: the maze should look decent.
AFAICT, no such algorithm exists.
Connected, sure, that's table stakes. But why is being non-cyclic a desirable property? (Other than it being the definition of "perfect maze", a term I've come to despise)