gaming, programming, python January 23, 2013 Jack No comments

Fun with Roguelike Generators

I may or may not be tooling around with a roguelike. Not because I think the genre is dead (it most certainly isn’t) but because some programming tasks are made fun just by their subject matter. I haven’t quite gotten to the point where I’m using “mana” and “damage” and etc. as variable names, but that’s not the first fun part. The first fun part is generating a rogue dungeon level.

Now, anybody that’s ever even thought about developing a roguelike should know about ASCII Dreams written by the developer of Unangband, Andrew Doull. I especially found his series on Unangband Dungeon Generation to provide a lot of insight into generating dungeons that are interesting a long with a lot of interesting history and philosophizing.

In the end, though, I wanted to try my own, naive, hand at the dungeon generation problem. I did take a few major things away from Andrew’s discussion however. Mostly that there are a lot of nice rooms that can be generating procedurally with simple tricks and, failing that, having a system for “vaults” (which are various, hand-designed rooms with interesting features) can be interspersed for extra flavor. Also, various features added to rooms, like water, lava, ice, minerals, rubble, etc. compel players to explore.

Most of this I’ll get to later, if ever, with my toy generator. The first problem is generating the topology of the dungeon itself.

My Approach

Now, one thing that I’ve found annoying about classic generation algorithms is that they tend to have a lot of really long tunnels. This is because rooms are generated at random across the static map and then, if they haven’t merged together, are connected by tunnels. This has never felt right to me. I understand that – in universe – a dungeon might not have the most sensible design, but having long winding tunnels are boring. Doing connectivity checks on the rooms is boring as well. While we’re at it, I don’t want to have a predefined playing field (array) to work with. I’ll put a limit on the area of the dungeon level, but if it’s a whole bunch of tiny rooms in a very long line, so be it. Unfortunately, I also want the level to be consistent (i.e. no physics violating overlapping inconsistent geometry) so it seems inevitable that the level will eventually be represented on a global grid, but at least that grid will be bounded and reasonably shaped to the level. If necessary, after the level is fully generated the excess grid could be eliminated just by noting where one room enters into another.

So, what I wanted to do was generate a dungeon level that is both tunnel free (for the most part), consistent and connected a priori. Interesting stuff like themed-features, rivers, lava flows, etc. could then be painted over the level geometry in broad strokes.

Problems vs. Classical

There are some troubles with this approach. The first of which is that it makes multiple level consistency really hard with multiple staircases. For a classical generator, you can randomly place down staircases on one level, and then replicate that pattern with up staircases on the next level and ensure that you have rooms to encompass them. This works when you’re going to manually connect all the rooms in the end, but it doesn’t work so well when you’re building a pre-connected level. As such, either there has to be only a single up and down staircase per level (not a bad idea, really) or you have to throw that level of consistency out the window and just match arbitrary up and down staircases. This means that you could have two down staircases right next to each other that would teleport you to different ends of the next level, but in a gametype that traditionally promotes save scumming (i.e. if you go down the same staircase twice, the level is different each time you descend) I think that’s acceptable.

Another problem is that, without tunnels, the dungeons are more likely to be dense. That’s a good thing in the fact that it gives a lot more interesting rooms close by and the player spends a lot of time in an environment. It’s also a dangerous thing because it means there’s a lot fewer twisty places to get out of sight of pursuing monsters. I think that’s acceptable as well, although it’ll be something to account for if I ever get around to generating monsters.

Implementation

I decided to bang out a proof of concept in an evening. Breaking down the logic, the easiest way to generate in this fashion is to generate one room, which will be the root. Then, generate another room. Connect these two rooms with a doorway, then that whole complex becomes the root “room”. Rinse and repeat until the dungeon is of a certain size.

In order to encompass this, I came up with a class for Space. A Space is any arbitrary portion of the dungeon level. It includes a 2-dimensional array geometry that describes what’s in that space. One Space’s geometry can be added to another Space’s geometry with a set overlapping point. A Room is just a space with a name and whose geometry is likely a single room, but is arbitrary. Then, special types of rooms, like one mentioned in Unangband as the core type, two overlapping rectangles (which results in single rooms, crosses, T-shapes, L-shapes, etc.) are just Rooms with special geometry generation.

Expand Code

I got a little lazy with the execution of __main__. There’s a cleaner way to deal with matching up the direction end-points (hell, just take a random one and rotate the entire room to match, really) but for an evening’s playing around I think the results are actually pretty nice.

Expand Example

Not many long tunnels, and a large number of rooms (which are indicated by different letters. Doorways are +s. There are still, of course, some places the geometry doesn’t make sense. Usually when two joined rooms have a doorway and also have adjacent open blocks (like P and H in the above). However, all in all, not bad for an evening’s screwing around.

Leave a Reply

Your email address will not be published. Required fields are marked *