I (like so many others here) am working on some procGen maps.
I stumbled upon this example: https://paginas.fe.up.pt/~ei12085/misc/dungeon-generator/?w=64&h=24&mazeType=random&roomAttempts=100&roomMinSize=1&roomMaxSize=5&connectiveness=0.02

Now, I understand the majority of the algorithm (or at least can replicate the effects)... but the last step is where I was hoping for some help.

As the demo shows, it selects placement for some rooms, then builds a maze around it.
Then using a connectiveness value it cleans up the majority of the maze, leaving only a few laborinthesc hallways.

I was trying to come up with a similiar algorithm, but i don't think my idea is as efficent as the method the demo uses.

My Idea was to label each room with a unique RoomId, then the maze path would not have a roomIds. Then I would iterate marking any square without a roomId with the roomId of an adjacent cell. If there are multiple adjacent RoomIds then:
If the RoomIds are distinct-> Do nothing (Indicates the hall connects to a different room)
If the RoomIds are the same, randomly choose to remove one of the halls or not.
If the choice is made to remove a hall randomly choose one of the halls to remove.

But I don't think the demo uses that algorithm... the algorithm used looks to be O(n) as cells in the top left are trimmed before cells in the bottom right regardless of room proximity and etc...

Just to clarify, are you trying to implement the same algorithm used by the demo? Or are you trying to implement a slightly modified variation? Because the demo you posted has a link to the article upon which it is based, which itself contains a link to the code used by the demo and the author's game.

@Waterlimon: My current algorithm creates a map where every cell that is open is accessible.

@Zipster: I am not trying to use the alg used by the demo, the article linked points to a different (very similiar generator). The algorithm I am using works much differently in the room placement step, but the part I want emulate is where it takes the maze that fully fills non-room area and trims many branches such that the resulting maze still has all rooms connected, but not every bit of open space is filled with maze corridors.


I think the issue is that my maze paths Through the rooms, where the one in the demo doesn't connect the rooms to the maze until the next step... but once that is done, the last step is simple trimming dead ends? (Pathing through rooms leaves no dead ends)

Filling in dead-ends is fairly straightforward, since dead-end cells are well-defined -- any open cell that is surrounded by walls on exactly three sides is a dead-end.

There are multiple ways to do this. The first, and easiest to implement, is to iterate every cell on the map and fill in those that match the dead-end criteria. Repeat this over multiple passes until no more cells are filled in, and you're done. Optionally, if you want to keep a few dead-ends for variety's sake, you can define a max number of passes so that not all dead-ends are removed.

The second approach uses pathfinding techniques and is closer to what you see in the demo. Iterate the map as before, but once you find and fill in a dead-end cell, look to see if there are any adjacent dead-end cells. If there are, fill those in too, and repeat the process on all those cells. You're essentially flood-filling dead-end cells with walls. Again, you can define a threshold value past which to stop filling if you want to leave some dead-ends.

any open cell that is surrounded by walls on exactly three sides is a dead-end.

True enough, but that doesn't catch cases where larger segments are are inaccessible.

Some areas may connect only to each other but be disconnected from the rest of the maze. A direct flood fill Waterlimon suggested is still likely the easiest solution. There are likely more mathematically-based graph algorithms to find segments that are not connected together, but a flood fill is easy to describe, to implement, and adequate for the solution.

Another option is to have objects in the game that can cut through walls: pickaxes, wands of digging, or whatever. Then the rooms are bonus areas. :-)

True enough, but that doesn't catch cases where larger segments are are inaccessible.

It was my understanding that the OP already had a map where all areas were accessible to all other areas, as per their response to Waterlimon, and that they just wanted to prune excess hallways. However I concede that I could be misinterpreting their reply, and that "accessible" means something else to them.