47
\$\begingroup\$

What are some good resources regarding procedural content generation in the context of dungeon generation?

Closest article I could find was Algorithm for generating a 2d maze, which isn't quite what I'm looking for. Features, such as rooms and connected hallways, are ideal.

Thanks!

\$\endgroup\$

closed as too broad by Josh Jan 6 '14 at 1:16

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

27
\$\begingroup\$

This has been more or less answered before. Your first stop place should be http://pcg.wikidot.com/

Since I was accused of this not being a helpful answer at all (really? Someone asks for a resource and I post a link to a wiki dealing with the subject?), this page on the wiki deals with Dungeon generators specifically and links to various articles on the subject.
http://pcg.wikidot.com/pcg-algorithm:dungeon-generation

I'd still recommend browsing the whole wiki though, as procedural content generation is just a very creative approach and any and all ideas are valid. It's a lateral thinking challenge - and a fun one at that.

\$\endgroup\$
  • \$\begingroup\$ +1 for "all ideas are valid", but I'd like to clarify on that: All ideas are valid, but some will work better than others. Your <vague computer jargon here> idea will function, and likely be what you want, but there are other ways to do it that will be more efficient, more random, more cohesive, more customizable, or any combination thereof, unless you are either really good or really lucky. \$\endgroup\$ – Nic Hartley Jan 14 '15 at 19:20
20
\$\begingroup\$

I managed to get reasonably good looking levels by using the following algorithm, based on a square grid:

First, create a set of rooms. Random parameters will define the size of rooms and their numbers. An adaptive algorithm could even define some zones that are made of large hallways, and others of very small rooms.

Then, you need to make sure that all rooms are connected to each other. For this, run a pathfinder to dig corridors (let's say, A*) in between each pair of rooms, giving a random chosen weight to existing spaces (rooms or other corridors) compared to space not yet carved (the walls). If the difference in weight is small, then digging new corridors will be reasonably cheap, and the algorithm will make many corridors in between rooms, with many possibilities to go from a place to another. If the difference in weight is high, then the algorithm will prefer going through existing rooms and corridors, making the paths more tortuous, and with fewer choices to reach a certain destination.

This allows you, from a small number of parameters, to create very different looking levels, from sparse massive halls with small corridors linking them to a hive looking maze of closely interconnected chambers.

Here is an example of a generated level.

enter image description here

Based on this algorithm, you could add wall decoration that depends on the zone, make corridors smaller or larger, make special rooms, and so on.

\$\endgroup\$
10
\$\begingroup\$

If you like reading code and can parse C#, may I suggest the dungeon generator my roguelike Amaranth uses? It's here. It handles connected rooms, extensible features, and some other nice stuff.

If you pull down and build the whole project, there's a standalone tool that will generate and draw the dungeons so you can tweak it and see how it works.

\$\endgroup\$
  • 1
    \$\begingroup\$ I ran across Amaranth what seems like months ago, but I'd forgotten the name by the time I got into dungeon generation myself. Thanks for the link! \$\endgroup\$ – Gabriel Isenberg Aug 19 '10 at 5:27
  • 2
    \$\begingroup\$ Your article at journal.stuffwithstuff.com/2014/12/21/rooms-and-mazes is really good too, I use a modified version of that with a few extra features like different corridor gen engines etc. \$\endgroup\$ – Tobsta Apr 23 '17 at 12:31
3
\$\begingroup\$

All these are great ideas. I have taken a little bit from RogueBasin and pcg.wikidot.com, and have written my own implementation in C#.

I really liked the 'natural' look of cave-like levels that can be generated by using the cellular automata method. To understand what I mean by cellular automata method, imagine Conway's Game of Life. My code uses whats called the 4-5 method, which means a tile will become a wall if it is a wall and 4 or more of its nine neighbors are walls, or if it is not a wall and 5 or more neighbors are walls. I start by filling the map randomly with walls or space, then visit each x/y position iteratively and apply the 4-5 rule. In order to help alleviate the problem of forming isolated caves, after filling the map randomly, I blank a horizontal line across the map, setting each tile to a space instead of a wall, before applying the 4-5 rule to each tile.

You can view the code for my map handler class, and any improvements I make here

or an archived version here.

\$\endgroup\$
  • 2
    \$\begingroup\$ This question has lots of votes and it would be better, if you could open this answer little bit more. Links tend to die, eventually, so try to answer so, that there's no need to click links. How does that work? What is the main idea? How does it differ from other algorithms? \$\endgroup\$ – Katu Aug 24 '13 at 6:40
  • 1
    \$\begingroup\$ The link actually did die. \$\endgroup\$ – htmlcoderexe May 28 at 12:12
2
\$\begingroup\$

I'd think the most direct place to find this is to actually look at the source code. Two major players in the field, Angband and Nethack, are both open-source.

\$\endgroup\$
  • 3
    \$\begingroup\$ Although open-source, from what I recall neither is hugely-well-documented-source or transparent-source or written-for-learning-from source. They're easy to hack tweaks on, but much harder to grok overall. \$\endgroup\$ – Tom Hudson Apr 10 '12 at 19:58
  • \$\begingroup\$ Maybe the originals aren't great references, but there's a huge number of variants, some of which are excellent. For example, the developer of UnAngband made a number of enhancements to the dungeon generation and wrote a series of excellent blog posts, so you can definitely use the ideas if not the code. \$\endgroup\$ – congusbongus Jun 5 '14 at 1:29
  • \$\begingroup\$ The NetHack source is notoriously difficult to understand. The dungeon generator(ONE of them) is spread out across no less than THREE C files, and about 15 functions \$\endgroup\$ – Élektra Aug 4 '15 at 1:03

Not the answer you're looking for? Browse other questions tagged or ask your own question.