Maze + Dungeon map generation

[seiyria]

Is there a map generation algorithm that supports rooms of a given size in a maze, while still having a fully-connected maze?

--- Want to back this issue? **[Post a bounty on it!](https://www.bountysource.com/issues/26471234-maze-dungeon-map-generation?utm_campaign=plugin&utm_content=tracker%2F297828&utm_medium=issues&utm_source=github)** We accept bounties via [Bountysource](https://www.bountysource.com/?utm_campaign=plugin&utm_content=tracker%2F297828&utm_medium=issues&utm_source=github).

[ondras]

No.

But all dungeon generation algos -- Digger, Uniform and Rogue -- will always connect all rooms together, so every room shall be reachable. (Sometimes, multiple paths from A to B will be available -- uniqueness of such path is specific to the Maze family of algorithms.)

[seiyria]

Sure, so then I have a request: Would it be reasonable to implement a dungeon algorithm that first generates rooms, then generates a maze around it? I'd normally just generate a maze, then dig out rooms, but I fear that might not leave all paths connected properly.

[jreel]

Have either of you seen this?: http://journal.stuffwithstuff.com/2014/12/21/rooms-and-mazes/ It seems like it may be exactly (or close to) what you're after.

[seiyria]

Hey, that looks really familiar. That's actually exactly what I mean.

[ondras]

Have either of you seen this?: http://journal.stuffwithstuff.com/2014/12/21/rooms-and-mazes/ It seems like it may be exactly (or close to) what you're after.

Nice one!

One the other hand: is there any conceptual difference between this algorithm and rot.js's Digger/Uniform variants? The one mentioned above does not generate a perfect maze; its rooms might be connected with more than one route.

@seiyria, what features and qualities do you require from the generated dungeon? Could you be more specific, especially when considering and comparing what our currently available methods do?

[seiyria]

Sure. You're right, it's not a perfect maze. I may have misspoke when I meant that. What I mean is a map that all of the tiles are occupied (much like in a perfect maze), but instead of paths, some areas have bigger rooms (like that link above).

Digger/Uniform currently only occupy the space they need to to create coherence (ie, paths to connect the rooms, and in most cases, not much else). This particular variant would, in addition to the rooms, would occupy all of the available space.

Currently, the DividedMaze generator seems very close (in appearance), but it appears to have a focus on corridors instead of rooms, such that there are very few rooms, but many corridors. This would essentially be the inverse of that -- focus on generating rooms, and using all of the remaining space to generate paths.

I can't seem to pass any options to DividedMaze (likely due to the algorithm behind it), but if I could, I would want to pass similar options as I do to Digger - room widths, heights, and the number of rooms to generate as well.

One thing that I would like to also be able to specify is the number of rooms generated, and be able to also make a perfect maze. My use cases for each are as follows:

• Number of rooms generated would allow me to further specify the detail in the world I have. In my game, users will get some level of control over the dungeon generation, so being able to say "I want 4 rooms" and "I want 10 rooms" is a great help. Obviously, there are situations in which you might request more rooms than are possible to fit, in which case it would have to just fit as many as it can, then abort, possibly allowing me to know somehow (via an optional ROT.Map.DebugFlag or some-such) that it went too high, so if it consistently goes over, I would be able to tune variables more adequately.
• Ability to specify a perfect maze AND number of rooms would be very good from the standpoint of, say, making a minotaur maze. I make two rooms, and you have to absolutely traverse the whole maze to get from one side to the other, all while avoiding a minotaur. In this case, it would also help to know the "start" and "end" of the maze, in case there are other rooms generated along the way (rest stops, treasure rooms, whatever), but only so I know to say "you started here, the stairs up are here" and" this is the final room, you made it to the end, the stairs down are here." Knowing where the start and the end are is an inconsequential detail though, I ultimately don't mind just randomly choosing rooms, it would just be nice.
• At some point, I plan to make hybrid maps (ie, half of the map is a maze, half of it is a town [a custom ROT.Map.Arena]), so being able to have a perfect maze with just one room (ie, the end), would be great. This might be a perfect maze, or might be an imperfect maze, depending on the circumstances).

Does that make sense?

[ondras]

Hi @seiyria,

thanks for your detailed explanation!

I understrand most of your requirements. They make perfect sense, although the implementation is almost certainly going to be pretty complex and time-consuming. I am willing to give it a shot, but I really cannot give any time estimates. Also, I am not sure if it is possible to fit all your requirements into a single map generation algo; perhaps a multiple implementations will have to be used.

I can't seem to pass any options to DividedMaze (likely due to the algorithm behind it), but if I could, I would want to pass similar options as I do to Digger - room widths, heights, and the number of rooms to generate as well.

Perhaps we can start by adding some more customization to this algorithm. DividedMaze does not understand any concept of rooms (it just builds wall dividing the initially empty area), but I am sure some tuning can be made.

Ability to specify a perfect maze AND number of rooms would be very good from the standpoint of, say, making a minotaur maze. I make two rooms, and you have to absolutely traverse the whole maze to get from one side to the other, all while avoiding a minotaur.

A perfect maze only guarantees one path connecting any two points. This path is by no means required to pass through every single cell in the maze. Quite the contrary -- perfect mazes are trees (topologically speaking), so when travelling from A to B, you (can) evade most of the other paths.

At some point, I plan to make hybrid maps (ie, half of the map is a maze, half of it is a town [a custom ROT.Map.Arena]), so being able to have a perfect maze with just one room (ie, the end), would be great. This might be a perfect maze, or might be an imperfect maze, depending on the circumstances).

I used a hybrid map for the very first level of my game The Royal Wedding. The algorithm works by first loading a map template (https://github.com/ondras/trw/blob/master/levels/forest.txt), creating a (small) EllerMaze map (https://github.com/ondras/trw/blob/master/levels/forest.js) and inserting it into the relevant subarea. Connections are made by digging corner-ish tiles (those next to labels "A" and "B" in the template), because the EllerMaze always results in empty corner-minus-one cells.

[seiyria]

Yeah, I had no expectation that any of these would be simple or fast changes, but I think having these options would improve the library as a whole as well as make it easier for users to do complex things. No need to estimate, I totally get that it's not easy, haha. I definitely don't expect all of these in a single algorithm and, in fact, I think it would be better to split it across multiple.

DividedMaze

Yeah, I figured this was how the algorithm works. I remember doing something similar a long while ago. If this could be made to understand rooms, that would help.

Perfect maze

Gotcha. Seems I still didn't get what it was, but I think I do now, haha. I still think my idea would be fine though, and I'd still do it.

The Royal Wedding

This is super cool, although I'm not sure how feasible it is for me to do this with how I have everything set up. I'll probably try to algorithmically generate the halves and stitch them together. Also, I was trying to look at the docs for EllerMaze and the explanation link is currently a 404, but based on the output I see what you mean.

Thanks again! I'm honestly still working out a proof of concept for my game so these advanced sort of things have only crossed my mind, I don't have the time to actually implement it yet.

[ondras]

Also, I was trying to look at the docs for EllerMaze and the explanation link is currently a 404, but based on the output I see what you mean.

Ah, thanks for letting me know. I adjusted the link to http://www.neocomputer.org/projects/eller.html -- this page also describes the algo.

[CelticMinstrel]

Maybe it's possible to add some option to the DividedMaze algorithm that limits the number of times the space is divided? I didn't see any obvious way to do it from code-reading though.

[ondras]

Sounds like an iteration limit to put into the main loop at

ROT.Map.DividedMaze.prototype._process = function() {
    while (this._stack.length) {
        var room = this._stack.shift(); /* [left, top, right, bottom] */
        this._partitionRoom(room);
    }
}

?

[CelticMinstrel]

Oh, yeah, that does look like a good place.

[john-science]

I wrote a maze-generating algorithm in Python that will create perfect mazes from a starting map that includes an arbitrary number of rooms of arbitrary shapes. https://github.com/theJollySin/mazelib/blob/master/docs/MAZE_GEN_ALGOS.md#dungeon-rooms

It is based on the classic hunt-and-kill maze-generating algorithm.

I could translate the algorithm to JavaScript and pull-request it into ROT, if there is interest.

[ondras]

Hi @theJollySin,

a PR would be nice :) Although I am not sure what is the difference between rooms and grid optional arguments. Also please keep in mind that rot.js's API for map generation is somehow non-standard with respect to the callback-based passing of computed values.

I really like your list of (python) algos; it would be great if you can enrich the page with screenshots/animations of resulting mazes...

[airstruck]

Probably a little late, but Digger can generate a pretty good maze-with-rooms with some minor tweaks.

1. Mark corridor walls as "expandable" (low-priority). Essentially build corridors as if they're narrow rooms with only two long walls.

2. When clearing high-priority walls after adding a feature to a corridor, downgrade them to regular-priority walls instead of removing their expandability altogether (optional).

3. Don't allow corridors or rooms to be tunneled back into. Simplest way is not allowing digging into expandable walls (if you want a perfect maze).

By "expandable" walls, I mean the locations stored in this._walls.

Digger could probably be tweaked a little and given some options to have it do this and other interesting things without making too much of a mess. Need some minor changes to corridor also.

[ondras]

Digger could probably be tweaked a little and given some options to have it do this and other interesting things without making too much of a mess. Need some minor changes to corridor also.

I am open to PRs in this case, as my time is rather limited these days and I do not feel like completely refactoring Digger (or any other map generator).

I definitely agree that Digger, by its very nature, could be made much more customizable, providing some very different results for different sets of configurations.

[airstruck]

I am open to PRs in this case, as my time is rather limited these days and I do not feel like completely refactoring Digger (or any other map generator).

I'll probably take you up on that. Will see how it goes in the Lua port first; would be happy to backport changes afterwards.

Thanks for taking the time to maintain this project!

[kosinaz]

I was looking for the same, mostly because I saw how nice it is in DoomRL, for example. Fun fact, DoomRL uses an algorithm that is very similar to our DividedMaze. After a little bit of hacking, I managed to implement almost all the Dungeon features on the DividedMaze as a range of customization options that resulted in some beautiful mixes.

I highly doubt that the OP would be still looking for a solution, but I think this would be a cool addition. Anyways, I'm planning to continue the improvement of this algorithm, to get even closer to the one in DoomRL, like a non-perfect maze variant and a biased wall-generation as additional options.

So related PRs are on the way, if you are still interested.