Procedural Room Generation Explained

There are lots of ways to do procedural dungeon generation. I came up with a way that will allow for both really chaotic room designs and fully formed, hand crafted rooms. It’s based on joining smaller patterns together to form the room’s interior. In this post, I’ll do my best to explain what’s going on.

Setup: Defining Patterns

This is a collection of four small primitive patterns, bound in separate colored boxes.
This is a collection of four small primitive patterns, bound in separate colored boxes.

I use the editor to make this room, which contains four basic structures, the patterns. Everything is composed of simple tiles like walls, columns, floor, and water.  Metadata in the room file marks specific tiles to define the pattern area (colored box enclosing the pattern) and two special types of tiles: the inlink and outlink positions. Each pattern has one inlink, shown with an E (for entrance), and one or more outlinks (empty colored squares). These are used to join patterns logically, which I’ll explain later.

For now, let’s walk through each step of the layout algorithm.

1. Create an Empty, Enclosed Room

The blue tiles are empty spaces--I know, it reminds me of Super Mario World too.
The blue tiles are empty spaces–I know, it reminds me of Super Mario World too.

Rooms can be any size–I’m using 31×17 as the default size for now. Each room is enclosed by the basic wall tile. (Walls are automatically blended to their neighbors in a separate algorithm.)

2. Place doorways at the door positions.

The top doorway has a cute little doorstep marker to prevent anything from blocking it off during construction.
The top doorway has a cute little doorstep marker to prevent anything from blocking it off during construction.

Each room has one entrance, and optionally has exits on the three other walls. In this room, we have the entrance at the bottom center, and a single exit at the top center. Some decorative side pillars are added for some ambience.

The arrows are special. An arrow on a tile means that tile is a boundary tile and can be joined to other patterns. The engine knows to start at the bottom arrow, because that’s the entrance door, and that’s where layout begins. The bottom arrow is actually treated as a pattern outlink (explained next).

3. Find a Pattern from the Collection

A pool of pattern candidates is created from the four patterns we defined in the editor earlier. It automatically makes variants that are flipped and rotated in various ways for the ultimate in variety and versatility.

To select a pattern, it goes through each one and tests it against the room’s outlink positions (currently just one, at the entrance door). It checks if the pattern will have all of its floor tiles contained within the room and not intersecting with existing walls or water. Once it has the list of candidates, it randomly selects one, and the layout engine applies it to the room.

It picked the blue pattern from our collection! Excellent choice.
It picked the blue pattern from our collection! Excellent choice.

After the pattern is applied, it clears the outlink marker that was used, so it doesn’t get tested in the next iteration. Instead, we have two exciting new outlinks, provided by the pattern: up and to the right.

4. Repeat step 3

…over and over, until nothing else fits.

5. Ensure a path to the exits

We only have one exit to worry about in this room, so it’s only done once. It essentially does a Photoshop-style “flood fill” of floor tiles starting at the exit’s doorstep position:

We can reach the exit now
We can reach the exit now

This isn’t always necessary, because sometimes the layout engine conveniently places a pattern that enables passage to the exit. The engine will never place a wall blocking the exit, because of the “reserved” doorstep position we added at the beginning.

6. Trim Dead Ends

Anyone who’s played Soulcaster knows how deadly nooks and crannies can be. If you get chased in there, you’re going to have a hard time getting out. So in an act of charity, I turn the unused outlinks (the ones not pointing to floor tiles) into walls.

Much safer
Much safer

Notice it doesn’t get rid of all the dead ends, just the ones created by the dangling pattern links. If I wanted to be truly kind I could have it fully zap the dead ends and ensure circular passages everywhere. But that’s a task for another day.

7. The Finishing Touch

No more empties
No more empties

Leftover tiles are transformed into pretty water. Aesthetics.

So that’s basically it! I’m aware that while this type of chaotic level layout may be interesting, it’s not as cool as having a more pre-planned layout like the old school Soulcasters had. I liked to put concentric circles like walls and moats, have islands with bridges, or an enclosure surrounded by trees that you needed to infiltrate. That stuff’s all coming: the cool thing about this pattern system is that I can define patterns of any size, tag them for special purposes, and link them together however. A pattern could be an entire castle 40×40 tiles in size. It could even leave interior rooms vacant and link into them, populating them as needed.

Spawner placement is the next challenge, something I’ll be tackling this week.

Thanks for reading–and comment if you liked this post and want more of this sort of thing (or if you want to hear about something in particular).

Procedural.

It’s been a really productive week–lots of code cleanup, which always feels so nice. Since refactoring doesn’t make for very interesting dev blogging, my goal for today was to have something new to show. And with just a few extra hours of work…

Soulcaster3 2014-11-21 17-08-10-33When this room layout engine is more robust, I’ll do a more thorough post explaining how it works. You can tell what’s going on if you stare at it…

Realtime Editor Lighting

When I fix the problem with WP uploading GIFs, I can post this sort of thing directly. In the meantime, here’s the room editor which now updates light sources and obstruction in realtime as the room structure changes:

This week is mostly earmarked for editor work, so I should have some editor features to show pretty soon.

Atmosphere

Most of today was spent doing fixes for the editor to handle the updated room definition and pattern format. But that doesn’t make for an interesting screenshot (yet), so here’s a test level with some light sources:

atmosphereIt’s starting to look a bit cooler. Need a few more light sources and better shadow behavior.