Generating a random "dungeon"?

[Jasoco]

How exactly do random dungeon generators work to the point they always create one you can complete? (i.e. no walls block you off from the most important places, but it's not so easy as there's direct paths right there)

I'm working on a game where I want the world to be random each time, but it needs to be navigable and not get in your way.

[vrld]

There are several approaches to do this.

The most common is to use a noise function like perlin noise or value noise (implemented in my entry for the explosion contest) to create the terrain. The problem is that the noise generation is really, really slow.

Noise functions use "random" functions that return the same value for a given set of coordinates. You can ignore the noise part and do 'something' with math.random(). You will get the same chain of numbers for the same seed, e.g. 0.84018771715471, 0.39438292681909, 0.78309922375861 are the first three numbers (on my computer) when seeded with 1. The question is then how to interpret the numbers. Drawback: The dungeons might look really, really weird.

To make the actual dungeon, you can use a maze generation algorithm. There are quite a few out there, for any kind of maze you can think of. Combine that with fixed-seed random number generators and you can probably get really good results.

Another interesting idea would be to use Markov chains to actually learn how a dungeon looks like and then generate one using that Markov chain.

Anyway, the Procedural Content Generation Wiki is a good resource for that kind of stuff.

[Taehl]

What vrld said. But as a shorter answer: Don't think of it in terms of walls (additive). Think of it in terms of rooms, and halls between those rooms (subtractive). Essentially, spawn a starting room. Then place some number of adjacent rooms with hallways connecting them to the first room. Then repeat this to the adjacent rooms, until you have the size of a dungeon you want. When placing rooms, check to make sure they don't overlap existing rooms (if you skip this check, you can end up with some strange stuff, but it may be good - experiment). Then just place walls along the perimeters of the rooms and halls.

A note on additive and subtractive: Contrast the Hammer level editor against the UnrealEd editor (though the UE3's editor can do either method). If you've used those, you'll see what I mean.

[bmelts]

There've been random dungeon-type things done in LÖVE before - this topic springs to mind, though tragically the forum attachment was lost in the alien abduction. Fortunately, I have it mirrored here.

Beyond that, the PCG wiki was already mentioned as a resource, and I can't recommend it highly enough. In particular, this list of articles ought to provide some guidance.

[Adamantos]

hi,

using a "binay space partition" is a very elegant way to handle the dungeon generation.
You can find a nice introduction here
There is also a working example (+ source code) on this site, where you can see the generator in action.

[Jasoco]

hi,

using a "binay space partition" is a very elegant way to handle the dungeon generation.
You can find a nice introduction here
There is also a working example (+ source code) on this site, where you can see the generator in action.

Thanks. That BSP tip on the Rogue Wiki is pretty helpful in understanding how they're usually made. I'm looking into it and have something working so far.

How about creating overworlds? This helps for dungeons, but what about generating simple land with trees and rivers mayhaps?

[Geti]

It depends what you want. Generally if you have a general target (say, an island) then you create a basis for that first (say, create a 2D world array with "medium height" tiles in a blob in the middle and "below sea level height" tiles around that) and mess it up a bit (apply noise, smooth, apply noise, smooth, run erosion simulation) and put objects on it (place premade tile group "house_15" at some coordinates x y, spam trees, drop mobs in, w/e).

This approach means that you never end up with freakish nightmare worlds (all sea, all sand, huge bizarre mishmash of tiles, etc) as you define the starting point and just set a random seed. You can apply random rivers and bays and whatnot by subtracting from the initial blob, too.

[Taehl]

Perlin noise is a good, fast way for making natural-looking things.

[Jasoco]

Yeah. This is a little difficult. I was trying to make a mini RPG style roguelike game and thought it might be cool to use randomly generated worlds. But I don't want it to be just dungeons. I'd want an overworld and towns and such. But I guess creating overworlds would be harder.

The hardest part would be creating "completable" random worlds. You don't want to end up with the only key on the wrong side of the door, or an exit right next to the entrance, or a wall that your engine forgot to make a pathway through.