Maze Generation

In limlib there exists a system for handling and generating mazes.

MazeGenerator

To place a maze in your world you want to give your chunk generator a MazeGenerator which can have a generic maze type MazeGenerator<MazeComponent> if you aren't doing anything special.

public class LevelZeroChunkGenerator extends LiminalChunkGenerator {

	public static final Codec<LevelZeroChunkGenerator> CODEC = RecordCodecBuilder.create((instance) -> {
		return instance.group(BiomeSource.CODEC.fieldOf("biome_source").stable().forGetter((chunkGenerator) -> {
			return chunkGenerator.populationSource;
		}), Codec.INT.fieldOf("width").stable().forGetter((chunkGenerator) -> {
			return chunkGenerator.mazeGenerator.width;
		}), Codec.INT.fieldOf("height").stable().forGetter((chunkGenerator) -> {
			return chunkGenerator.mazeGenerator.height;
		})).apply(instance, instance.stable(LevelZeroChunkGenerator::new));
	});

	MazeGenerator<MazeComponent> mazeGenerator;

	public LevelZeroChunkGenerator(BiomeSource biomeSource, int width, int height) {
		super(biomeSource);
		this.mazeGenerator = new MazeGenerator<MazeComponent>(width, height, /* Cell X Thickness */ 8, /* Cell Y Thickness */ 8, /* Seed Modifier */ 0);
	}

}

Typically you would have a fixed Cell thickness, you would need one if you'd be using nbt files to generate the maze. So in the constructor of the MazeGenerator it's wise to have that be separate from the codec. The actual size of the maze however can usually be left to the codec.

The Seed Modifier is a number to adjust the seed of the maze if you have multiple mazes in a single chunk generator.

To generate it in the world, simply call the generateMaze function. You will also need to define two methods, for making a new maze, and decorating a cell.

@Override
public CompletableFuture<Chunk> populateNoise(ChunkRegion region, ChunkStatus targetStatus, Executor executor, ServerWorld world, ChunkGenerator generator, StructureTemplateManager structureTemplateManager, ServerLightingProvider lightingProvider, Function<Chunk, CompletableFuture<Either<Chunk, ChunkHolder.Unloaded>>> fullChunkConverter, List<Chunk> chunks, Chunk chunk) {
	this.mazeGenerator.generateMaze(new Vec2i(chunk.getPos().getStartPos()), chunkRegion, this::newMaze, this::decorateCell);
	return CompletableFuture.completedFuture(chunk);
}

public MazeComponent newMaze(ChunkRegion region, Vec2i mazePos, int width, int height, RandomGenerator random) {
	DepthFirstMaze maze = new DepthFirstMaze(width, height, random);
	maze.generateMaze();
	return maze;
}

public void decorateCell(ChunkRegion region, Vec2i pos, Vec2i mazePos, MazeComponent maze, CellState state, Vec2i thickness, RandomGenerator random) {
	Pair<MazePiece, Manipulation> piece = MazePiece.getFromCell(state, random);

	if (piece.getFirst() != MazePiece.E) {
		generateNbt(region, pos.toBlock(), this.nbtGroup.pick(piece.getFirst().getAsLetter(), random), piece.getSecond());
	}
}

Like the names suggest, newMaze creates a maze, and runs whatever maze algorithm it wants to use. decorateCell is run on every cell in the maze and is responsible for putting the blocks into the world.

Keep in mind all the code above is pseudo-code and is there to just give you an idea of what you need to do.

MazeComponent

Now for the actual algorithms used in creating a maze, everything stems from a MazeComponent. A MazeComponent has an array of CellStates corresponding to the actual maze. To create your own MazeComponent simply extend it and override the create method. In there you can run your algorithm, whatever it may be.

Limlib has a handful of builtin maze generators.

DepthFirstMaze

The DepthFirstMaze generates a maze using the depth first search algorithm.

DepthFirstMazeSolver

Similarly to the DepthFirstMaze, the DepthFirstMazeSolver uses the depth first search algorithm to 'solve' the maze at a number of starting positions to find an ending position.

DilateMaze

The DilateMaze algorithm simply takes in a maze and expands it according to some dilation. Even if your maze going in has no empty cells, the dilated maze will always have empty cells from the dilation.

CombineMaze

The CombineMaze algorithm takes in a list of other mazes and stitches them together into one single maze.

MazePiece

To help with generation, MazePiece is an enum representing the directions a certain maze cell has. To choose a random MazePiece with a random Manipulation, you can call MazePiece#getFromCell which takes in a CellState and a RandomGenerator. It is important to note, that the manipulations in this method assume that the base case, ie Manipulation.NONE, have specific directions according to their state.

The T piece is assumed to go up, left, down, right.

The F piece is assumed to go up, left, down.

The L piece is assumed to go up, left.

The I piece is assumed to go up, down.

The N piece is assumed to go up.

And of course E is empty.