I'm working on a game using procedural generation and although the game is nowhere near done I thought the generation technique itself was interesting enough on its own to post about.
Rather than try to explain it myself I'll just send you to someone who already has, better than I likely could. BorisTheBrave: Graph Rewriting for Procedural Level Generation
Instead, I'll just share some of my initial results. The general idea is to generate the "big picture" details first and then successively refine them to build a fleshed out so the levels generated here are shown at 1/8 scale. Eventually every pixel in these maps will expand to be one tile at full scale with additional generation filling in the fine details along the way.
The rules I'm using a pretty simple for now; they were mostly intended to help me shake out any bugs in the graph rewriting system itself. The actual rules I end up using will probably be somewhat more complex but even so I think I'm already getting some decent results.
The Cycle
The first thing I do is generate a cycle with a start (green square) and an end (red square.) The idea for each level is you go in, get whatever is waiting for you at the end—treasure, a boss fight, whatever—and then have to get back out. Having a cycle gives you multiple potential routes to accomplish that.
At the moment the cycles go one-way—although it's not shown—with one path leading toward the end and the other path leading from the end back to the start. But you could have two paths heading towards the start where one might be shorter but full of enemies and the other is longer but relatively safe, and all sorts of other variations.
Terrain
Next up is terrain. For this demo I just have two terrain types, stone and water. You can have both types on a single tile giving you wet stone. The rules are written so that stone and water will never touch directly but will always have wet stone in between. This also results in the occasional patch of wet stone bordered by either stone on both sides or water on both sides which helps to vary things up a bit more.
For the actual game I'm thinking I'll just have abstract terrain types: terrain-1, terrain-2, etc. Then each level will have a randomly chosen theme and that theme will give me a terrain palette which will assign actual terrain types. So you could have fire level and ice levels and so on.
Enemies
The enemy rules are fairly straight forward. There are four types:
- Large enemies (big X)
- Small enemies (small x)
- Swarms (clusters of small enemies that attack together)
- Guardians (in a white box with a border. When you come into their
area everything closes off and you can't continue until you defeat
them. Basically mini-bosses.)
The red ones will be visible as you approach and the yellow ones will be hidden and ambush you. You'll never get two large enemies right next to each other but any other combination of enemies is possible.
Obstacles
Obstacles show up on the map as locks and keys but they may not be actual locked doors requiring keys. They're just anything which requires you to do or obtain something in one part of the level in order to progress in another part. The "key" could be an actual key but it could also be a lever or a puzzle or a new ability. Maybe you need to drain water in one area to reveal a door in another. Whatever.
This, in particular, is an area where I think graph rewriting shines. Since at this stage the whole level is represented as a graph and the path from start to end and back to start is a directed sub-graph, it's relatively easy to ensure that keys never end up behind their associated lock. The lock and key are initially spawned on the same tile with keys optionally then being moved backwards along the path but never past the start.
At the moment there's a 50% chance of a key moving on each iteration of the rules so, on average, keys are found fairly close to their locks but I can tweak the probabilities to have them move either more or less.
Rooms
Rooms are added to empty areas near the main path. Rooms are either big or small and once placed one or more doors are added to the room connecting it to other rooms and/or the main path.
The dark gray bars connecting the rooms to the path are just to show roughly where doors are and how they connect up to the main path. There won't be literal corridors to every room. Either the rooms will be moved closer to the main path or the surrounding terrain will be expanded to the edge of the room.
At the moment the rooms are all just kind of plopped down on top of each other. Whether overlapping rooms merge into a bigger room or where exactly the walls between them will be will be figured out at a later stage.
Next steps
Next is to take this simple set of rules and and basic level layouts and turn them into full-fledged level maps to get the basic infrastructure in place to handle that process.
After that I'll probably take a break to work on actual game mechanics before really diving into the level generation rules.
[Please log in to post a comment]
