SeaBomb – Random Level Generation
I'm pretty sure this is about the millionth random level generation blog on the internet. So, with that in mind, I'll try keep it fairly short, include pictures, and cut straight to the chase.
Randomly generated content isn't always ideal for game design and game play. There are fairly wide views on its use (See this article by Ben “Yahtzee” Croshaw “Why Randomly Generated Content Sucks”). Given that, why would I go for randomly generated levels? Well, let me tell you why I dare defy the great gaming gods.
- My levels are short and very quick to get through. The randomness should never cause the player to feel lost, just send then down the odd wrong direction every now and then.
- I'm only one person. It's in my best interest to get the most mileage out of every single asset I create.
- I'd like to have the game be able to progress indefinitely.
- If I some how managed to win the game dev lotery, and get noticed by Ben “Yahtzee” Croshaw. A video of him raging over my game and smashing my head in with a randomly generated hammer would be the pinnacle of my career.
Overview
When deciding how to generate my random levels I had a couple of primary objectives in mind:
- The process should be largely data driven.
- Custom designed gameplay areas should be easy to integrate.
- It shouldn't be limited to 2D.
- It should be able to produce visually diverse results.
To meet these objectives, I went with manually 3d modelled level parts. The level parts are built into a tree hierarchy creating the layout for the level. Each part can have as many children as they have connections. The main downfall of this method is that there can never be loops in the level. At the moment, I'm OK with this limitation, and if it starts to bother me I have a couple of ideas of how to address it without adding additional code :)
Level Parts
The level parts are modular peices that the algorithm can place together to build the environment. They are made up of a visual mesh, a navigation mesh, object aligned bounding boxes (to help check if level parts overlap), and connector locators for lining up each part.
The connectors are tagged with a type, and can only connect with connectors of the same type. In my test level, the grate bridges have connector type “B” while the ground areas use a connector type “A”. Gotta love my sweet naming convention. The level parts can also have locators in them that denote various game specific elements, such as the player start location, bases, and health pickups.
Piecing the Puzzle Together
First any random part can be placed down in the level. I start by using a part that contains a base, as this means that the level will always have at least one. Each open connection on the tree is visited, and a part is attached. This can be done as many times as required to produce a level of appropriate size. Finally, all of the open ends are capped off with parts that only have one connection.
When placing a part in the level tree, all specified parts and their connections are tried in a random order until one fits (making sure it's bounding boxes do not overlap with any already in the level tree). If absolutely no parts fit, then the part with the bad connection can optionally be pruned from the level's tree structure (along with all the children of that part).
I've added a few additional steps in to try get extra bases in, keep the levels longer, and make sure there is always a player start location. Writing down the steps can get a bit convoluted, so instead, here's an animated gif of the process:
It is possible to break this algorithm with data, you need to have an end cap for every type of connection. Further more, your end caps must fit with every possible part that has a matching connector type. If this condition isn't met, then you will occasionally wind up with only one uncapped part in your level. Additionally, you can drastically improve the level size by giving more part options.