Ranger Sheck's Blog

There are a lot of good resources out there for Procedural Content Generation. The PCG wiki lists a ton, and if you’re looking to read up on the subject, it’s a great place to start.

A lot of these ideas are derived from the original Nethack game (and predecessors like Rogue and Angband). As the PCG wiki says, there are two basic methods to dungeon generation: you either start with a bunch of rooms and then connect them, or you start with solid rock and carve out a maze.

As you might expect, implementations of the first method are more widely used. I’ve been playing Chocobo’s Dungeon off and on for a while now (over a year, I guess), and whenever I play it I start thinking about procedural generation. It’s quite obvious that the dungeons in Chocobo’s are a bunch of standard room shapes randomly scattered about a floor and then connected via corridors.

There is a code sample and live demo (in javascript) linked toward the end of this article, but if you’re impatient and you want to see what the heck I’m talking about, here is the demo!

Starting with the Rooms

In some cases, the shapes of rooms might themselves be randomly derived. I noticed that in Chocobo’s, there were some definite pre-created room shapes. I decided to try it that way myself. I created a couple of text files to store each room-shape’s data. I used a simple, arbitrary code for “drawing” the rooms with characters:

An example room:

W+WWWWW
Wfffff+
WfffffW
WfffWWW
WfffW
+fffW
WW+WW

Toss some Rooms together, one Row at a Time

At first it’s tempting to be really random when throwing rooms together. Most of the time, however, we want our rooms to collectively fit into a nice neat square or rectangle. Personally, I don’t want my rooms too spread out either. Which lead me to the next temptation – just create a grid and put one room in each cell of a grid. I think you can already guess how boring that might look. It’d be like someone built a dungeon on a tic-tac-toe board.

So I’m going for a compromise. First, I start with an arbitrary size limit – like: 30×40. Then I take things one “row” at a time – and by “row”, I mean a row of rooms. I pick a room at random, stick that into a list. I keep track of how much x-space (width) this room is taking up out of my maximum. I pick another random room (narrowing my list down to only rooms that will fit in the space remaining – adding 3 units to account for corridors in between), add it to the list, add up the total used space, and so on.

What I end up with is a handful of room shapes. I randomize the order of my list and start placing them in a row – as if I’m sticking objects side by side into a box – taking care to pad the breaks in between with 3 units to make sure there is minimum room for a corridor. Then I figure out the leftover horizontal space on the end of the box. I redistribute that space randomly throughout the whole “room row”, causing rooms to space out from each other a little if there is extra room.

At this point, the room-row is as tall as the tallest room. I can now shuffle the shorter rooms up and down randomly. Here’s a sample room-row:

W+WWWWW              WWW+W
Wfffff+   WWW+WWW    WfffW
WfffffW   Wfffff+    WfffW
WfffWWW   WfffffW    +fffW
WfffW     +fffffW    WfffWWWWW
+fffW     WWW+WWW    Wfffffff+
WW+WW                WfffffffW
                     W+WWWWWWW

Then we move on to another row of rooms, and another, as long as we have space to accommodate them. The key to keeping this as un-grid-like as possible is variations on room shapes – particularly, variations on widths and heights. Try making rooms that are large, small, long, tall, L shapes (pointing in various directions) and other interesting shapes.

Connecting Rooms with Corridors

There are a few different ways to go about generating corridors. You can specifically try creating them room by room, ensuring that every room is connected to at least one other room; the benefit of this method is that you never have to worry about having a map split into two segments, unreachable from each other.

I decided to go another direction though: almost totally random connections. The side effects of method are: a) you are not guaranteed that all rooms will be connected – you have to do some kind of test (like a flood fill) at the end and discard your dungeon if not all floor tiles are reachable; and b) you get some interesting results where rooms might connect to themselves by an external corridor across one side. I liked this second side effect, since it adds just a little less predictability to the process, so that’s why I’m doing it this way.

First, I find what I call the “nubs” of every room. These are the points out in space, just off the connector points that I used a ‘+’ to designate. I find each ‘+’, then ask “where is the blank space from here”? In other words, from the (x,y) of the ‘+’, I try N, S, E, W until I find the coordinates that have just a space (rather than a ‘f’ or a ‘W’). Then I take a random ordering of the “nubs” and for each one of those, I try connecting it randomly to every other. I check to see if a corridor could be drawn by first checking to see if a rectangle could be drawn, with each nub as a corner. If I can draw a rectangle without crossing any other filled coordinates, then we go ahead and make a corridor.

Drawing a Corridor

Making a corridor is pretty easy, really. You have a start point and end point. First, you have to determine which x-direction and which y-direction you need to go. For example: if your start is 2,3 and your end is 6,7, then you need to go positive in both x and y. If your start is 2,7 and your end is 6,3, then you need to go positive in x but negative in y. Then we randomly decide – either step in the x direction or step in the y direction. Each step we take, we make sure not to go over the ending x or y. For example, if we reach the x destination, then we stop picking x or y randomly and instead just step in y direction the rest of the way.

W+WWWWW          
Wffffffff WWW+WWW
WfffffW f Wfffff+
WfffWWW ffWfffffW
WfffW    fffffffW
+fffW     WWW+WWW
WW+WW           

an example of a randomly drawn corridor

Notice that we didn’t bother with the walls – we’ve only mapped out the floor tiles between the start and the end points. After the floor is drawn, we can add walls by cycling through every floor tile and checking N, S, E, and W of each one. If there is a blank tile next to a floor tile, turn that blank into a ‘W’. Finally, we replace any unused ‘+’ tiles with a ‘W’ as well.

Code Sample and Live Demo

I wrote this code originally in Ruby, since it’s going to become part of the code-base for Aethora (no, you won’t see these kinds of dungeons in Aethora, but you will see a spin-off: a more “dungeon crawler RPG” type of game, less “tactics/strategy” type of game). I’ve taken the time to rewrite the algorithms as javascript so that I can demonstrate it easily on a web page and that more people will be able to dig into it and read it (admitting that more people are familiar with js than ruby).

Requirements for this code: I used jquery this time, so you’ll need that I’m using 1.4.2). I’m also using the small but awesome lowpro library, which allows for an object-oriented style way of writing behaviors for events on elements. This library was extremely useful when used with prototype, since prototype lacks the handy “attach” functions that jquery has, but I still find it nice for jquery because it allows me to organize event handling in a clean way.

If you view the source on the page (that I’m about to link to) you’ll notice a couple of other js files that I’ve created:

• array.js – just a few helper methods for bastardizing the Array prototype to include sum, max, and min
• room_template.js – a simple object class for encapsulating those room shapes that we set up in the beginning
• mapper.js – an object class used to encapsulate the map generation functions

You’ll also see a small block of js in the source of the index file where RoomGenerator is defined – that’s the lowpro behavior. We just attach it to the “generate” form.

The room shapes are in textareas, so go ahead and tweak them if you want. Also you can play with the dimensions – I’ve given you a starting size of 30×30, but put in whatever you want. Use at your own risk!

Procedural Dungeon Generation Demo

One more note – notice that in this demo, we’re not checking to make sure all the rooms are connected. In my real code, what I do is: first generate a dungeon. Second, make a copy of the dungeon. Grab a floor tile of the copy and replace it with an ‘X’, and flood-fill out from there, replacing all f’s with X’s. Then I loop through the copy and make sure there are no f’s left. If there are, then I know those floor tiles were unreachable by flood-fill, and therefore unconnected. I toss out the dungeon and generate a new one (no, it doesn’t really take long to randomly generate these dungeons; a few milliseconds is all). Another option would be to somehow look for a way to force a connection between any disconnected rooms, by just finding any ol’ space where a corridor might fit.

Bonus Round: Converting ‘f’, ‘W’ into images

We’ve covered the generation of the rooms and corridors. If you’re making a text-based game, then just using ‘W’ to designate a wall works just fine. But if you want to convert those walls into image tiles, you’ll want to figure out how to place corners, horizontal walls, vertical walls, connecting walls, and so on.

To simplify this task, I decided to name my walls based on the directions a wall tile connects to other walls. Some examples:

WW
W

The first tile is a corner wall. It connects to a wall to the South and a wall to the East. It’s image name is wall_s_e.
The second tile connects only to the West: wall_w
The bottom tile connects only to the North: wall_n

WWW

The first tile only connects to the East: wall_e
The middle wall tile connects to the East and to the West: wall_e_w.
The last tile connects to the West: wall_w

It may seem a little backwards at first – because you think a wall is sticking out to the South, but it’s connecting to the North, so we call it wall_n instead of wall_s. There is a reason for doing it this way – it’s much easier to write code to detect which directions walls connect in than which directions they “stick out in”.

So anyway, it’s just a matter of looping through all the wall tiles and then checking: do I have a wall to the North? do I have one to the South? East? West? Okay, on to the next wall tile.

Before you know it, you’ve turned your W’s and f’s into tiles:

click the image for a larger version

Well, that’s all for today. If you have any questions, don’t hesitate to ask. I’m too lazy to put a license in the js code itself, but you can consider it licensed under MIT (so do whatever you want with it; credit would be nice, but not required). If anyone has the time to port this code to PHP, Python, perl, .NET, or whatever, please let me know. I can provide a ruby version on request, but if you’re patient, I do plan on releasing a whole giant chunk of the Aethora code base (which is Ruby on Rails) as open source.