Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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

Closest article I could find was http://gamedev.stackexchange.com/questions/910/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!

share|improve this question

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

There are either too many possible answers, or good answers would be too long for this format. Please add details to narrow the answer set or to isolate an issue that can be answered in a few paragraphs.If this question can be reworded to fit the rules in the help center, please edit the question.

    
Also, take a look at maze generation. –  anthony-arnold Aug 13 '10 at 1:51
    
There are some article on this subject at RogueBasin –  PATRY Aug 13 '10 at 21:29
add comment

5 Answers 5

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
1  
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! –  Gabriel Isenberg Aug 19 '10 at 5:27
add comment

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.

share|improve this answer
3  
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. –  Tom Hudson Apr 10 '12 at 19:58
    
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. –  congusbongus Jun 5 at 1:29
add comment

All these are great ideas. I have taken a little bit from RougeBasin 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 at at http://csharpcodewhisperer.blogspot.com/2013/07/Rouge-like-dungeon-generation.html

share|improve this answer
1  
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? –  Katu Aug 24 '13 at 6:40
add comment

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