So, I'm Jake, and I am working with Harry on the aforementioned game, and have been designing the infinite maze generation, which seems like a good topic for a devlog post.

Infinite mazes

So, since we can't generate the entire maze at once (duh!), we need to split the maze into patches, and generate a bunch of them around the player wherever they happen to be. This is not unlike how minecraft handles world generation with chunks.

Seeding

It would be nice if the maze was generated the same if we travel away from a given patch and back again. To accomplish this we can set the seed of the random number generator based on the x,y of the patch and a number we set at the start of the game (commonly refereed to as the "seed" for the map), giving us a fixed maze that is different each time we load up the game, sweet! I'm using the RandomXS128 random number generator included in LibGDX, the state of which is held in two numbers, so

rng.setState(seed + x, seed + y);

seems like the natural thing to do. However as you move though the maze vertically or horizontally, only one of the numbers is changing, and the other by not very much, and the maze is not very random at all. It turns out

rng.setSeed(seed + (x << 16) + y);

is much better. The y coordinate is still not varying the seed by much, but we are only after the illusion of randomness, and after some testing, it seems ok. We will leave a comment for future us in case it becomes a problem.

Patch boundaries

Ok, we have our random number generator ready to go, now we just have to generate a patch from it. But we can't just go making patches willy-nilly, the patches actually have to join up into a coherent maze. So lets generate the boundary, and lets do it simply:

public int[] createPatchBoundary(int x, int y) {
    int nCells = Patch.PATCH_HEIGHT + Patch.PATCH_WIDTH - 1;
    int[] bound = new int[nCells];
    setRandomState(x, y);
    for (int i = 0; i < nCells; ++i) {
        if (rng.nextFloat() <= boundaryPathChance) {
            bound[i] = PATH;
        } else {
            bound[i] = WALL;
        }
    }
    return bound;
}

createPatchBoundary generates an array of cells that will form the left and bottom edges of our patches. We run this for our current patch and the ones above and to the right (and above and to the right) to fill in the border of our patch. boundaryPathChance is exactly what it sounds like, the chance of a given cell on the boundary to be a path. Which gives us a nice dial to fiddle with later for balancing. 0.5 seems like a good choice for the time being.

Patch centre

The juice of the problem, as it were. I tried a few different approaches, both on pen and paper and in code, and this is what I settled with. It definitely could be improved, but it seems to work for the purposes of the game. First we ignore the boundaries, and generate a perfect maze in the central section. (A perfect maze is one that has no loops). There are loads of ways to do this, but I chose the growing tree algorithm, because it's pretty simple to implement, and offer a certain amount of flexibility.

Fixing it up

So now we have something like this (for a 10x10 patch size, "." is a path, "X" is a wall):

X.....X.XXX
..XX.X.X...
X.X..X.X.X.
X.XX...X.X.
.....X.....
.XXXXXX.XXX
X.........X
X.XXXXX.X.X
X.X.....X..
X.XX.X.XX.X
..XX..X.X.X

Which is actually very serviceable as a maze. However, as you move though a field of similar patches, the maze is very open (at least on this patch size), and not really very challenging to navigate. We need to block off some paths. First let use label each path, to note which boundary it belongs (note "." now represents a wall, to make the numbers clearer):

.44444.4...
15..5.5.552
.5.55.5.5.2
.5..555.5.2
15555.55552
1......5...
.555555555.
.5.....5.5.
.5.55555.52
.5..5.5..5.
13..33.3.3.

Numbers 1-4 are the sides, and 5 is the centre (if you couldn't work that out on your own). Now we iterate over all the cells, and for any "5" cells, we note which numbers it is adjacent to, making lists of each combination of adjacencies. Then, block of all but one from the lists for "4" and for "2". This means that the centre maze is still connected to those sides, but at only one point. The reason we don't do the same for "1" and "3" is that the patches to the left and down will be doing the same, and it is a bit to restrictive to block off from both sides.

After doing so, we end up with something like:

.44444.4...
15..5.5.5.2
.5.55.5.5.2
.5..555.5.2
15555.555.2
1......5...
.555555555.
.5.....5.5.
.5.55555.52
.5..5.5..5.
13..33.3.3.

We lost 2 connections to the "2" side and 1 connection to the "4" side. Note that the top left "5" survived as it is connected to the "1" side as well. This is an arbitrary choice, but doing so lets us keep connectivity up. Note that although we are connected to all 4 sides, this doesn't guarantee connectivity between patches. If the patch below decided the only connection it wanted to keep to use was in the 8th column, we wouldn't be connected to them at all. This isn't necessarily a bad thing, we do want some dead ends and roundabout routes bigger than a single patch, but we would like a dial to play with to go between this, and what we had before we started blocking things off. So we end up with something like:

while (connectionList.size() > 1) {
   if (rng.nextFloat() <= blockChance) {
      int index = rng.nextInt(connectionList.size());
      Point choice = connectionList.get(index);
      patch[choice.x][choice.y] = WALL;
      connectionList.remove(choice);
   } else {
      break;
   }
}

We can control the degree to which blockages are placed with the blockChance variable. 1.0 gives us full blocking (down to one connection), 0.0 gives us the unblocked behaviour.

On patch size

Generally larger patch size results in better quality mazes, as more of the maze is generated as a "perfect" maze, however if blockChance is left at 1.0, the connections to the boundary are going to get further apart, and less likely to actually connect the two patches. To combat this, a similar approach to the blocking method can be taking to introduce more connections. By looping over cells, looking for wall cells that are neighboured by a "5" and one of the boundaries, and grouping these points by boundary, single paths can be placed that create more connections from patch to patch. Assigning a probability to this gives another dial to play with in order to fine tune the resulting maze.

Final Thoughts

The algorithm outlined above still has the chance of screwing over the player. If you are really unlucky you could get boxed in the first patch (1 in ~70 billion on a 10x10 patch). After some play testing, it seems plenty good enough for what we want it for, however, here are some ideas on how to improve the alogrithm:

- Guarantee n paths on a boundary

- Generate a perfect maze on the patch level, in order to decide which boundaries to connect and block off

- Do a path-finding along the walls to connect boundaries to the centre further than one cell away.