Procedurally generating a maze without 'cycles'

Question

I wanted to write an algorithm which could generate a 'maze' like structure within a closed room. [This is not a typical maze. I just want some walls here and there within the room.]

The catch is that I don't want any 'cycles'. eg:

1. I want this:-

2. I do not want this:- [Here the bot is stuck as it cant access the rest of the room]

I understand this as not having cycles in the wall structure. So I thought of one solution: Generate a wall segment and then after generation check for cycles (if there are cycles, regenerate), but that seemed tedious as I'd have to encode stuff in a graph, so I thought of another solution.

Generate a wall segment and then choose an empty cell and see if you can reach all other empty cells from that cells (if not, regenerate). This one seemed promising but I did not know where to start.

Moreover these solutions don't address the elephant in the room: to generate the walls correctly in the first place! Moreover, one can't truly talk about the time complexity of the former algorithms.

How should I proceed with this problem?

P.S: I am using doing this in Unity with C#.

Answer 1

The recursive division maze generation method does what you want. https://en.wikipedia.org/wiki/Maze_generation_algorithm#Recursive_division_method

From the pictures you posted, you want wide open 'rooms', so you will want to stop the algorithm early. Instead of "until all chambers are minimum sized" you can specify required minimum size greated than 1.

Answer 2

Generate a wall segment and then choose an empty cell and see if you can reach all other empty cells from that cells

If you still wanted to use that idea, then one way to do that is to use a flood-fill algorithm to count the reachable tiles from the start location and confirm that it is the same as the number of empty tiles in total.

This page is part of a larger tutorial that contains a more detailed description of this idea. See the “Banishing disconnected islands (a roguelike developer's greatest enemy)” section.

Answer 3

Your problem is a little different than the standard "maze generation" algorithms, because you want to allow cycles in the path, just no cycles in the walls, and I think this is an important part of the game.

So, I would solve this using a variant of Kruskal's algorithm that satisfies this requirement.

Level 1

1. Initialize a disjoint set data structure. Make a set for every cell. Whenever we fill a cell with wall, we will merge its set with the sets of all adjacent filled cells (including diagonal neighbors).
2. Fill in all the border cells and merge their sets as indicated above.
3. Make a list of all the unfilled cells
4. Repeat the following until the list of unfilled cells is empty:
5. Choose an unfilled cell from the list at random.
6. Check the sets of its 8 neighbors. If any two of them are in the same set, then filling this cell would create a wall cycle. Discard it.
7. Otherwise, fill the cell, merging its set with its filled neighbors, and go back to step 4.

When you're done, you will have a pretty dense maze -- it will be impossible to fill any empty cell without creating a wall cycle. If you want a bit more space, you can remember and undo the last fills, or you can just stop filling after a certain number of cells are filled.

Level 2

Instead of using just one list of unfilled cells, divide them into buckets based on the pattern of their neighbors -- eight neighbors filled or unfilled makes 256 possible neighbor patterns.

Then, instead of choosing from the whole bunch randomly, assign different weights to each pattern and assign cells in that bucket a different probability.

This gives you a lot of power to adjust the character of the mazes you create until you find one that's right for you. Maybe you want avoid filling cells adjacent to walls, because that makes your maze too blocky. Maybe you want to prefer filling cells that continue the end of an existing path. Maybe you want to avoid filling cells that make diagonal connections. You can play with the weights you want until you get mazes you like.

I've done a similar thing with more traditional mazes here. Try adjusting the weights.

Note that this algorithm is very fast, with or without level 2. There is no backtracking/retrying, and operations on the disjoint set structure are effectively constant time, which makes the whole thing pretty much O(n)