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!
This has been more or less answered before. Your first stop place should be http://pcg.wikidot.com/
Since I was informed of this not being a helpful answer at all, 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.
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.
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.
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.
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.
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.
