Generating Cool Levels for Rift Wizard

Rift Wizard is a roguelike with a big focus on combat.  The levels are designed to be short, focused, and memorable.

The game launched recently on steam in early access.  Many players gave feedback along the lines of "although I have access to many interesting tools for my own character, the situations I use them in are not adequately varied".  So for the first patch, I worked on, among other things, a terrain generation overhaul.

There are many terrain generation algorithms available.  Unfortunately for me, most of what I found was set up to generate similar feeling maps each time.  There are algorithms that always generate a series of connected rooms, there are algorithms that always generate organic feeling caves.  This was a problem for Rift Wizard, which focuses on tactial spell battles on short and focused maps.

What Rift Wizard needed, was an algorithm that would generate maps which felt different each time.  Encountering new challenges each playthrough is an important part of the roguelike genre.  The more novel and different these challenges feel to the player, the deeper the experience becomes. 

Rift Wizard is, as the name implies, a game about spells.  There are spells for every situation.  Nightmare aura shines in coiled mazes, while blinding light excels in large open spaces.  Summon spells are defensively useful in maps with chokepoints, but offensively more useful in maps with wider passages.  It was important to Rift Wizard that each playthrough had a slightly different optimal build, and terrain generation could be a big part of that.

Eventually I came up with a system I liked very much.

Heres the system in action, generating 4 levels:

Each of these maps is a very different experience for the player.  Some of them have lots of open sight lines, some are maze like, some are cavelike, some have lots of cover, some seem organic, some seem manmade- there is wide variety in how the various spells and monsters in the game can interact with all these different terrain configurations.

Here is how the system works:

There is a list of mutators.  Mutators take in a map, and, well, mutate it into another map.
Some of the mutators are seed mutators, some are not.  This will be important later.

Step 1: Choose a random tile type (Floor, Wall, or Chasm) and fill the map with that tile.
Step 2: Run 1-5 randomly chosen seed mutators.  Seed mutators are mutators likely to produce interesting results regardless of the input.  Some examples:

Drawing random lines
Creating lumps
Adding white noise
Making squares
Make a grid of walls or floors every nth tile

These mutators all operate by checking which tile type is required and creating more of that tile type, pushing the map towards a more balanced state.  So if the map starts as all floors, then lines and lumps of walls and chasms will be created, whereas if it starts as all walls, lines of floors will be created.

Step 3: Run 0-10 randomly chosen general modifiers.  These include seed modifiers, and also include other modifiers like:

Fold the level in half to make it symmetric
Run 1-5 iterations of Conway's game of life
Create a 1-6 tile wide border of walls or chasms around the level
Convert big chunks of one terrain type to another random terrain type.
Find big chunks of one terrain type and put slightly smaller chunks of another terrain type inside of them
Create 4 way radial symmetry in the level
Diffuse all tiles of a selected type outwards

These would all be boring on their own, but can create cool and unexpected effects when combined.
 
Even with a small list of modifiers, a huge number of combinations can happen.  

The order of combinations can be quite important as well.  

Symmetry operations near the end is obvious, whereas symmetry in the middle of the process is less evident , though it still leaves traces of symmetry in the end result:

The Border mutator is very obvious when introduced as the final mutator, but still has a subtle effect on the level when used near the beginning:

The first 3 steps are the main meat of the terrain generation.  It usually generates something cool, but can easily generates something unplayable- a level of all walls, or of several isolated islands.  To fix this, we have steps 4 and 5.

Step 4: Check how many walls and floors tiles the level has.  This is to check that the level is "interesting".  A level too few or too many floors is considered uninteresting.  If the level is judged to be uninteresting, run random seed mutators until the level qualifies as interesting.

Step 5: Separate the level into connected components, and then connect all of them.  This step is done twice- first for walkable tiles, and then for tiles that can only be flown over (chasms).  Isolated pockets of chasms are really annoying when flying enemies teleport into them and never leave.

The beauty of the last 2 steps, is that they free us from having to think too hard about mutators.  They do not have to maintain connectedness, nor do they have to guarantee balance- though it is certainly nice if they  tend towards it, as it will reduce the number of random mutators that have to be used in step 4 to correct the level.  These 2 steps are pretty good at turning random junk into playable levels:

For instance, a blank grid becomes a neat maze:

While a set of random squares becomes a traditional dungeon map:

White noise over a chasm is almost already an interesting playable map, connecting it gives us this chaotic organic space:

Generally though, it makes something like the maps shown above.

One tip I would give to others trying to do similar systems, is to log early and log often.  This process creates alot of boring, blank outputs during development.  Seeing exactly what happened to create that was incredibly helpful.  As an added bonus, the shipping version of the game still includes the levelgen logs- which are kind of a cool thing to let the players look at.  Roguelike fans tend to be interested in such things.

Before this update, Rift Wizard had a much more deterministic, hand specified algorithm.  It would generate paths, then open spaces, then had a chance to convert the insides of some of the open spaces to walls or chasms.  This can be expressed within the new system as a sequence of mutator choices, which is very nice and elegant.  It also means every level which could previously generate, can still generate.

The feedback so far on the beta has generally been that the new maps are more interesting than the old ones, and more varied in difficulty.  Rift Wizard forces the player to kill every enemy on the level, so the maps can vary wildly in length depending on how long it takes to path from one enemy to the next- this number can be much higher, or much lower than before with the new system.

Future improvements I would consider would be 1) more modifiers, 2) add more terrain types to make the system inherently more interesting and 3) segment the map into multiple subregions that each have totally different mutators applied to them.  Actually, (3) could perhaps be implemented as a (recursive) mutator.

I think this method could be applicable to any roguelike, the connectivity step might have to be modified for generating larger dungeons.  The hardest part of applying it to larger maps would be that sometimes these maps end up being nightmarishly twisted to navigate, for games with larger maps, there might need to be another last step to mollify that tendency.

Rift Wizard is currently available on steam, and the first patch launches tomorrow.