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.

Question is, where do you draw the line? In Tomb of the Snake, the first step in generating the forest level is... placing trees at random. How else? That doesn't make the rest of the process any less, well, procedural. And in RogueBot the items to collect are placed randomly on the otherwise procedurally generated map. Does that somehow diminish the result?

As for how exactly to generate dungeons, there are many valid approaches. So far I've done well with drunken walks, and especially BSP trees. But with Escape from Cnossus and now Glittering Light I kinda reached the limit of the latter, so I have to try new things going forward. RogueBot was such an attempt actually.

I say don't dismiss naive, unsophisticated approaches, because they can yield surprisingly good results. And the human brain is remarkably apt to see patterns even where there are none. Which is, like many other things, both a tragedy and a boon.

The levels in Mondrian - Abstraction in Beauty combine preset design, procedural generation, and unlockables for some pretty nifty results. Basically, the more you unlock in the game, the deeper the generation goes. Everything gets generated in about 6-8 seconds when a level loads.

1. Determine Layout: This is the heaviest handmade part of generating a level. We currently have 40 premade layouts for the main levels, and 4 layouts per Benefactor Pack (levels based on other games). So the game generates a random number between 0-39, and if that specific level is unlocked and activated, the game generates the blocks for that layout.
2. Set Color Scheme: The game then determines which particular color scheme a level will have. There are 7 schemes overall, from completely randomized to only R, G, or B values, and preset palettes.
   
3. Set Platform Emulator: Then the game decides how derezzed it will look, and for particular platforms, like the Handheld style, this overwrites the Color Scheme setting.
   
4. Set Ball, Paddle, Wall Shape & Rotation: The game does a quick roll of the dice to determine which core gameplay elements the player will have in this level. Again, this is all based on what the player has already unlocked and activated.
   
5. Scatter Powerups: Before even the blocks are placed, the game decides which powerups will be available in a level: Bomb, Lock, Wildcard, Shield, and/or None. Once all the blocks are laid out, each one loops through possible choices of available powerups or None. This creates a really fun, unpredictable, and slightly strategic feeling to each level, and makes each level very different from the last.
   
6. Background: Finally, the game picks a random background from the ones available.
   

Like I said, all that's done in less than 10 seconds. These 6 steps essentially create a massive number of possible level variations within a strict set of rules. It's not a precise calculation, as it does not take every color and every block on the grid into account, but my current calculation of possible levels within those sets of rules is 1,185,408,000.