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.

Subterfuge

Welcome to stackoverflow.com. Please take some time to read the help pages, especially the sections named "What topics can I ask about here?" and "What types of questions should I avoid asking?". Also please take the tour and read about How to Ask good questions. Lastly please read this question checklist. – Lightfooted

hi, i read "What types of questions should I avoid asking?" and it's not on the list ,and it is related to algorithms, and i do see similar questions here,you know.and i did search and did summerize – Subterfuge

perhaps you can point out the problem? – Subterfuge

Stack Overflow isn't a code or algorithm writing service. Show us what you've tried, tell us the problems you have (preferably asked as a set of small, narrow and specific questions, and not one single broad one). And if this is for game development you might have more luck on the Gamedev Stack Exchange site. – Lightfooted

By infinite do you mean arbitrary dimensions (within 64-bit) or literally infinite? – Crinoid

@Internal Server Error arbitrary dimensions (within 64-bit) – Subterfuge

"Show us what you've tried, tell us the problems you have" I've shown that I searched, I wrote some algorithms but they make no progress.by the way this problem cannot be divided,i'm sorry – Subterfuge

You need to better define what you mean by "Infinite" here. Give us an example of what you mean by an algorithm that say, just generates an infinite array of random squares. – Arella

@Arella added – Subterfuge

I'd look into fractal space-filling curves for inspiration. – Titan

I believe that I can fulfill three and a half of the four conditions under section one. Condition 1.4 is a quite hard though, especially if diagonal 2x2 blocks are disallowed as well (which assume they are). – Arella

@Arella I think 2.2 is way harder. – Elinaelinor

@Elinaelinor I believe that I can do that one. I wasn’t really counting that as a constraint so much as a functional description. Either way, I think that I can do everything except the “no all-wall 2x2 cells”. – Arella

with some effort, 1 and 3 can be completed(i will edit later) , and the hard part is 2 by the way “no all-2x2 cells" is quite common for mazes – Subterfuge

How 'hard' should this maze be? Would you settle for blocks of '7 by 7' square mini-mazes connected in an infinite spiral, if it satisfied all of your other conditions? – Hannibal

@Hannibal "How hard should this maze be?":this isn't for solving, and it's infinite, though. "Would you settle for blocks of '7 by 7' square mini-mazes connected in an infinite spiral, if it satisfied all of your other conditions?" i do accept this kind and has thought about it, but it's hard to "connect", you know – Subterfuge

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

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

Subterfuge

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.

Hannibal

looks nice, i'm going to write the code later and then "accept" and vote up – Subterfuge

i improved the algorithm so that the inside of the maze-block can be generated randomly with the seed – Subterfuge

@Subterfuge That's excellent, did you use one of the other maze algorithms to generate the inside? It might be worth posting your code as its own answer. – Hannibal

well,it's quite simple, note that a finite perfect-maze(without whole-wall edge) has spaces in specific places on the edge – Subterfuge

well, i used a 4-chunk-breaking algorithm in the inside, probobly not in that link though – Subterfuge