Procedural Level Generation In Worm Run

This was originally posted on the Golden Ruby Games company blog.

When demoing Worm Run, we often get asked about how the game creates the tunnels that the player runs through. Usually, I launch into a long rambling explanation of the procedural generation in the game, so we thought it’d be fun to break it down in a blog post. I’m pretty pleased with how the level generation turned out, so I’m happy to share the ins and outs of exactly what is going on.

Origins

When we started the game, I was very inspired by (and gleefully sinking amazing amounts of time into) several rougelikes, most notably Derek Yu’s masterpiece, Spelunky. I modeled a lot of the the game’s Map Manager after Spelunky in so much as the game is never the same, but has several distinct areas with their own feel and common structures. Being able to count on the same types of rooms showing up in given areas allowed us to modulate the difficulty level of the game, but still allowed for a level generator capable to throwing out unexpected spaces.

Darius Kazemi has an excellent breakdown of the level creation in Spelunky that is worth checking out as well : http://tinysubversions.com/spelunkyGen/

I read it a few months after finishing up Worm Run, but there’s a lot of really great insight into clever procedural level design there.

Goals

Our goal for the levels in Worm Run were:

A quick note on that last requirement: In most rougelikes, the level generator creates a floor of the dungeon and it’s done, but Worm Run can’t do that because it is a runner. It must continue to add to the map while the player is in the middle of the game without slowing things down or pausing to make more. This became one of the trickier aspects of the procedural design for a game that had to run on mobile devices.

Basic Structure

The entire game sits on two grids, the Tile Grid and the Room Grid. As you can pretty easily guess from looking at a screenshot of the game, Worm Run is made up of tiles that can be empty or filled with ground or a special tile (such as ice or conveyor belts). Everything in the game is a tile, even if the art is bigger. For example, item pickups appear larger than the other tiles, but as far as the game is concerned, they are stored in a single empty tile.

By default, every tile in the Tile Grid is filled with ground. Paths are essentially carved out of this.

The other grid is the Room Grid. The Tile Grid is broken up into 12X12 chunks which are each considered a room. These rooms are the structures used in level generation and in addition to keeping track of their 144 tiles, they store a little bit of info about the path itself (such as which direction the player will move through it, if it is a gravity flip area etc).

By default, all rooms are set to EMPTY, which means they are just filled with ground tiles and are not part of the path the player will be taking.

Some Quick Definitions

Tile - The individual blocks that make up the world in Worm Run
Room - a collection of 12X12 tiles.
Map Manager - the class in Worm Run that handles the creation and placement of new rooms.
Open Room - the current end of the map. This is where the Map Manager will place the next room
Pathway - A collection of one or more rooms that the Map Manager considers as a unit when placing rooms.

Scrolling

Mobile devices cannot contain an ever growing map, and really they don’t have to. The player does not backtrack in Worm Run as doing so tends to mean instant death in the mouth of the worm. So it’s OK for us to throw out old rooms once the player passes through them.

The grid that the game is played on is 228X228 tiles, which corresponds to 24X24 rooms. Obviously, very little of this is ever on screen at a given time, but this space allows rooms to be setup and replenished off screen without the player noticing (most of the time. A little further one we’ll talk about what happens when this fails).

The level generation has the most space to work with when the player is in the very center of the grid, so every time the player enters a new room, the game will try to scroll the grid and everything on it to recenter the player. These scrolls are done in 1 room blocks, so when a scroll happens, everything is moved by 12 tiles either up, down, left or right. The position of the player is also adjusted and the entire operation is imperceptible to the player because everything (including the camera) moves all at once. It seems like nothing happened, but the internal Tile Grid and Room Grid have been shifted over.

Any rooms pushed off of the grid during a scroll are deleted and the game completely forgets about them in order to make space for new rooms. Because these scrolls can destroy rooms, any time we want to scroll, the game must first check to make sure it is safe. The map must pass these checks before scrolling is allowed:
1) The scroll must not destroy any unexplored room that is on the path to the Open Room. Because the path of Worm Run is very linear, almost all unexplored rooms will be required for the player to reach the Open Room.
2) The scroll must not push the Open Room off of the grid. It will be very hard to add new rooms to something not on the grid.

In this diagram, the game will not be able to scroll left because the rooms marked with “!” would be pushed off of the grid, but the player must pass through them to reach the green Open Room.

When the game scrolls, a new column or row of unused rooms (and 12 columns or rows of tiles) will be created. They will default to being filled with ground and marked unused.

Adding Rooms

Whenever the player is too close to the Open Room, the Map Manager will attempts to add new rooms to the grid. When this happens, the Open Room is moved to the current end of the map. This is done using premade pathways that consist of one or more rooms. When the game starts, about 100 of these pathways are generated and stored separately from the grid; as the game goes on, more of these pathways are generated to replace the ones that get added to the grid or thrown out.

Here is an example of a Room Grid (right) with the Open Room marked in green and a collection of potential pathways on the left. Each room is marked with an arrow to show the entrance and exit direction.

In addition to the tiles and room info, each pathway knows it’s entrance and exit directions (top, bottom, left or right). For the purpose of map generation, each pathway has one entrance and one exit, even if it’s a room the player could reasonably enter from either side. For the flow of the game, the Map Manager must know which way the player is moving through the Pathway, even if it is arbitrary.

When adding a new room, the Map Manager looks at the Open Room and goes through the list of pathways it has stored in memory to try and find a suitable one to attach to the map using this set of rules:

1) The exit direction of the room on the map that connects to the open room must be the opposite of the new pathway’s entrance direction (IE, if the room on the map exits to the left, the new pathway must enter on the right). This rule automatically rules out about 75% of the available pathways and is very computationally easy to check, so it is done first to avoid wasting time doing more expensive checks on rooms that might wind up to just be facing the wrong way.

The first pathway here has an entrance on the bottom. It will not fit in the current Open Room which requires an entrance on the right.

2)  The new pathway must have at least 2 overlapping empty tiles with the edge of the room already on the grid that it will be next to. This makes sure that a room that opens on the right, but only has a small path at the bottom does not get placed next to a room that exits on the left, but which only has a small opening on the bottom. Although the entrance/exit direction are correct, there will still be no path.

3) The new pathway must fit entirely in the grid when placed on the Open Room. Since pathways can be made up of multiple rooms, we don’t want to place a 6 room long hall if the Open Room is only 3 rooms away from the edge of the grid. Furthermore, there is a 2 room buffer the game keeps from the edge of the grid to allow for some leeway when scrolling. Pathways that would enter this space when placed are also skipped.

The second pathway is rejected because although it has the right entrance direction, it is long and has two rooms that are too close to the edge of the gird.

4) The pathway must fit on the grid. This means that none of the rooms can occupy the same space as existing rooms that have not been explored. The game does allow for old rooms to be covered up by new rooms.

The third pathway is rejected because the last room would cover up an exiting part of the map.

5) Once placed, there must be a potential path from the end of the pathway (which will be the new Open Room) to the edge of the grid. This is to make sure that the map does not snake in on itself, which will eventually lead to there being no place to put new rooms because because any pathway will cover existing rooms. This is bad.

The fourth pathway would lead the path in on itself, eventually creating a dead end.

6) The pathway should not add any rooms that are currently on screen. It looks bad when the path pops into existence, so the Map Manager tries to add rooms to parts of the grid that are offscreen. There are some exceptions to this, though. For example, if the player manages to get the Open Room on screen, there is nothing that can be done because the new pathway must be placed on the Open Room.

If the new pathway passes all of those checks, the Map Manager adds it to the grid and removes it from the list of potential pathways stored in memory.

The last pathway passes all checks and is added to the grid, moving the Open Room to where the next pathway will have to be placed.

If, however, the entire list is run through and none of the pathways fit, an entirely new room is created (more on how that works in a bit) and added to the end of the list. It is checked and added if it can fit, otherwise it remains in the list of potential pathways. This is done once per frame until a suitable room is created. Pathways in the list that have been checked once for a given Open Room are not rechecked each frame, only the newly created rooms.

The reason I do not just keep creating rooms all at once until one fits is that I need to balance creating the map with not slowing down the player’s game. If the game generates and checks 10 new rooms in one frame, it will slow down to a crawl, so instead I just do one per frame. This almost always finds a suitable room in time, but on the occasions that it does not, a special room, appropriately called an Emergency Room, is created to keep the game going. I’ll talk about these rooms in a bit.

It is worth noting that when a pathway is added the grid, it just becomes a set of rooms that have no relationship to each other besides being adjacent. For example, half of a pathway can be pushed off the grid by scrolling without the other half being affected because once they are on the grid, they are considered separate entities. Pathways are just used in the process of placing new parts of the map.

How Pathways Are Made

So that’s how rooms are placed, but the real thing people usually want to know is how they are made in the first place.

Although the pathways are always different, you will see a lot of similar structures in each area of the game. This is because each area of the game has about 10 prototype pathways that define a specific type of pathway. These prototypes are each a set of rules that help define a specific type of pathway. Some are very similar to each other, and some allow for a great degree of variation, but any pathways created from a specific prototype pathway will have a lot in common with other pathways created from the same prototype. As you play the game, you will invariably begin to notice these types.

Several variation on the Cave Hallway prototype pathway (note that prototype pathways can produce pathways with varying number of rooms):

Several Variations of a pathway I named Telephone (I am very clever):

This allows rooms to feel different but still guarantee that they are interesting and that there is a somewhat consistent difficulty level. For example, although I don’t know exactly how each room in the Temple will turn out, I know that they will be much more cramped than any other area because the basic shape of each room in that area laid out in the prototype rooms just don’t have much space.

Here’s a quick overview of what the prototype pathway for the Cave Hallway looks like. The actual prototype pathway is a C++ class, but I’m going to paraphrase it here just so you can get a sense of how one these prototypes work.

That’s an example of what the Cave Hallway prototype does to create a room: It has a bunch of preset parameters and then does several coin flips and die rolls to make each pathway it makes a little different. Every prototype room is different and most have quite a bit more going on than this one.

Emergency Rooms

As I mentioned before, the Map Manager does a pretty good job of filling in the grid before the player gets to the end of the map, but sometimes things go awry and many frames go by without a suitable pathway being found. When this happens, the player may reach the Open Room, and it would be very bad if the map didn’t expand instantly as a dead end not only breaks the flow of the game in a very literal way, but also invariably means death since the worm will will still charge in and eat the player.

Because the map needs to be expanded RIGHT NOW I don’t want to go through the list of available pathways because there is no guarantee that I will find or make one that fits, and thus far that method has failed anyway or we wouldn’t be here. Instead, there is a separate list of 12 emergency pathways. These are each only one room long, ensuring that they will never collide with any existing pathway, and cover all possible combinations of entrances and exists (which comes out to 12, hence the number). Because of how simple they are and the fact that all entrance/exit combos are covered I can be certain that one or more of these rooms will fit any Open Room. The fact that there are only 12 means I can check and find the one that fits very quickly, so if the Open Room is on screen, the game can find one of these emergency rooms, pop it in and then generate a new one with the same entrance/exit as the placed room for the next time we find ourself in a bind.

Each emergency room is done in the style of the area it is in (Cave has a spike, Temple has a column etc) so they look right along side of the other rooms.

Review

-Pathway prototypes are used to make pathways that the Map Manager stores without putting on the map
-Each pathway is a collection of rooms
-Each room is a 12x12 grid of tiles
-Available pathways are added to the map when the player is near the Open Room (current end of the map)
-Pathways are only placed if they fit the map based on a set of criteria to ensure there will never be dead ends
-Emergency Rooms can be swapped in if the player has reached the Open Room without an available pathway being found that fits.
-When the player is not in the center room, the game will try to scroll the entire grid of tiles and rooms over
-Doing this will bump old rooms and tiles off of the grid, giving just space for new ones.

And that's how Worm Run generates a map on the fly! Feel free to drop me a line at [email protected] if you have any questions or comments about how this works.

You can get Worm Run here:
iOS - https://itunes.apple.com/us/app/worm-run/id569497239?mt=8
Windows - http://apps.microsoft.com/windows/en-us/app/wormrun/f3a97f77-a3f2-4c7b-a9c3-a520462b86d1

UPDATE: Unfortunately, after the closing of Golden Ruby Games, Worm Run is no longer available.