Gists

Maze MapGen: Generate a world that consists of a 2D maze extending to the world's limits.

To use, create a new world and activate the mod before entering the world for the first time. Checked with 0.4.16, 0.4.17 and 5.0.0.

Screenshot:

Notes

This maze is not intended to be solvable. It is intended to give the visual impression of an "infinite maze", while keeping some degree of credibility.

The maze is a subset of a bigger, 65537x65537 nodes maze. The coordinates are truncated because the maximum size of a Minetest map is 61840x61840. Therefore, if a path from an arbitrary point A to another arbitrary point B needs to go through the area outside the 61840x61840 map, there will be no path to go from A to B.

However, due to the method of generation, I believe that within the 16385x16385 square that goes from 0 to 16384 in both directions, it's guaranteed that there's always a path from any point to any other point.

Discussion

Generating a maze is a very non-local process. Placing a wall at a certain location could divide the maze into two areas, and it's not possible to know whether it does without at least some knowledge of the structure of the rest of the already generated part of the maze.

As a consequence, standard generating methods necessarily need to keep the whole maze in memory, which of course is not feasible for a 61000x61000 maze in Minetest. Some nonstandard method is necessary.

There are very few algorithms that are suitable for generating mazes that are big in two dimensions and keep locality. The one chosen is the recursive nested maze.

The idea is as follows. A maze basically consists of taking a grid of rooms each with four walls, and removing certain walls between the rooms until you get the maze. Well, what if each room is not just an empty space, but is also a maze in itself? Since every maze allows travelling between two arbitrary points, a room and a maze are equivalent. So, instead of removing a wall of the big maze, what is removed is a passage-sized section of the outer wall of the smaller, room-sized maze, at a random location.

Applying this concept recursively, we can build a big maze out of smaller ones.

Now, the size of each sublevel can vary. I chose 2x2 rooms at all nesting levels for simplicity, because that simplifies a lot of things. There are four possible 2x2 mazes, which are the four possible rotations of a U shape.

#####    #####    #####    #####
# # #    #   #    #   #    #   #
# # #    ### #    # # #    # ###
#   #    #   #    # # #    #   #
#####    #####    #####    #####

In order to know whether to draw a wall or not at a given location, due to the non-locality of mazes, all levels of recursion need to be examined, and the algorithm is not very different from that of querying a quadtree. In this implementation, given the size of the maze, that means 14 levels of recursion. At each level, each of the four quadrants needs to be examined, and if the area being generated intersects it, it needs to be recursed into.

A complete, valid maze, except for two missing outer walls, can be generated by replacing this line:

    mazegen_recursive(-32768, -32768, 32768)

with this:

    mazegen_recursive(-16384, -16384, 16384)

The two missing outer walls aren't generated because they were going to be out of the map anyway. But it's easy to generate them. Under the "first the fixed walls" comment, add this code:

    setwall(xpos + 1, zpos + 4)
    setwall(xpos + 2, zpos + 4)
    setwall(xpos + 3, zpos + 4)
    setwall(xpos + 4, zpos + 1)
    setwall(xpos + 4, zpos + 2)
    setwall(xpos + 4, zpos + 3)
    setwall(xpos + 4, zpos + 4)

With both changes, the maze will be a valid 32768x32768 maze.

With this generation method, at the centre of the maze there will always be two walls extending one from top to bottom and one from left to right, except for exactly three holes (one in one of the walls and two in the other). It would be possible to alleviate that problem by increasing the order of the maze to something bigger than 2x2, but I havent tried to do that.