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

Rooms and Mazes: A Procedural Dungeon Generator

journal.stuffwithstuff.com

Post reply on HN
Print view View original

21–30 of 51 posts

Re: Rooms and Mazes: A Procedural Dungeon Generator

#21

Post by agentultra »

doomlaser wrote: post #6

Another cheap and very effective technique for procedural level and maze generation is to create a "walker" or series of walkers that start at some point, walk in a direction and then turn at random intervals, leaving a path of corridors and occasionally rooms in their wake. This is how Vlambeer's Nuclear Throne generates its levels, and there's a good article from Jan Willem Nijman, it's developer, here: http://www.…

Have you seen Brogue? It's level design is pretty incredible. I do love Spelunky but I think Brogue, from a design and technical perspective, is better.

One area I've been experimenting in is constraint-based solvers in my generators. It requires keeping track of rooms or regions but allows the algorithm to express ideas like: this room has a health potion but the boss cannot be within 2 rooms of it. You can of course get more creative with your constraints. I'd like to build up the ability to have sophisticated (for some value of sophistication) puzzles built into the dungeons I generate.

Re: Rooms and Mazes: A Procedural Dungeon Generator

#22

Post by munificent »

doomlaser wrote: post #6

Another cheap and very effective technique for procedural level and maze generation is to create a "walker" or series of walkers that start at some point, walk in a direction and then turn at random intervals, leaving a path of corridors and occasionally rooms in their wake. This is how Vlambeer's Nuclear Throne generates its levels, and there's a good article from Jan Willem Nijman, it's developer, here: http://www.…

These links are awesome. I've considered an "incremental digger" model like Nuclear Throne's before. I like that they're "realistic" in that they sort of simulate how creatures would have created the dungeon. I haven't played with them enough to see if I can get fun results out of them, but now I find myself wanting to try.

> Keep in mind the basics of a good story: an escalation in tension and difficulty, spaced with breathers for rhythm and flow.

It's out of scope for this article, but my little game tries to do some of that. Once the dungeon is generated, it chooses a random starting place for the player. Then it calculates the distance to that tile for every other tile.

When monsters, treasure, and quest goals are placed, those distances are taken into account. Harder monsters and better stuff are placed (roughly) farther from the player, so it feels like there's a general progression in difficulty and reward as you go farther through the dungeon.

There's definitely a lot more I could there.

Now that I think about it, one simple refinement would be:

1. Place all of the monsters first.

2. Recalculate distances and treat tiles near monsters as being "high distance" based on the monster's strength so that paths that go through monsters become "longer".

3. Now place treasure according to that.

That would give you dungeons where monsters "guard" better treasure, and stronger monsters protect better loot.

Re: Rooms and Mazes: A Procedural Dungeon Generator

#23

Post by kibwen »

gus_massa wrote: post #17

> It’s not perfect, though. It tends to produce annoyingly windy passages between rooms. One possibility is to straight some corridors in a new final step, but I don't know how well this work in the actual mazes. For example, transform: -+ +- ==> ----- +-+ and | | | +- ==> +--- +-+

Amusingly, I think this demonstrates one of the problems with classic roguelike dungeon generation: single-tile corridors are rarely very interesting, and usually much less interesting than the rooms they connect.

To cop a quote from the OP itself:

"Fundamentally, games are about making decisions from a set of alternatives."

In a hallway, your alternatives are reduced to moving forward and moving backward. When confronted with enemies, you can choose from at most two to attack (ignoring AOE for a moment, since it's usually also strictly less interesting in narrow corridors, as the article mentions as well).

Instead of passageways, I prefer a technique I've seen in Dungeon Crawl Stone Soup: start with an enormous open level (often in a more interesting shape than a square, such as a randomly-generated blob), and generate enclosed rooms within that level. At the limit, you can recursively partition the entire level until it's a series of small interconnected rooms, doing away with passageways altogether.

Re: Rooms and Mazes: A Procedural Dungeon Generator

#25

Post by mjn »

doomlaser wrote: post #6

Another cheap and very effective technique for procedural level and maze generation is to create a "walker" or series of walkers that start at some point, walk in a direction and then turn at random intervals, leaving a path of corridors and occasionally rooms in their wake. This is how Vlambeer's Nuclear Throne generates its levels, and there's a good article from Jan Willem Nijman, it's developer, here: http://www.…

As another resource, here's a draft chapter on dungeon generation, from a textbook on procedural content generation in games: http://pcgbook.com/wp-content/uploads/chapter03.pdf

(Draft in part because some of the figures still need work. I'm a coauthor of the book, but not of this particular chapter.)

Re: Rooms and Mazes: A Procedural Dungeon Generator

#26

Post by alilja »

munificent wrote: post #22
doomlaser wrote: post #6

Another cheap and very effective technique for procedural level and maze generation is to create a "walker" or series of walkers that start at some point, walk in a direction and then turn at random intervals, leaving a path of corridors and occasionally rooms in their wake. This is how Vlambeer's Nuclear Throne generates its levels, and there's a good article from Jan Willem Nijman, it's developer, here: http://www.…

These links are awesome. I've considered an "incremental digger" model like Nuclear Throne's before. I like that they're "realistic" in that they sort of simulate how creatures would have created the dungeon. I haven't played with them enough to see if I can get fun results out of them, but now I find myself wanting to try. > Keep in mind the basics of a good story: an escalation in tension and difficulty, spaced wit…

You could enhance that second point by adding some noise to the function so the difficulty isn't a smooth ramp — you get some tough monsters earlier and then maybe the next group isn't as difficult.

Re: Rooms and Mazes: A Procedural Dungeon Generator

#27

Post by munificent »

mjn wrote: post #25
doomlaser wrote: post #6

Another cheap and very effective technique for procedural level and maze generation is to create a "walker" or series of walkers that start at some point, walk in a direction and then turn at random intervals, leaving a path of corridors and occasionally rooms in their wake. This is how Vlambeer's Nuclear Throne generates its levels, and there's a good article from Jan Willem Nijman, it's developer, here: http://www.…

As another resource, here's a draft chapter on dungeon generation, from a textbook on procedural content generation in games: http://pcgbook.com/wp-content/uploads/chapter03.pdf (Draft in part because some of the figures still need work. I'm a coauthor of the book, but not of this particular chapter.)

Can I take a moment to be critical here? I hate sounding negative, but I'll try to be constructive.

I was really excited when I first stumbled onto this book. As you can imagine, it's perfectly in line with my interests. But, when I tried to read it, the prose just killed me. I think there's good ideas in there, but I can't bear to wade through the heavy-handed academic style get there.

I understand writing for a certain venue requires certain stylistic choices, but I really hope you guys can tone it down a bit. Here's a sentence plucked randomly from the linked chapter:

> "Generative grammars were originally devised as a method to formally describe sets of linguistic phrases."

Let me just go through that:

"originally devised" -> "Devise" implies originality.

"as a method" -> This adds nothing to the sentence.

"formally" -> I suppose this matters in some cases but given that the chapter isn't a precise introduction to generative grammars, whether or not it's a formal system doesn't seem very critical to me.

"sets of" -> This adds nothing.

"linquistic" -> What other kinds of phrases are there?

I would edit this sentence down to:

> Generative grammars were invented to describe written text.

I understand academic writing isn't designed to be read for pleasure, but we're all human. If you make the prose more approachable, you'll reach a much wider audience. You have some fantastic material in here, great algorithms, diagrams, and structure. I just feel that the writing style gets in the way of it.

If I could suggest anything, it's that the authors go through the prose and for every phrase ask themselves: "Does this add information? Is there a way to convey the same concept in plainer language?"

Re: Rooms and Mazes: A Procedural Dungeon Generator

#28

Post by munificent »

alilja wrote: post #26
munificent wrote: post #22

Earlier quoted context omitted.

These links are awesome. I've considered an "incremental digger" model like Nuclear Throne's before. I like that they're "realistic" in that they sort of simulate how creatures would have created the dungeon. I haven't played with them enough to see if I can get fun results out of them, but now I find myself wanting to try. > Keep in mind the basics of a good story: an escalation in tension and difficulty, spaced wit…

You could enhance that second point by adding some noise to the function so the difficulty isn't a smooth ramp — you get some tough monsters earlier and then maybe the next group isn't as difficult.

Right. I fuzz that on the other end in my game: the distances are calculated accurately, but the monsters are distributed semi-randomly by distance.

The basic process is:

1. Pick a random difficulty for the monster. 2. Pick n random locations for the monster and place it at the farthest one.

n is based on the monster's difficulty so stronger monsters get more chances to end up farther away. This means you can still run into really hard stuff early, it's just less common.

Re: Rooms and Mazes: A Procedural Dungeon Generator

#29

Post by munificent »

pavel_lishin wrote: post #24

Any thoughts on letting the rooms overlap sometimes, to generate dungeons that have non-rectangular rooms?

Yes, that would work fine. You just have to track when that happens so that you know those two rooms are already merged.

Another option is to generate non-overlapping bounding boxes for rooms, but then don't fill in that entire box. Instead, you can draw whatever shape you want in there.

The maze generator will then fill in the cracks you leave.

Re: Rooms and Mazes: A Procedural Dungeon Generator

#30

Post by p0nce »

agentultra wrote: post #21
doomlaser wrote: post #6

Another cheap and very effective technique for procedural level and maze generation is to create a "walker" or series of walkers that start at some point, walk in a direction and then turn at random intervals, leaving a path of corridors and occasionally rooms in their wake. This is how Vlambeer's Nuclear Throne generates its levels, and there's a good article from Jan Willem Nijman, it's developer, here: http://www.…

Have you seen Brogue? It's level design is pretty incredible. I do love Spelunky but I think Brogue, from a design and technical perspective, is better. One area I've been experimenting in is constraint-based solvers in my generators. It requires keeping track of rooms or regions but allows the algorithm to express ideas like: this room has a health potion but the boss cannot be within 2 rooms of it . You can of cour…

Brogue is indeed really impressive with level generation (and also gameplay!). I still wonder how holes and deep water are positionned.
Post reply on HN