News for hackers. Stuff that matters.
Re:Procedural Dungeon Generation Algorithm by smlacy on Friday September 04, 2015 @03:00PM (#10172230)
I've seen algorithms that produce results similar to this before, and I find them lacking in any sort of feeling of purposeful design.

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.

Re:Procedural Dungeon Generation Algorithm by ajross on Friday September 04, 2015 @03:23PM (#10172369)
> Dungeons are (in theory) built by intelligent people for a reason.

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.

Re:Procedural Dungeon Generation Algorithm by colechristensen on Friday September 04, 2015 @06:15PM (#10173091)
>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.

Re:Procedural Dungeon Generation Algorithm by panic on Friday September 04, 2015 @05:27PM (#10172942)
Think less "town" and more "cave". Spaces created by natural processes also lack any feeling of purposeful design, but still have lots of interesting variation. The feeling of exploring an untamed natural space (which even the creator of the game hasn't seen before!) is part of what makes these games fun, I think.
Re:Procedural Dungeon Generation Algorithm by douche on Friday September 04, 2015 @04:09PM (#10172630)
Dungeons as portrayed in every video game ever are a fantastic concept. It's not like there are actually anything like real dungeons outside of our imaginations (digging through rock is hard). The closest real analogues would probably be cave systems, like Carlsbad Caverns or Mammoth Cave, which are formed by irregular natural processes.
Re:Procedural Dungeon Generation Algorithm by twic on Friday September 04, 2015 @05:45PM (#10172993)
Re:Procedural Dungeon Generation Algorithm by jpreiland on Friday September 04, 2015 @04:53PM (#10172814)
the catacombs, perhaps? I've participated in and run more than a few dungeon crawls in catacomb settings
Re:Procedural Dungeon Generation Algorithm by riffraff on Saturday September 05, 2015 @06:29AM (#10174437)
catacombs (at least those I have visited) have _really_ tiny living spaces, and connections between rooms are basically holes.

This is somewhat far from the "the adventurers met a group of monsters in the corridor" or "moria's halls".

Re:Procedural Dungeon Generation Algorithm by kiiski on Saturday September 05, 2015 @01:18PM (#10175396)
I'm sure that every military has its share of cave complexes built into solid rock. My mandatory service in the Finnish Defense Forces took me to 5 such places, of which at least 3 had multiple levels (I can't say for sure how large any of those were, because they were generally of limits to conscripts; I was only in them because my tasks (mostly installing fiber optics and such) required it).
Re:Procedural Dungeon Generation Algorithm by fapjacks on Saturday September 05, 2015 @01:19AM (#10174036)
Hawaii has dungeons. Defensive positions (and related) built after Pearl Harbor right into the rock. Dungeons exist insofar as dungeons are underground structures built by X that are now left to ruin and hiding strange creatures and hidden treasure. Those places exist on Oahu, among others.
Re:Procedural Dungeon Generation Algorithm by dllthomas on Friday September 04, 2015 @04:11PM (#10172641)
Mines?
Re:Procedural Dungeon Generation Algorithm by goldfeld on Friday September 04, 2015 @06:58PM (#10173223)
The Parisian underground system?
Re:Procedural Dungeon Generation Algorithm by sago on Friday September 04, 2015 @06:48PM (#10173202)
I agree, though the issue, I think, is wider than 'purposeful' design. The dungeon could be a range of things, but this one doesn't look like anything except an 'algorithmic dungeon'. Is it:

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.

---

[1] http://www.reocities.com/aetus_kane/writing/cam.html

Re:Procedural Dungeon Generation Algorithm by fenomas on Saturday September 05, 2015 @04:21AM (#10174290)
Calling this a step backwards is patently unfair. The author is explaining a simple algorithm, simply enough for even beginners to implement, for building layouts of a given connectedness. They are not making any kind of argument that the results can be used as-is in any particular genre of game.

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?)

Re:Procedural Dungeon Generation Algorithm by sago on Saturday September 05, 2015 @08:31AM (#10174645)
Good points.

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.

Re:Procedural Dungeon Generation Algorithm by fenomas on Saturday September 05, 2015 @12:56PM (#10175334)
> They shouldn't? This can in specific cases..

"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.

Re:Procedural Dungeon Generation Algorithm by Litost on Saturday September 05, 2015 @04:36PM (#10175974)
For completeness, i guess most people have seen the ant colony layouts? https://www.youtube.com/watch?v=IGJ2jMZ-gaI https://www.youtube.com/watch?v=CmD5ahkOPAQ
Re:Procedural Dungeon Generation Algorithm by venomsnake on Friday September 04, 2015 @03:08PM (#10172259)
> 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.

put those constraints as a starting point and use genetic algorithms?

Re:Procedural Dungeon Generation Algorithm by andrepd on Friday September 04, 2015 @06:35PM (#10173164)
"Dungeon" is a term in game design to refer to a self contained challenge space, which can be realized in many different ways. It does not necessarily mean "dungeon" as in a real life dungeon or catacomb. It can be an actual human built space, in which case you are right, or it can be a Zelda dungeon, in which there is an overarching theme but not necessarily a sense of verisimilitude, or it can be such a simple and abstracted dungeon such as in Nethack or whatever, in which case those concerns are meaningless.
Re:Procedural Dungeon Generation Algorithm by adnzzzzZ on Friday September 04, 2015 @04:44PM (#10172778)
This really depends on the game you're making. Some games don't call for super purposeful layouts because the fun comes from things other than your surroundings making a lot of sense. As long as they generally look believable it's mostly fine. And so in those cases as a designer you just really need some places to place enemies in and going for a random enough algorithm is a good idea.
Re:Procedural Dungeon Generation Algorithm by angersock on Friday September 04, 2015 @03:35PM (#10172437)
Dungeons are (in theory) built by intelligent people for a reason.

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!

Re:Procedural Dungeon Generation Algorithm by logfromblammo on Friday September 04, 2015 @04:44PM (#10172776)
I am concerned about your apparent disregard for smashable barrels. It is critical to ensure that payroll and minor health potions are located near at hand to the live defenders of the dungeon, to keep them from loitering around near the nice parts when they should be down patrolling the adventurer-murdering parts.

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?

Re:Procedural Dungeon Generation Algorithm by Balgair on Friday September 04, 2015 @07:50PM (#10173328)
Here and there. Suppose your dungeon is full of ant people or orcs, creatures that can swing picks but are essentially dumber than the rocks they are hitting. They are rule followers and have not care for design, much like an algo. You can imagine an adventurer having to infiltrate such a place to steal a mcguffin, be it an uber-bee hive, an intestinal system of the dragon that ate you, or the random water paths that carved out a cave. The creator has to give the player a good reason why the system is random.
Re:Procedural Dungeon Generation Algorithm by SixSigma on Saturday September 05, 2015 @02:13AM (#10174110)
Funny you should mention DF. You should look at the procedurally generated dungeons it makes!
Re:Procedural Dungeon Generation Algorithm by sedatk on Friday September 04, 2015 @09:39PM (#10173576)
Not every dungeon is built for logistics. Think of temples, tombs, or traps for invaders.
Re:Procedural Dungeon Generation Algorithm by cobalt on Friday September 04, 2015 @10:24PM (#10173673)
those are still purpose built however
[dead]
Re:Procedural Dungeon Generation Algorithm by lotharbot on Saturday September 05, 2015 @01:06AM (#10174020)
HN staff has made a concerted effort to eliminate gratuitous negativity [0]. It's simple in the case of your post -- eliminate the first and last paragraphs, keeping only the substantive argument ("These dungeons are indeed built by people for a reason... video games... not making a city builder or world sim".)

[0] the following comes from https://news.ycombinator.com/newsguidelines.html

Be civil. Don't say things you wouldn't say in a face-to-face conversation. Avoid gratuitous negativity.

When disagreeing, please reply to the argument instead of calling names. E.g. "That is idiotic; 1 + 1 is 2, not 3" can be shortened to "1 + 1 is 2, not 3."

Re:Procedural Dungeon Generation Algorithm by PhasmaFelis on Saturday September 05, 2015 @12:50AM (#10173985)
Dungeons in games have to do two things: serve as spaces of play, and provide verisimilitude, suspension of disbelief. Most often, the first takes high priority, and the second shows up only as set dressing: cells in a prison, waterways in a sewer, altars in a temple, etc.

If you look at classic tabletop dungeons, though--the games that gave us the modern meaning of "dungeon" as "enclosed space full of loot and danger" as opposed to the dictionary "underground prison"--you're more likely to see a balance between the two. Everything still serves the needs of play, but within that framework you'll find bunkrooms, kitchens, storage rooms, training areas, etc, etc, sometimes even with discussion of schedules and which characters are likely to be where when, which the players can attempt to learn and take advantage of. It's more work, but it does make the gameworld feel more immersive, more real.

Either approach is perfectly valid. In a fast-paced hack-and-slash game, you're not likely to stand still long enough to notice the set dressing; you just need a space in which to kill monsters, and anything more is a waste. In a more thoughtful/exploratory RPG, the game can really benefit from a thoughtful layout.

Now isn't it nice when we can disagree without getting all huffy and belligerent?

Re:Procedural Dungeon Generation Algorithm by adnzzzzZ on Saturday September 05, 2015 @01:20AM (#10174039)
I agree with both him and you. But I think part of his point is that often times HN comments tend to focus on kind of irrelevant stuff. I'm the author of this post and the top comment here bothered me a bit because it has nothing to do with the content of the article itself, it's just the top commenter giving his opinions on what types of dungeons he likes better. I didn't even post the article to HN myself because my past experience with comments here (https://news.ycombinator.com/item?id=7540555) were similar in that discussion tends to not be that meaningfully related to what was written.
Re:Procedural Dungeon Generation Algorithm by forrestthewoods on Saturday September 05, 2015 @01:32AM (#10174053)
Thanks for making the post. Sharing knowledge is great and I appreciate it.

I've written a handful of educational posts as well. I swear the majority of comments only exist to make the commenter try to show off how much smarter than the OP they are. Reddit is the absolute worst. But HN isn't far behind.

I'm sorry the top comment doesn't actually provide any value to any one. Please don't let dingleberries like him prevent you from writing more in the future. Thanks for sharing.

Re:Procedural Dungeon Generation Algorithm by dang on Saturday September 05, 2015 @05:50AM (#10174383)
The trouble with your posts in this thread is that they make the problem worse by poisoning the well further.

We all know that HN has a problem with negative and uncharitable comments. We each need to see it in our own case in order for this to get better.

Re:Procedural Dungeon Generation Algorithm by LanceH on Saturday September 05, 2015 @12:39AM (#10173969)
He's got a point. Almost none of these algorithms produce a bathroom that's any usable distance from the front door. Imagine you're the resident ogre just back from pillaging and you've got nowhere to go. And the absurdity of a minimally connected dungeon shows itself the first time you have to run to answer the phone.
Re:Procedural Dungeon Generation Algorithm by fapjacks on Saturday September 05, 2015 @12:58AM (#10174007)
I would rather play a game involving a dungeon that was created out of realism than something like "this room is this size because the slime monster that lives here is what the PCs need to encounter now". Also I find your comment needlessly aggressive, in addition to it smelling like you are the only one that knows what is best for gamers and game designers.