Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Procedural Dungeon Generation Algorithm

gamasutra.com

Post reply on HN
Print view View original

41–49 of 49 posts

Re: Procedural Dungeon Generation Algorithm

#41

Post by dang »

forrestthewoods wrote: post #37
adnzzzzZ wrote: post #36

Earlier quoted context omitted.

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 m…

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 pr…

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

#42

Post by riffraff »

archimedespi wrote: post #25
karl_gluck wrote: post #11

If anyone's interested, there is a Reddit post explaining this and an interactive demo from 2 years ago: https://www.reddit.com/r/gamedev/comments/1dlwc4/procedural_... http://tinykeep.com/dungen/

http://tinykeep.com/dungen/ _was_ the source of the figures in the article, AFAIK.

to me they look slightly different, both in animation (because of underlying algorithmic differences) and graphics (space inside rooms is black in dungen, blue in TFA).

But maybe it's just tweaks, I don't know.

Re: Procedural Dungeon Generation Algorithm

#43

Post by riffraff »

jpreiland wrote: post #17
douche wrote: post #8

Earlier quoted context omitted.

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.

the catacombs, perhaps? I've participated in and run more than a few dungeon crawls in catacomb settings

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

#44

Post by sago »

fenomas wrote: post #40
sago wrote: post #23

Earlier quoted context omitted.

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 suppos…

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…

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

#45

Post by yoklov »

neolefty wrote: post #30
carlisle_ wrote: post #6

I really like the idea to just use a physics engine as a means of randomizing the layout. Smart, succinct, and easy to implement.

I delighted in this article because of its opinions about what is easy and what is hard. Physics engine: easy; of course you have one; everyone has a physics engine. Graph data structure & algos: suggests a few places to find one. 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" an…

A physics system good enough to support this is probably ~200loc. Probably less if you cut out everything extraneous. All it is is AABB collision detection+resolution, and then some update code.

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.

Re: Procedural Dungeon Generation Algorithm

#46

Post by yoklov »

catpolice wrote: post #7

I've been working on an algorithm to make more playable dungeons with included puzzles (e.g. locked door/key quests etc.). The math is there to ensure everything is solvable and relatively interesting (you're guaranteed to run into a puzzle before you find all the elements you need to solve it, for instance) but I got bored when it came time to make an example game to illustrate how it works. I'll pick that back up a…

Brogue does this, although none of its puzzles are strictly required to progress, they are guaranteed to be solvable.

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.

Re: Procedural Dungeon Generation Algorithm

#47

Post by fenomas »

sago wrote: post #44
fenomas wrote: post #40

Earlier quoted context omitted.

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…

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. > sim…

> 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

#48

Post by kiiski »

douche wrote: post #8
smlacy wrote: post #2

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 dunge…

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.

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

#49

Post by Litost »

sago wrote: post #23
smlacy wrote: post #2

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 dunge…

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 suppos…

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
Post reply on HN