Procedural generation is a pretty hot topic nowadays. I'm kinda into it since I'm lazy and love to explore. It's also a pretty tricky subject that a lot of people seem to get wrong from the beginning, so I figured I should make a discussion thread and try to share my wisdom, spur discussion and whatnot.
First of all, I've seen some horrific cases of people mixing up 'procedural' and 'random', and made generators along the lines of "spawn a bunch of trees and rocks at random positions in the game room". That's... not going to be very addicting to play in the long run. x3
The issue with that kind of approach is that it's very, VERY bottom-up; you spawn stuff somehow and then decide afterwards what it became. The thing with that kind of approach is that you have very little control over the end result, and I'm not quite fond of bottom-up approaches as a result. I guess their main draw is that they require less planning and are easier to set up, and you often get more organic results from them, so they're good for natural-looking areas (caves, Minecraft clone worlds).
The first random generation method I got working was a bottom-up approach that worked along these lines:
- Generate a world grid and fill it with 'wall'.
- Pick a start point along one of the map's edges, but a few step away from the edge. Pick the appropriate direction across the map. (To make this explanation easier to understand, I'll assume the left edge and the direction right were picked)
- Go across the map one step at a time, putting 'floor' tiles into the grid (overwriting the 'wall' tiles).
- Your path has a 'width' that is at least 3 tiles; apart from making the active cell a floor, you also make [width] cells below it floors.
- Every step, with a random chance, move the active cell up or down one step.
- Every step, with a random chance, make the width 1 cell bigger or smaller. (Don't let it get below 3).
- Stop once you're close enough to the right edge of the grid.
It's a very easy method to get working, and it's pretty powerful as well. You can make more complicated dungeons by doing more than one 'path', for instance, and if you note down every path start and end point, you have a list of possible places to spawn the exit, treasure, and the player in. The method is binary (any cell in the grid is either a wall or a floor), so the dungeons you generate are a bit crude, but you can post-process it to refine it, e.g. by creating a 'region' grid to decide whether places are just rock, mossy rock, or completely covered in vegetation. Or something like that.
The other big school of random generation is top-down. This basically means that you decide what everything is before you spawn it.
One method I'm currently working on (2D platformer-perspective dungeons) goes along these lines:
- First, decide how many floors the dungeon has and how wide each floor are. Make a grid (layout_grid) with that size and fill it with null values.
- Decide on a random start position for the first floor.
- Decide on how many rooms the first floor should have.
- Fill in that many cells with 'DUNGEON_ROOM_NORMAL'.
- Select one of the cells randomly and change it into DUNGEON_ROOM_STAIRS_TO_NEXT_FLOOR.
- Go to the next floor.
- Decide how many rooms this floor should have
- Decide on a start position such that one of the rooms of this floor will be above the previous floor's stairs.
- Fill in rooms with DUNGEON_ROOM_NORMAL, except for the room that is directly above the previous floor's stairs; fill that with DUNGEON_ROOM_STAIRS_TO_PREVIOUS_FLOOR.
- Keep going until all floors are done.
- Create another grid (content_grid) with the same size and fill it with null values.
- Using a list of the number of encounters, treasure and quest objectives, place CONTENT_ENCOUNTER, CONTENT_TREASURE and CONTENT_QUESTOBJECTIVE values at random spots in content_grid, but never overwrite another such value, and only put them in spots where layout_grid isn't null.
- Finally, select room types for all rooms (using a third grid) and actually spawn them in the game. I'm still working on this step so not much details on HOW. x3
Note how it has 4 steps instead of 2? That's the price you have to pay for doing things top-down. They can also be a lot less varied since there's less chaos going on. So I guess you might want to combine top-down and bottom-up approaches for the best results.