Procedural Dungeon Generation Algorithm
gamasutra.com
gamasutra.com
https://www.reddit.com/r/gamedev/comments/1dlwc4/procedural_...
But maybe it's just tweaks, I don't know.
He kept an interesting blog about the development of Tiny Keep and added other posts about improvements to the generation mechanics for the dungeons, including this nifty one about generating locked areas that Ben Jones worked on: http://blog.tinykeep.com/2013/09/just-sneaky-quick-update-fr...
As an older programmer who is in the midst of retooling, I would assume the opposite: graphs easy, physics hard. But that's what retooling seems to be all about -- finding the new "easy" and learning it.
I think the graph + graph algos would be trickier most of the time, but that could just be since I've written the above code many, many times.
They do something like that, but with self-contained tiles that are randomly arranged, with some variation in e.g. key/item placement.
Highly recommend brogue for anybody even tangentially interested in traditional roguelikes. Most interesting RL game design in years and the game is absolutely gorgeous, despite being glyph-based (no tiles). I'm on mobile or else I'd link.
[1] https://en.wikipedia.org/wiki/The_Warlock_of_Firetop_Mountai...
Dungeons are (in theory) built by intelligent people for a reason. There needs to be distinct working, eating, socializing, farming areas. There needs to be wider or thinner pathways between areas based on flow of people & goods.
A good starting place to look for amazing looking dungeons is to look at people who play Dwarf Fortress, and how they build & organize their forts, which are essentially dungeons.
Here are a few good links:
http://discourse.stonehearth.net/t/slave-to-armok-god-of-blo...
https://leelubutterfly.wordpress.com/2013/01/01/dwarf-fortre...
etc. just google image search for "dwarf fortress" and you'll see a lot.
Good algorithmic dungeon design should take into account some of these factors, like good city design would.
Well, in the make believe universes you frequent anyway. Others have different tastes.
I mean, in the realm of software there's a whole genre of these things going back to the original Rogue which never pretended to have any purpose at all. And digging even farther back you'll find a dice-driven (and, relative to modern standards, really terrible) random dungeon generator in an appendix at the back of the 1e AD&D DMG. Likewise even earlier TSR products like "Dungeon Geomorphs" were clearly aimed at random-or-at-least-mostly-sensesless generation.
That's not to say you can't do better, just that "not random" is probably not exactly the right aesthetic to chase.
I'd say not only. A procedural generator that took account of architecture and reason could probably make a more interesting game, not everything needs to point towards that goal, but it'd be neat if some did.
I'm bothered more with many first person shooters more which design environments basically just as long kinked up hallways you have to walk through while pretending to be in a place supposably designed with a purpose in mind.
http://www.bbc.co.uk/wiltshire/content/articles/2005/11/22/u...
This is somewhat far from the "the adventurers met a group of monsters in the corridor" or "moria's halls".
a) an underground city (your analysis is spot on, doesn't look like that)
b) a cave system
c) a mine
d) a prison
e) the lair of some non-intelligent species
f) a fortress to protect something
Another option is that they're supposed to be 'abstract challenge spaces' (as another commenter claims), but roguelikes aren't intentionally abstract: they attempt verisimilitude on lots of levels. Nethack in particular has a very detailed naive physics with all kinds of internal logic.
Brogue does its natural caves pretty well, I think. Minecraft seems to, and places its seams of minerals reasonably (neither are perfect, but they're clearly trying).
But this kind of dungeon generator? We're nearly 20 years after Crimes Against Mimesis [1] was written, and this feels like a big step backwards.
---
Honestly, you might as well attack an A* pathfinding article on the grounds that game units shouldn't necessarily take the shortest path to their goal. Algorithms like this are tools in a toolbox - obviously tweaking them is what makes any given game unique, but beginners still need to start somewhere.
(Also - Nethack? The game where you find potion shops eight levels underground that can only be reached via three rooms full of soldier ants, etc?)
Some quibbles:
> game units shouldn't necessarily take the shortest path to their goal
They shouldn't? This can in specific cases lead to weird looking behavior, but nobody is suggesting it is an 'abstract movement strategy' that isn't supposed to correspond to anything a person would do. The reason shortest paths are used is that they do correspond to the way people move, to a first approximation.
> simply enough for even beginners to implement
Really? Using delaunay triangulation, minimum spanning trees and relaxation? With no sample code? This isn't a beginner tutorial.
> can be used as-is in any particular genre of game.
Really? You don't think this is specifically for roguelikes/roguelites?
> Nethack
Nethack definitely has crimes against mimesis too, definitely. In fact it has that 'old adventure' feel. I was using it just to show that the challenge spaces aren't abstract.
"Shouldn't necessarily" means shouldn't in some cases, should in others. The point is that something like a pathfinding algorithm is not meant to distinguish between those cases, just as the worldgen algorithm in this article is clearly not attempting to create genre-specific dungeons. It gives you raw information, which you'd need to refine if you wanted to have a feel that's specific to a given game.
> This isn't a beginner tutorial.
Beginner gamedev. Is this a distinction that you think negates my argument? It sounds like you're listing up everything in my post that you think people could disagree about.
> You don't think this is specifically for roguelikes?
Whether it's about roguelikes is neither in evidence nor at issue. The parent post took issue with the article for not making maps that felt like a prison/mine/fortress/etc., and I'm saying it clearly didn't attempt to.
> Nethack ... the challenge spaces aren't abstract.
Every game is abstract in some ways and not in others. But within that universal truth, Nethack is most definitely not a game that even gestures in the direction of realistic world generation, and is a counterexample to the overall point of your post.
put those constraints as a starting point and use genetic algorithms?
That reason is typically to store something behind a lot of very dangerous traps, trick architecture, and maybe enemies.
Unless you're concerned with maintenance, you don't worry about farms and all that other nonsense--that's gold you should've been spending on golems, pit traps, and other self-maintaining defenses!
I find the current theory circulating that suggests such placement of critical resources only serves to reinforce and resupply invaders is almost entirely without merit. Why wouldn't a guard take additional effort to defend his barrel? Are they all so incompetent that they would expire before breaking into the emergency medical supplies?