Infinite maze generating algorithm

Question

I searched and even visited a maze-algorithm-collecting website, but nothing satisfies the following statements I require.
To make it clear, I need an infinite maze generating algorithm that:

1. makes a perfect maze , which is to say,
   1. 2d,grid-based
   2. each square is space/wall
   3. every 2 spaces are linked and there's only one path
   4. no 2x2 square is all space/wall
2. provides an f(s,x,y), where s is used for random seed or something like this
   1. returns type of square at (x,y)
   2. for different s within 0~(32768 or something), gives different results
3. infinite (probably limited by 64-bit int though)
4. extra space (I mean in program) is allowed

Clarification:

1. meaning of infinite here: something like this

function f(s,x,y){
    // for each x,y it gives a result, so we consider it "infinite"
    return (s*x+y)%32768<30 ? "wall" : "space";
}

2. this is a finite algorithm (satisfies 1)

init:all walls
choose a square,flag it and add to list
while(list not empty)
{
    chose randomly from list
    delete from list
    if(there's a flag)
    {
        delete it
        continue
    }
    make a flag
    if(surrounding wall num≤1)
    {
        add 4 surrounding walls to list
    }
}

3. something satisfies 1 and 3
   we start from the Eller's Algorithm

it is generated row by row, and saves a set of regions

first row:all regions into a set,wall between regions(randomly)
while(not last row){
    foreach(neighbour regions){
        if(not in the same set){
            break their wall and merge the regions(randomly)
        }
    }
    foreach(region){
        break the wall below(randomly,and at least one does this)
    }
    generate next row
    for this row:{
        foreach(region){
            if(connected with above){
                merge to prev-set
            }
        }
        throw away prev-prev-set
    }
}
last row:connect all regions that are not in the same set

If we start from the centre and generate it circle by circle, it can be infinite; sadly we have rule 2.

Answer 1

The problem seems a bit overwhelming: infinitely many infinite mazes, such that we can restrict ourselves to a multitude of different bounds (say, if we wanted a roughly 1 million x 1 million square) and still have unique paths between any two spaces (and your other conditions). Let's break this down into smaller pieces.

Suppose we could construct a 7 by 7 square maze-block, and were able to make a border of walls around it, with one or two gates on this border where we wanted. Then all we'd have to do is connect these square blocks in a spiral: a central square with one gate at the top, and a counterclockwise spiral of blocks with two gates each, in the direction of the spiral:

(Each numbered box is a 7x7 maze)

---

There's two general cases:

• 'Straight' pieces, where the two gates are on opposite sides, and
• 'Corner' pieces, where the spiral turns and gates are on adjacent sides.

We want to make these pieces generic, so we can mix and match mazes and have them fit together. To do this, we'll use this template:

1. Border Rule: The bottom and left sides of each square are all walls, except in the center of each side.
2. Free space Rule: Unless required by rules 1 or 3, no walls are allowed in the top and right sides of a maze square.
3. Gate Rule: Where two mazes meet, if the meeting is part of the spiral, both center sides will be open (in other words, crossings happen in the center of the borders). Otherwise, the maze which is below or to the left of the other shall have a wall in the center of this border.

That's a lot, so let's see an example. Here we have a template for a 'straight' horizontal connector, highlighted in blue (all mazes are 7 by 7). X means wall, O means required to be open (a crossing point/open gate between two mazes). Red X's are the border from rule 1, purple X's are blocked gates from rule 3.

The center 5 by 5 of each maze is customizable. We must ensure that there are no inaccessible squares or equal 2x2 within our maze only, since the rules above guarantee this is true where mazes meet.

One possible maze to fit the above template (there are many):

For an example of a corner piece:

I've similarly drawn examples of each possible connection to make sure it's always possible: there are many possible ways to do this for each piece type (including the special center piece).

---

Now, for how to generate infinitely many infinite mazes based on a seed. Suppose you created at least 2 examples of each connection piece (there are 2 straight connectors and 4 corners), although you can just make one of each and reflect it. (Really you only need 2 different examples of one connection type.)

Given any seed binary string, e.g. 10110, let this denote our choices of which example piece to use while we make the maze spiral, counting up as in the first picture. A '0' means means use our 1st example for this connector; a '1' means we use the second. You can then repeat this/extend the binary string infinitely (10110 10110 ...). Since this is periodic, we can, using some math, figure out the piece type at any point in the sequence.

I've left out the math for the pattern of connection types: this is easy to work out for a counterclockwise spiral. Given this pattern, and a convention that the point x,y = (0,0) is the bottom left corner of the spiral-start-maze-block, you can work out 'wall or space' for arbitrary x and y. This maze is infinite: you can also restrict the borders to any full odd square of mazes in the spiral, i.e. (7*(2n+1))^2 cells for positive n.

This framework pattern for a maze is customizable, but not very difficult to solve, as the regularity means you only need to solve it locally. There's nothing special about 7; any odd number at least 7 should work equally well with the same rules, if you want to make local maze blocks larger and more complex.