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.
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.
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.
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:
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.
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.
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.
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].
> 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.
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.
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.
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.
I agree. I also have spent a lot of time thinking about how to make PCG better. My conclusion is that the key is intent/design. The PCG algorithm needs to first generate the high-level gameplay design/intent and then the context. Instead of just arbitrarily placing things, it needs to place things constrained by what makes sense from a gameplay/fun point of view.
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.
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 =)
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.
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.
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.