Procedural Generation discussion

A topic by Yal created May 11, 2016 Views: 680 Replies: 11
Viewing posts 1 to 6

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.

Moderator

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 first step is placing random trees? O_o

Something with that sentence just feels a bit off to me, I kinda feel rendering is the last step. How do you make sure the player cannot leave the level area, and make sure there is a path from the start to the goal?

Then again, with at least four finished roguelike(like)s, I'm pretty sure I'd trust you with pure randomness over some of the other people I've seen using it... at least you know what you're doing. :P As always, what tools you use are less important than how well you use them. (I'd personally recommend top-down approaches to everyone starting out with random generation, since working on a higher layer of abstraction means it's easier to keep track of what you're actually doing)

Moderator

"How do you make sure the player cannot leave the level area, and make sure there is a path from the start to the goal?"

I simply tell the player they have no reason to wander off the map, if they try. No need for a more involved fiction. As for your other question, after placing the trees I generate a forest trail that plows right through them if necessary. Which is... pretty much how you'd do it in real life. Doing the opposite would be a lot more complicated, and putting the cart before the horses on top of that. I'm generating a forest village, not a planned city! (The latter is, of course, exactly what I'm doing in RogueBot. Notice how the algorithm is radically different there.)

That said, thanks for the kind words. I got to this point after many failed attempts, spread over long years. And I'm still a novice at PCG. But my methods work. ;)

There are as many ways to go about procedural generation as there are potential random variable outcomes, it depends on the parameters and needs of the user. There's a pretty extensive resource thread on the subject on tigsource here that people may find interesting.

I also found the .kkrieger demo really facinating for what they managed to accomplish.

Moderator

Wow, that's a lot of links. And of course .kkrieger is a classic, though I shudder to think how obfuscated the code must be. I'd much rather stick to what I can code cleanly, for my own sanity and ability to, you know, reuse my work.

Heh, I can sympathize. I seem to remember they built a custom proc-gen editor to build it though which they called ".werkkzeug", the latest being ".werkkzeug3". I think some versions were released to the public, it's probably still floating around the net somewhere.

I can actually see procedural object generation being a pretty powerful tool, you could export models or textures created procedurally and then use them in something you're manually designing. Especially when it comes to natural things like mountains and trees, it could probably give that variety you need to keep your environments feeling alive. Not sure exactly how reusable a generation code is in itself, though, since many things are only shaped like themselves, and I imagine most generators would only have a relatively narrow span of things they can produce.

Moderator

You'd be surprised. I recommend a classic book called The Algorithmic Beauty of Plants. And I've seen other people do fabulous things with procedural 3D, like entire cities with a variety of architectural styles. See some related work in this thread. As for procedural textures, they are already a thing. There's at least one tool hosted right here on itch.io that generates tile art for games starting from simple rules.

As an aside, the term "procedural texture" is more often used for when you specify the optical properties of a material and the software makes it look right -- like in raytracers, though the Wavefront OBJ format also has limited support for that. But as you might imagine, that basically invites procedural generation. And painting a regular texture in memory before applying it to an object is also a valid technique I've seen recommended.

Gwosh, things sure has come a long way the last few years. (I guess having grown up in the age where 64KB ram was a lot makes me narrow-minded or something. I kept using floppy disks well into the 2000s by pure habit, but having a cellphone too close to a floppy apparently wipes its data, so I had to switch over to USB memories to much dismay).

That tool also looks really interesting. Connecting different modules together seems like a really interesting and (infinitely) powerful approach. In fact, it's more or less what the procedural generation engine I'm currently tinkering with does, and it's not very advanced (and only has three steps at the moment), yet it pretty much beats my previous works. Doing that in the general case...

This got me thinking... what if one'd randomly connect different modules together (in a way that makes sense, obviously)? With THAT approach, I can sort of imagine the whole 'the possibilities are endless' thing for general generation.

Moderator

I'm a bit younger. When I got my first computer, 64K was already the standard...

But I'm not sure what you mean by connecting different modules. Something that would work like the late Yahoo Pipes, or a software synthesizer, except procedurally? That kinda makes me think of genetic programming. Which is, of course, a thing -- and a good thing to think of now and then.

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.
Now the level has loaded, but before the Fade-In, the game checks whether or not this level should be a Challenge level (which show up after every 3 wins in Endless & Gem Hunt modes, and always every 4th level in Arcade Mode). The game then makes any adjustments necessary for this particular challenge, like destroying the Wall.

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.