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 follows:

1. makes a perfect maze, which is to say,
   1. 2-dimensional and grid-based
   2. each grid is either space or wall
   3. every 2 spaces are linked and there's only one path
   4. no 2x2 square is all space/wall (to make it look nice)
2. can provide a function that looks like f(s, x, y), where s is used for random seed or something like this
   1. returns the type of grid 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: filled with walls
choose a grid, tag it and add it to list
while (list is not empty)
{
    choose <x> randomly from the list
    delete <x> from the list
    if (<x> is tagged)
    {
        delete <x>
        continue
    }
    tag <x>
    if(number of surrounding walls ≤ 1)
    {
        add 4 surrounding walls to list
    }
}

3. something satisfying 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

I guess I need to explain my answer in detail.

Here is the code in javascript:

// C-flavour random
let gsrand = 0
function srand(x) { gsrand = x }
function rand() {
    gsrand = (gsrand*1103515245+12345)&0xffffffff
    return gsrand>>16 & 32767
}

class Chunk{
    matrix
    constructor() {
        // suppose the map is divided into 64×64 chunks
        this.matrix = new Uint8Array(4096)
    }
}

Chunk.prototype.put = function(x, y, type) {
    this.matrix[x<<6|y] = type == 'space' ? 0 : 1
}

/* * * Core * * */
Chunk.prototype.generate__infmaze_4 = function(lx, ly, rx, ry) { // split the map recursively
    let x0 = rx - lx
    let y0 = ry - ly
    // room small enough (width = 1)
    if(x0==0 || y0==0) {
        for(let i = lx; i <= rx; i++) {
            for(let j = ly; j <= ry; j++) this.put(i, j, 'space')
        }
        return
    }
    let mx = lx+2*(rand()%(x0>>1))+1
    let my = ly+2*(rand()%(y0>>1))+1
    for(let i = lx; i <= rx; i++) this.put(i, my, 'wall')
    for(let i = ly; i <= ry; i++) this.put(mx, i, 'wall')
    // split the map into four smaller rooms
    this.generate__infmaze_4(lx, ly, mx-1, my-1)
    this.generate__infmaze_4(lx, my+1, mx-1, ry)
    this.generate__infmaze_4(mx+1, ly, rx, my-1)
    this.generate__infmaze_4(mx+1, my+1, rx, ry)
    // three exits serve as passages through rooms
    let d = rand()%4
    let myl = (my-ly+1) >> 1
    let myr = (ry-my+1) >> 1
    let mxl = (mx-lx+1) >> 1
    let mxr = (rx-mx+1) >> 1
    if(d == 0) {
        this.put(rx - 2*(rand()%mxr), my, 'space')
        this.put(mx, ly + 2*(rand()%myl), 'space')
        this.put(mx, ry - 2*(rand()%myr), 'space')
    }
    else if(d == 1) {
        this.put(lx + 2*(rand()%mxl), my, 'space')
        this.put(mx, ly + 2*(rand()%myl), 'space')
        this.put(mx, ry - 2*(rand()%myr), 'space')
    }
    else if(d == 2) {
        this.put(lx + 2*(rand()%mxl), my, 'space')
        this.put(rx - 2*(rand()%mxr), my, 'space')
        this.put(mx, ry - 2*(rand()%myr), 'space')
    }
    else {
        this.put(lx + 2*(rand()%mxl), my, 'space')
        this.put(rx - 2*(rand()%mxr), my, 'space')
        this.put(mx, ly + 2*(rand()%myl), 'space')
    }
}
Chunk.prototype.generate__infmaze = function(x, y) {
    // chunks are isolated at first
    for(let i = 0; i < 64; i++) {
        this.put(i, 0, 'wall')
        this.put(0, i, 'wall')
    }
    // use the seed
    srand((x<<15 + y) ^ seed<<3)
    this.generate__infmaze_4(1, 1, 63, 63)
    // break the isolation between chunks
    let r1 = rand()%32
    this.put(2*(rand()%32) + 1, 0, 'space')
    this.put(0, 2*(rand()%32) + 1, 'space')
}

If you want to fit in the rules, simply let the s (in f(s, x, y)) be the seed used in srand and cache the data generated by new Chunk().generate__infmaze.

If you have noticed that this doesn't fit rule 1.3, you will also find it easy to fix it (change the break-the-isolation-between-chunks part, only that it may not look nice :).

Demo (seed = 0, (0, 0) ⇒ (63, 63)):

#############################.##################################
#.................................#.............................
#######.#########################################.##############
#...........#...#.#.#.........#.#.#.......................#.#.#.
###.#####.#.#.#.#.#.###.#####.#.#.#.#####################.#.#.#.
#.......#.#.#.#...#.#.#.#.#...#.#.#.#...#.......#.#.......#.#.#.
#####.###.###.#.#.#.#.#.#.###.#.#.#.#.###.###.###.#####.###.#.#.
#.#.#.#.#.#...#.#.#.....#.#.#.#.#.#.#.....#...............#.#...
#.#.#.#.#.#.###.#.#.###.#.#.#.#.#.#.#.#.#.###.#####.#######.#.#.
#.#.#.#.#.#.#.#.#...#...#...#...#.#.#.#.#.#.......#.........#.#.
#.#.#.#.#.#.#.#.#.#.#.###.#.#.#.#.#.###########.###########.#.#.
#.#.#.#.#...#...#.#.#...#.#...#.#.#.#...................#.#.#.#.
#.#.#.#.#.#.###.#.#.#########.#.#.#.#.#.#.#####.#######.#.#.#.#.
#.#...#.#.#.#...#.#.....#.....#.#.#.#.#.#.#...........#.#.#.#.#.
#.#.#.#.#.#.#####.#########.###.#.#.#.#.#.###.###########.#.#.#.
#...#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#...#...#.....#.#.#.#.
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#####.#.###.#.###.#.#.#.#.
#.#.#.#.#.#.#.#...#.#.#...#.#.#.#.#.#.#...#.#.........#.#.#.#.#.
#.#.#.#.#.#.#.#.#.#.#.#.###.#.#.#.#.#.#.#.#.###########.#.#.#.#.
#.#.#...#.#.#.#.#.#.#.#...#...#.#.#.#.#.#.#.#.............#.#.#.
#####.###.#.#.#.###.#.###.#.###.#.#.#.#.#.#####.#########.#.#.#.
#...#.#.#.#.#...#.#...#.......#.#...#...#.#.............#.#.#.#.
#.###.#.#.#.#.#.#.#.#.#.#####.#.#.#########################.#.#.
#.......#.#.#.#...#.#.#...#...#.#.#.......................#.#.#.
#.#.#.###.#.#.#.#####.#######.#.#.#######################.#.#.#.
#.#.#...#.#.#.#...#...........#.#.#...........................#.
#########.###################.#.#.###########################.##
#.......#.#.#.......#.........#.#.#.#...............#.....#.#.#.
#.#####.#.#.#.#.#######.#######.#.#.#.###############.#####.#.#.
#.#...#.#...#.#.#...#.#.#.....#.#.#.#.........#.....#.....#.....
#.#.#.#.#.#.#.#.###.#.#.#.#####.#.#.###.#########.#######.#.#.#.
#...#.#.#.#.#.#.#.#.#.........#.#.#.#.........#.....#.......#.#.
###.###.#.#.#.#.#.#.#.#.#######.#.#.###.#######.#####.#####.#.#.
#.....#.#.#.#.#.#.#.#.#.......#.#.#.................#.....#.#.#.
###.#.#.#.#.#.#.#.#.#.#.#.###.#.#.#############.#######.#####.#.
..#.#.#.#.#.#.#.#...#.#.#.#...#.#.#...#.#.#...#...#.#.....#.#.#.
#.#.#.#.#.#.#.#.###.#.#.#.#.###.#.#.#.#.#.###.#.#.#.#####.#.#.#.
#...#.#.#.#.#.#.....#.#.#.#...#.#.#.#.#.#...#...#.#.#...#.#.#.#.
#.#.#.#.#.#.#######.#########.#.#.#.#.#.#.#.#.#.#.#.#.###.#.#.#.
#.#.#.#.#.#.#.#...#.#...#.#...#.#.#.#...#.#...#.#.#.#.#.#.#.#.#.
#.###.#.#.#.#.#.#.#.###.#.#.#.#.#.#.#.###.#.#.#.#.#.#.#.#.#.#.#.
#...#.#.#.#.#.#.#.#.#...#.#.#.#.#.#.#.....#.#.#.#.#.#...#...#.#.
#######.###.#.#.#.#.#.###.#.#.#.#.#.#.#.#.#####.#.#.#.#.#.#.#.#.
#...#.#.#.#.#...#...#.....#.#.#.#.#.#.#.#.....#.#.#.#.#.#.#.#.#.
#.#.#.#.#.#.#.#.###.#.#.#.#.#.#.#.###.###.###.#.#.#.#.#.#.#.#.#.
#.#.#...#.#.#.#.#.#.#.#.#.#.#.#.#.#.#...#.#...#.#.#.#.#.#.#.#.#.
#.#.#.#.#.#.#.#.#.#.###.#####.#.#.#.#.#.###.#####.#.#.#.#.#.#.#.
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.....#.#.#.#.#...#.#.#.
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.###.###.#.#.#.#######.#.
#.#.#.#.#.#.#.#.#...#.#.#.#...#.#.#.#.#.#.#.#.#.#...#.#.#.#.#.#.
#.###.#.#.#.#####.###.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
#...#.#.#.#.#...#.....#.#.#.#.#.#.#.#.#.#.......#.#.#.#.#.#.#.#.
###.#.#.#.#.#.#.###.#.#.#.#.#.#.#.#.#.#.###########.#.#.#.#.#.#.
#.#.#.#.#.#.#.#.#.#.#.......#.#.#.#...#.#...............#.#.#.#.
#.#.#.#.#.#.#.###.#.###.#.#.#.#.#.###############.###.#.#.#.#.#.
#.....#.....#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.....#...#.#.#...#.#.#.
#######.#.###.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#######.#.#####.#.#.#.
#.....#.#.#.#.#.#.#.#...#.#.#.#...#.#.#...........#.#...#...#.#.
###.###.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#########.#.#.#.#.#.#.
#.......#...#.......#.#.#.#.#.#.#.#.#...#...#.......#.#...#.#.#.
#.#################################.#.###.#.#####.#.#.#.#.#.#.#.
#...............................#.#.#...#.#.#.....#.#.#.#.#.#.#.
###########################.###.#.#.#.#####.#.#####.#.#.#.#.#.#.
#.............................#...#.....#.........#.#.#.#.#.#.#.

Answer 2

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.