10 ms·

Rooms and mazes: A procedural dungeon generator (2014)

163 points by probabletrain 4y ago

UnpossibleJim 4y ago
I'm still waiting for someone to name their dungeon generator "Mazes and Monsters" as a nod to Tom Hanks' entry into the anti-D&D hysteria that gripped the 1980's. I am sure I would be pleased with the product but once again, disappointed in the name =)
- timoteostewart 4y ago
  The 1982 Tom Hanks movie of that name was based on the 1981 novel by Rona Jaffe! https://en.m.wikipedia.org/wiki/Mazes_and_Monsters_(novel) https://en.m.wikipedia.org/wiki/Mazes_and_Monsters_(novel)
wintermutestwin 4y ago
Interesting to have the explanations of how it is built and the code, but the end results pale in comparison to this amazing tool which I frequently use in my D&D campaigns: https://watabou.itch.io/one-page-dungeon https://watabou.itch.io/one-page-dungeon Other interesting generators here as well: https://watabou.itch.io/ https://watabou.itch.io/ And this prior discussion is full of great links: https://news.ycombinator.com/item?id=30338074 https://news.ycombinator.com/item?id=30338074
- Minor49er 4y ago
  Someone in the comments for One Page Dungeon pointed out that someone has been using it to generate books and sell them on Amazon without crediting or giving anything back to the code's author. While it doesn't violate the license, it's sad to see.
  - gernb 4y ago
    Is it sad? I recently put up a game with MIT license. The game IMO is pretty fun. I didn't need to write this in the README but just to be clear I wrote "You're free to ship this in a commercial app". I intentionally made it MITed. I know the reprocussions. If someone has the initiative to make a commerical product from it good for them. I'm too lazy which is exactly why I just posted it to github and MITed it.
    - Minor49er 4y ago
      I think it's sad because credit should be given where credit is due
      - gernb 4y ago
        Well if the person isn't following the license that's bad. MIT says you must include the license which means they would get credit.
        Minor49er 4y ago
        The license can say that you're free to do anything without repercussion. My point is that if someone is essentially repackaging something that they had little input in creating, a mention of what was used would be nice.
throwanem 4y ago
Hugged to death? https://web.archive.org/web/20220420162023/https://journal.stuffwithstuff.com/2014/12/21/rooms-and-mazes/ https://web.archive.org/web/20220420162023/https://journal.s...
nonrandomstring 4y ago
Enjoyable to see someone reasoning creatively about various ways to solve this. In the end there are so many ways, each giving their own feel. I would do generative landscapes by starting with Perlin noise clouds, low pass filtering and then "flooding" the height-map with a water table. That's basically how old generative landscapes like Bryce used to work I think. For caves, pick a min and max plane, extrude to get walls. As mentioned in the article checking connectivity was always the PITA - and with 3D procedural mazes you have to also check they're passable for the chosen engine's collision code. That's how I learned about my favourite constant... Gerver's optimal sofa constant...the maximum size sofa that can move around a unit corner [1]. [1] https://de.zxc.wiki/wiki/Sofaproblem https://de.zxc.wiki/wiki/Sofaproblem
- thaumasiotes 4y ago
  > The sofa problem is a so far unsolved geometrical problem that was described in 1966 by the Austrian-Canadian mathematician Leo Moser . It is a two-dimensional idealization of the practical problem of moving furniture around obstacles. Doesn't seem to have much to do with the actual problem of moving furniture, where the third dimension is heavily exploited.
- cheschire 4y ago
  I wonder what Douglas Adams would've said about that. https://dirkgently.fandom.com/wiki/Sofa_on_the_staircase https://dirkgently.fandom.com/wiki/Sofa_on_the_staircase
dataminded 4y ago
It'd be great if someone connected this to a virtual table top like Foundry. You could get maps, lighting, encounters, etc. at the press of a button. It would really enable the online-first, one-shot friendly reality of TTRPGs.
bovermyer 4y ago
If you really want to dive into tabletop game generators, there's this resource: https://rpggen.dev/ https://rpggen.dev/
jonnycomputer 4y ago
I was a little skeptical of the result, but the dungeons in the game Hauberk are pretty nice actually.
- munificent 4y ago
  The current version of Hauberk uses a bunch of different dungeon generators which it is able to merge together. This was sort of a holy grail for me for many many years. I've been meaning to write down something about it but haven't gotten around to it.
  - mysterydip 4y ago
    As someone with an interest in procedural generation in general and working on a game using dungeon generators specifically, I'd love to read it when you do.
murrain 4y ago
Tile-Based Map Generation using Wave Function Collapse in 'Caves of Qud' https://www.youtube.com/watch?v=AdCgi9E90jw https://www.youtube.com/watch?v=AdCgi9E90jw
- tokai 4y ago
  I'm a huge fan of CoQ. But sometimes the chaotic layout of the procedural maps really clash with the neatness of the hand made story locations and towns. It's minor gripe though, meshing curated and procedural content seems like a hard task.
  - at_a_remove 4y ago
    I spend like, a hideous amount of time thinking about this exact thing. I have been using computers to aid me in DMing since I was doing Basic/Expert on my TI-99 4/A. Procedural content has a number of drawbacks. Just to pick one example, take the various cellular automata algorithms to generate cave systems (or really any algo). What would be great for this is if the 2D very simulationist matrix of on/off cells could be remapped to a series of nodes ("large enough caves") and edges ("passageways"). You could then try to do lock-and-key puzzles based on this. Aside from the "sameness" issue, most of these lack two big features that people can extrapolate from playing a dungeon: history and purpose. The first, purpose, is essentially about the creature, humanoid, whatever that did the excavation -- what were they doing? Was it a xorn just kind of gobbling around? Water? Perhaps a humble owlbear looking to make a nest. Or were some dwarves tidily making a mine? Perhaps a religion was having secret meetings there. The smarter the creature, the more you have to think about purpose and intention. As an example, let's take our secret cult (literally "occult"): unless they worshiped a slime deity, they probably wouldn't place the privy next to the altar. Nor would dwarves place the privy next to the kitchen. Logical places would exist for things. History comes from having multiple excavations over time. A river overflows its banks for a century and hollows out a spot under a cliff. Then the owlbear. Ah, but a dragon eats the owlbear. Years later a dwarf hikes by and sees a gleam of promising minerals at the back of that abandoned owlbear cave and brings friends to excavate. Later, the mine is played out and a lich moves in, adding various traps ... Most procedural dungeons pay little to no attention to these steps, which are, after all, quite hard. After that, you have to avoid your "monster hotel" scenario to make some kind of quasi-believable ecology to your system. In reality, most full-time cave dwellers are small and feeble and delicate, so you may want to "shallow up" your dungeons or populate the more remote areas with creatures whose nutritional needs are scant (fungi, slimes, undead, constructs). Perhaps there are holes through which a vibrant river drains and at least there are fish for Gollum to catch. Or deep magicks emanate a kind of mana to be devoured by a fungus not unlike the kind that has adapted to live on spent fuel rods here on Earth. Then, you have to consider player satisfaction. You may want to "Jaquay" that dungeon area. Some players like exploration, some like puzzles, and some must kill every last critter no matter how small. Others want to accomplish the goal (whatever that is) and leave. Putting all of this together gets harder and harder with procedural content.
tunesmith 4y ago
I've recently gotten back into first edition D&D (AD&D) and had overlooked for years that there's a whole dungeon generation "algorithm" in the back of the book. I've started to use it to play "solitaire", which I've learned is a fairly popular thing to do for old DMs that enjoy practicing their DM skills (you roll up your own group and pretend they're making their own choices). What's fun about it is that the dungeons it generates are crazy. Diagonal passageways, varying passage widths, stairways that might go down multiple levels and then come back up, rooms that are only accessible by traveling to other levels temporarily, etc. The other thing that is interesting is that the order of generation is based off the party's choice of what door/passage to explore next, so it's very much intended to be generated during actual play. I've thought more than once it would be fun to work up a tool to generate that dungeon on demand, to just press a button each time a choice is made and then watch it animate.
- lakkal 4y ago
  I used to DM games sometimes using those random charts from the AD&D DM Guide. It was a lot of fun. The players (who knew what I was doing) always tried to figure out the purpose of the labyrinth based on what what developed.
- cableshaft 4y ago
  You might be interested in "Four Against the Darkness". It's a solo pen and paper dungeon crawler with dungeon generation. You just need to get a couple of paperbacks to play. https://boardgamegeek.com/boardgame/197097/four-against-darkness https://boardgamegeek.com/boardgame/197097/four-against-dark...
  - HelloNurse 4y ago
    The exact title is "Four against Darkness" (usual abbreviation "4AD"). Highly recommended.
  - tunesmith 4y ago
    Wow. That looks wildly inventive. I'm more interested in the DMG version just to practice my DM skills, but I totally understand the appeal.
dang 4y ago
Related: Rooms and Mazes: A Procedural Dungeon Generator (2014) - https://news.ycombinator.com/item?id=20533546 https://news.ycombinator.com/item?id=20533546 - July 2019 (15 comments) Rooms and Mazes: A Procedural Dungeon Generator - https://news.ycombinator.com/item?id=8782295 https://news.ycombinator.com/item?id=8782295 - Dec 2014 (48 comments)
HelloNurse 4y ago
Apart from caring about correct connectivity and ensuring it in a principled and general way by merging connected components (an obvious "best practice" that randomness-obsessed authors sometimes neglect because it addresses unlikely cases) the main good idea in the article is filling up the space between disconnected rooms with tunnels: two easy and very general "modules" as a starting point and two editing steps (knocking down 1-cell walls, then optionally pruning dead ends), also easy, are enough to obtain a good dungeon. The same technique could be applied to better starting rooms than random rectangles (more varied random shapes, constrained good layouts like Rogue's 3 by 3 rooms arrangement, predefined "vaults", etc.) to obtain production-quality dungeons for roguelike games.
bullen 4y ago
I use his visit card dungeon code for my upcoming multiplayer dungeon crawler: http://cave.rupy.se http://cave.rupy.se It's inefficient (I slow it down to see how it works on this example page) but it's pretty cool for so little code!

163 points by probabletrain 4y ago

I'm still waiting for someone to name their dungeon generator "Mazes and Monsters" as a nod to Tom Hanks' entry into the anti-D&D hysteria that gripped the 1980's. I am sure I would be pleased with the product but once again, disappointed in the name =)

timoteostewart 4y ago
The 1982 Tom Hanks movie of that name was based on the 1981 novel by Rona Jaffe! https://en.m.wikipedia.org/wiki/Mazes_and_Monsters_(novel) https://en.m.wikipedia.org/wiki/Mazes_and_Monsters_(novel)

wintermutestwin 4y ago

Interesting to have the explanations of how it is built and the code, but the end results pale in comparison to this amazing tool which I frequently use in my D&D campaigns: https://watabou.itch.io/one-page-dungeon https://watabou.itch.io/one-page-dungeon Other interesting generators here as well: https://watabou.itch.io/ https://watabou.itch.io/ And this prior discussion is full of great links: https://news.ycombinator.com/item?id=30338074 https://news.ycombinator.com/item?id=30338074

Minor49er 4y ago
Someone in the comments for One Page Dungeon pointed out that someone has been using it to generate books and sell them on Amazon without crediting or giving anything back to the code's author. While it doesn't violate the license, it's sad to see.
- gernb 4y ago
  Is it sad? I recently put up a game with MIT license. The game IMO is pretty fun. I didn't need to write this in the README but just to be clear I wrote "You're free to ship this in a commercial app". I intentionally made it MITed. I know the reprocussions. If someone has the initiative to make a commerical product from it good for them. I'm too lazy which is exactly why I just posted it to github and MITed it.
  - Minor49er 4y ago
    I think it's sad because credit should be given where credit is due
    - gernb 4y ago
      Well if the person isn't following the license that's bad. MIT says you must include the license which means they would get credit.
      - Minor49er 4y ago
        The license can say that you're free to do anything without repercussion. My point is that if someone is essentially repackaging something that they had little input in creating, a mention of what was used would be nice.

throwanem 4y ago

Hugged to death? https://web.archive.org/web/20220420162023/https://journal.stuffwithstuff.com/2014/12/21/rooms-and-mazes/ https://web.archive.org/web/20220420162023/https://journal.s...

nonrandomstring 4y ago

Enjoyable to see someone reasoning creatively about various ways to solve this. In the end there are so many ways, each giving their own feel. I would do generative landscapes by starting with Perlin noise clouds, low pass filtering and then "flooding" the height-map with a water table. That's basically how old generative landscapes like Bryce used to work I think. For caves, pick a min and max plane, extrude to get walls. As mentioned in the article checking connectivity was always the PITA - and with 3D procedural mazes you have to also check they're passable for the chosen engine's collision code. That's how I learned about my favourite constant... Gerver's optimal sofa constant...the maximum size sofa that can move around a unit corner [1]. [1] https://de.zxc.wiki/wiki/Sofaproblem https://de.zxc.wiki/wiki/Sofaproblem

thaumasiotes 4y ago
> The sofa problem is a so far unsolved geometrical problem that was described in 1966 by the Austrian-Canadian mathematician Leo Moser . It is a two-dimensional idealization of the practical problem of moving furniture around obstacles. Doesn't seem to have much to do with the actual problem of moving furniture, where the third dimension is heavily exploited.
cheschire 4y ago
I wonder what Douglas Adams would've said about that. https://dirkgently.fandom.com/wiki/Sofa_on_the_staircase https://dirkgently.fandom.com/wiki/Sofa_on_the_staircase

dataminded 4y ago

It'd be great if someone connected this to a virtual table top like Foundry. You could get maps, lighting, encounters, etc. at the press of a button. It would really enable the online-first, one-shot friendly reality of TTRPGs.

bovermyer 4y ago

If you really want to dive into tabletop game generators, there's this resource: https://rpggen.dev/ https://rpggen.dev/

jonnycomputer 4y ago

I was a little skeptical of the result, but the dungeons in the game Hauberk are pretty nice actually.

munificent 4y ago
The current version of Hauberk uses a bunch of different dungeon generators which it is able to merge together. This was sort of a holy grail for me for many many years. I've been meaning to write down something about it but haven't gotten around to it.
- mysterydip 4y ago
  As someone with an interest in procedural generation in general and working on a game using dungeon generators specifically, I'd love to read it when you do.

murrain 4y ago

Tile-Based Map Generation using Wave Function Collapse in 'Caves of Qud' https://www.youtube.com/watch?v=AdCgi9E90jw https://www.youtube.com/watch?v=AdCgi9E90jw

tokai 4y ago
I'm a huge fan of CoQ. But sometimes the chaotic layout of the procedural maps really clash with the neatness of the hand made story locations and towns. It's minor gripe though, meshing curated and procedural content seems like a hard task.
- at_a_remove 4y ago
  I spend like, a hideous amount of time thinking about this exact thing. I have been using computers to aid me in DMing since I was doing Basic/Expert on my TI-99 4/A. Procedural content has a number of drawbacks. Just to pick one example, take the various cellular automata algorithms to generate cave systems (or really any algo). What would be great for this is if the 2D very simulationist matrix of on/off cells could be remapped to a series of nodes ("large enough caves") and edges ("passageways"). You could then try to do lock-and-key puzzles based on this. Aside from the "sameness" issue, most of these lack two big features that people can extrapolate from playing a dungeon: history and purpose. The first, purpose, is essentially about the creature, humanoid, whatever that did the excavation -- what were they doing? Was it a xorn just kind of gobbling around? Water? Perhaps a humble owlbear looking to make a nest. Or were some dwarves tidily making a mine? Perhaps a religion was having secret meetings there. The smarter the creature, the more you have to think about purpose and intention. As an example, let's take our secret cult (literally "occult"): unless they worshiped a slime deity, they probably wouldn't place the privy next to the altar. Nor would dwarves place the privy next to the kitchen. Logical places would exist for things. History comes from having multiple excavations over time. A river overflows its banks for a century and hollows out a spot under a cliff. Then the owlbear. Ah, but a dragon eats the owlbear. Years later a dwarf hikes by and sees a gleam of promising minerals at the back of that abandoned owlbear cave and brings friends to excavate. Later, the mine is played out and a lich moves in, adding various traps ... Most procedural dungeons pay little to no attention to these steps, which are, after all, quite hard. After that, you have to avoid your "monster hotel" scenario to make some kind of quasi-believable ecology to your system. In reality, most full-time cave dwellers are small and feeble and delicate, so you may want to "shallow up" your dungeons or populate the more remote areas with creatures whose nutritional needs are scant (fungi, slimes, undead, constructs). Perhaps there are holes through which a vibrant river drains and at least there are fish for Gollum to catch. Or deep magicks emanate a kind of mana to be devoured by a fungus not unlike the kind that has adapted to live on spent fuel rods here on Earth. Then, you have to consider player satisfaction. You may want to "Jaquay" that dungeon area. Some players like exploration, some like puzzles, and some must kill every last critter no matter how small. Others want to accomplish the goal (whatever that is) and leave. Putting all of this together gets harder and harder with procedural content.

tunesmith 4y ago

I've recently gotten back into first edition D&D (AD&D) and had overlooked for years that there's a whole dungeon generation "algorithm" in the back of the book. I've started to use it to play "solitaire", which I've learned is a fairly popular thing to do for old DMs that enjoy practicing their DM skills (you roll up your own group and pretend they're making their own choices). What's fun about it is that the dungeons it generates are crazy. Diagonal passageways, varying passage widths, stairways that might go down multiple levels and then come back up, rooms that are only accessible by traveling to other levels temporarily, etc. The other thing that is interesting is that the order of generation is based off the party's choice of what door/passage to explore next, so it's very much intended to be generated during actual play. I've thought more than once it would be fun to work up a tool to generate that dungeon on demand, to just press a button each time a choice is made and then watch it animate.

lakkal 4y ago
I used to DM games sometimes using those random charts from the AD&D DM Guide. It was a lot of fun. The players (who knew what I was doing) always tried to figure out the purpose of the labyrinth based on what what developed.
cableshaft 4y ago
You might be interested in "Four Against the Darkness". It's a solo pen and paper dungeon crawler with dungeon generation. You just need to get a couple of paperbacks to play. https://boardgamegeek.com/boardgame/197097/four-against-darkness https://boardgamegeek.com/boardgame/197097/four-against-dark...
- HelloNurse 4y ago
  The exact title is "Four against Darkness" (usual abbreviation "4AD"). Highly recommended.
- tunesmith 4y ago
  Wow. That looks wildly inventive. I'm more interested in the DMG version just to practice my DM skills, but I totally understand the appeal.

dang 4y ago

Related: Rooms and Mazes: A Procedural Dungeon Generator (2014) - https://news.ycombinator.com/item?id=20533546 https://news.ycombinator.com/item?id=20533546 - July 2019 (15 comments) Rooms and Mazes: A Procedural Dungeon Generator - https://news.ycombinator.com/item?id=8782295 https://news.ycombinator.com/item?id=8782295 - Dec 2014 (48 comments)

HelloNurse 4y ago

Apart from caring about correct connectivity and ensuring it in a principled and general way by merging connected components (an obvious "best practice" that randomness-obsessed authors sometimes neglect because it addresses unlikely cases) the main good idea in the article is filling up the space between disconnected rooms with tunnels: two easy and very general "modules" as a starting point and two editing steps (knocking down 1-cell walls, then optionally pruning dead ends), also easy, are enough to obtain a good dungeon. The same technique could be applied to better starting rooms than random rectangles (more varied random shapes, constrained good layouts like Rogue's 3 by 3 rooms arrangement, predefined "vaults", etc.) to obtain production-quality dungeons for roguelike games.

bullen 4y ago

I use his visit card dungeon code for my upcoming multiplayer dungeon crawler: http://cave.rupy.se http://cave.rupy.se It's inefficient (I slow it down to see how it works on this example page) but it's pretty cool for so little code!