How to generate doorways procedurally, on the fly, and guarantee acessibility

Question

I'm currently creating a spaceship exploration game, and I have a massive problem I've been trying to solve for months, and through the rest of my group deciding to opt for a rewrite to fix some massive spaghetti.

Anyway, the problems goes as follows:

The player starts in a room, from which they can travel to some other adjacent rooms through doorways.

These doorways are stored in a map of the direction they're in, and the doorway object they reference. Each Doorway object keeps track of the two rooms it links, and will direct the player to each one when necessary.

However, all rooms need to be accessible by at least one route, and going through a doorway on the starboard side means that the other room needs to have the same doorway on the port side. I can do this by just having every wall be a door, but that gets boring to explore.

Pre-generating these proved enough of a glitchy mess for me to fail it, but now, the spec has changed. The world will be theoretically infinite, and as such, the pathing cannot be pre-generated, and instead must be done as new rooms are needed, or expected to be requested soon.

So I need to generate what is essentially a maze, with loops allowed, drawn on a grid, one square at a time, where not only is every room not directly aware the others exist, but acessible from every other. On top of this, going through a doorway on one side of a room means that the same doorway needs to be on the opposite side of the next room.

What's a good way to guarantee all these properties? I am willing to part with rooms having no knowledge of others, but would rather keep it this way for ease of re-generating a room's type later, should that become necessary.

Below is a text file ascii mockup of a 5x5 example I created https://pastebin.com/EtdAWAwD Lines are walls, Xs are doors, and the S is the player starting position.

Any advice at all is appreciated, even on alternate routes to consider for generating these.

Answer 1

There's many ways to do this - there's even a wikipedia article on it.

Googling for stuff like "Prim's Algorithm maze", "Kruskal's Algorithm maze" etc leads to a bunch of sample code and youtube videos.

For your requirement of needing something that scales to an infinite world, I think the "recursive subdivision" method would be easiest, although there are definitely visible grid alignment if the player is looking at the map. You should be able to place the gaps in the grid through some fixed deterministic hash so that you can re-generate the same maze at the same location every time.

Answer 2

When your world is supposed to grow indefinitely, then Prim's Algorithm and Kruslak's Algorithm won't help you, because they operate on a field of known size.

What you can do instead is grow your maze by starting with a single room and then keep attaching new rooms randomly to the border of the maze. You do that by picking a random room which still has free edges, generate a new room bordering that edge, and connect the two rooms with a doorway.

That will generate a maze with a tree-shaped topology with the first room as its root. When you want the maze to be able to loop, you can simply check if a newly generated room also happens to borders any other rooms than the one it was generated from, roll a random number for each, and when it's high enough you also connect to that room with another door (how much is "high enough" depends on how many loops you want).

Answer 3

You could try that:

Whenever a room needs to be generated (say, it's in some proximity r and is not yet generated) at (x,y)

1. find all doors to the 'void' in the radius R from (x,y) (it can be in any measure). If none is found then create a door connecting to (x, y)

2. generate a maze starting from any position found in 1, filling the 'void' in the whole region of radius R around (x, y) (by any algorithm that guarantees connection between any two points, so for example recursive backtracing). If at any point it would create a door to a room outside radius R create the door but don't follow it. (So you effectively generate a whole region at once, instead of single room)

3. For the doors found in 1. force the connection from both sides.

You have to choose R and the metric empirically for what you need. It could even be possible to procedurally generate a bounding polygon (which is quite easy) each time and use it as the restricting region. That way you put more irregularity into the generator.

One disadvantage of that algorithm is that the shape of the maze is dependent on the order of discovery, so it is impossible to replicate solely by the seed. But I can't think of any other algorithms achieving that that wouldn't be purely probabilistic.

I'll also leave this link https://nothings.org/gamedev/herringbone/ here, maybe it can be useful somehow.

Answer 4

The first thing is to realize it's a graph, and since it's on a grid it mean each node has at least 4 neighbor.

1. Since you have a starting position, using a tree like structures guarantee all room are always reachable. So when generating new room, it should always link to a previous room, this simple rule guarantee there is always a path to the starting point, and since all rooms are connected to the starting room there is always a path to any rooms, because that's how tree works.
2. Now you have a tree, add randomly or using clever tricks, links to another room, and you will have cycle and it stop being a tree.
3. In order to have more maze like features, nest the grid, generate an overall graph, then inside each chunks, run any generative maze algorithm such has it links all of the opening of the master node.
4. It's a game, please don't confuse the player and offer way to understood how it navigate around lol.