Over-engineering dungeon generation

[RogerN]

I've been working on a new variant (yeah, I'll probably never finish it) and I decided to overhaul the dungeon generation code a bit. I'm sure my techniques are overly-complicated, inefficient, and generally involve more programming work than necessary... but I rather like the results so far.

A few quick notes:
- I'm using the SAngband character set at the moment, mostly because I liked the doors
- I'm writing everything in C# because I'm a lazy bum who doesn't like to deal with memory allocation issues
- I've only implemented a handful of basic room types. It's very easy to add other types of rooms later, though.

Here's a quick preview of the dungeon generation output.

So why did I even bother writing a new dungeon generator?
1. IMO it's actually a very fun and interesting programming exercise
2. I wanted to be able to cram more rooms into a smaller space
3. I didn't like the Angband-style corridors; they meander a little too much for my taste

From here I'll just describe the techniques I'm using. Feel free to tell me that I'm going about this all wrong

Step 1: Make a random list of rooms

At this point I don't worry about drawing rooms on the map or even deciding where they go. I just randomly create a list of 30-40 rooms with defined sizes.

Step 2: Room placement

I start placing the rooms by putting the 1st room in the center of the dungeon. The remaining rooms are distributed by essentially playing Tetris

At each step, the algorithm considers the dungeon from a different direction: from above, left, right, or below. It really does play a form of Tetris at this point. It looks for the deepest hole into which it can slide one of the remaining rooms. The room is then placed into the hole, leaving 1-4 tiles as a buffer.

We keep going until we run out of rooms or the Tetris algorithm has failed to work from every direction.

Step 3: Which rooms should be connected?

Now Angband just connects rooms randomly. It might (and frequently does) try to connect rooms on opposite sides of the map, and it doesn't care if the rooms between get turned into swiss cheese.

Instead of random connections, I decided to use delaunay triangulation of the room coordinates. The resulting triangle edges form a pool of room connections that I construct the tunnels from. Not all of the triangle edges are used to make tunnels (that would make too many tunnels), but the triangulation ensures that tunnels are frequently drawn between neighboring rooms.

From the edges that were obtained during the triangulation I construct a minimum spanning tree; this ensures that there are no disconnected regions of the dungeon. I use approximately 30% of the remaining edges to make additional tunnels, so that there are multiple paths between rooms.

Step 4: Drawing tunnels

Sometimes I like Angband tunnels, and sometimes they're totally crazy. They can move in and out of the same room multiple times, bend back on themselves, and generally behave in a very illogical fashion.

I wanted my tunnels to be a little less erratic: more straight (on average), but with a few bends to add flavor and tactical complexity to the dungeon. I settled on using the A* pathfinding algorithm, with the following additional considerations:

- Similar to Angband, tunnels into and out of rooms are only allowed in certain areas. We don't allow the pathfinder to move through certain types of rock.

- The pathfinder incurs a cost penalty whenever the tunnel makes a turn. This forces it to prefer straight sections

- I'm using Perlin noise in order to define invisible regions of "hard" rock. The pathfinder incurs a penalty for trying to move through hard areas. This prevents our tunnels from being completely straight.

- It's cheaper to move through existing tunnels. Therefore the pathfinder will prefer to meet up with an existing tunnel whenever possible, creating intersections

- Some of the tunnel intersections are artificial. One of the random "room" types is actually just a solid block of granite, but it still gets considered as a room when everything is connected. So when adjacent rooms gets connected to it it appears to be a natural tunnel intersection. This also causes occasional dead-end tunnels which are great for staircase placement.

[Antoine]

Originally Posted by RogerN

I've been working on a new variant (yeah, I'll probably never finish it) and I decided to overhaul the dungeon generation code a bit. I'm sure my techniques are overly-complicated, inefficient, and generally involve more programming work than necessary... but I rather like the results so far.

It's looking good already!

Remember a dungeon does not consist only of rooms and corridors. If you can think of innovative ways of placing monsters, objects and other features, it will be a good thing.

A.

[andrewdoull]

Originally Posted by RogerN

Some of the tunnel intersections are artificial. One of the random "room" types is actually just a solid block of granite, but it still gets considered as a room when everything is connected. So when adjacent rooms gets connected to it it appears to be a natural tunnel intersection. This also causes occasional dead-end tunnels which are great for staircase placement.

Nice hack rendered problematic by the original Angband tunnelling code as it doesn't tunnel the first grid. Obviously you've avoided that particular issue here.

That's quite a few rooms you've managed to pack into the level. What's the average room count per level (including or excluding 'room junctions')?

Also, what's the line count for the implementation?

Andrew

[Nick]

This is very cool. I'm looking at revamping level generation for FAangband in the next version, so thanks for giving me some stuff to think about.

[RogerN]

That's quite a few rooms you've managed to pack into the level. What's the average room count per level

Right now I'm only trying to create 40 rooms max. Since they're packed pretty tight I'm using a smaller overall dungeon size than Angband. However, if I expand the dungeon to full Angband size (198 x 66) then I can usually cram 90 rooms inside, including intersections.

Of course it varies a bit depending on the sizes of the rooms. The number might shrink as I add larger room types.

Also, what's the line count for the implementation?

That's also difficult to say since I'm reusing a lot of code. The triangulation code came from here , while the A* code and the perlin noise generator were borrowed from another one of my (failed) projects.

Excluding the reused bits, the amount of new code (not ported directly from Angband) is probably about 300 lines. That count also excludes the code for picking room types, etc... That's C# code, though, so if the implementation were ported back into C then it would probably grow.

[takkaria]

Nice dungeon, though I'd suggest that smaller levels than Angband uses at present are pretty much a good thing. (It used to be that dungeons would be much more size-variable than they are now.)

Originally Posted by RogerN

- I'm using Perlin noise in order to define invisible regions of "hard" rock. The pathfinder incurs a penalty for trying to move through hard areas. This prevents our tunnels from being completely straight.

Hmm. Try placing streamers of quartz/magma/hard rock/whatever through the dungeon before generating any rooms, and then tweak the pathfinder to avoid those rather than using a noise function, maybe? I dunno what the results would be like, but it would reduce work if you're planning to have streamers anyway and results in some nice internal consistency.

[darkdrone]

good work !

i've been always meaning to do a Dungeon Generator in C# , but somehow my line of work doesnt offer too many opportunities...

or the time to!

would like to look at that code there sometime !

[RogerN]

Originally Posted by takkaria

Try placing streamers of quartz/magma/hard rock/whatever through the dungeon before generating any rooms, and then tweak the pathfinder to avoid those rather than using a noise function, maybe?

Using the streamers was my actually my first idea for improving the tunnels. Unfortunately the effects weren't all that great. I think there are a couple of reasons why:

- There's only a couple of streamers per level, so most of the tunnels are unaffected by them

- Streamers are usually very long. The pathfinder just ignores them most of the time because crossing the streamer is inevitable. There's no benefit in trying to avoid it.

But using perlin noise isn't much of a hassle. Since I already had the perlin noise function lying around, it was only 4 or 5 lines of code to tweak the pathfinder.

would like to look at that code there sometime !

I'll post it when I get a chance. There's very little functionality, though, other than dungeon generation. You can walk around, open doors, etc... but there are no monsters yet.

[Mangojuice]

Originally Posted by RogerN

I'll post it when I get a chance. There's very little functionality, though, other than dungeon generation. You can walk around, open doors, etc... but there are no monsters yet.

I'll look forward to that, too. In my variant, Z+Angband, certain quests take place in "castles" that are meant to be densely packed with rooms. I'm really not so happy with the way they look right now... but the kind of well-packed dungeon your code creates would be great! I'm filling up a square region by recursively dividing a rectangle in two.. and it gets a little dull.

Of course, I maybe don't need the code. If I have to port it back to C anyway, I might as well just implement the algorithm myself.

[RogerN]

I've posted the source code for anyone who's interested in playing with it. It's well-documented (for me at least). Just a couple of notes:

- I'm using Visual C# Express 2005. But the code should also compile in VS 2008.

- If you want to explore the dungeon properly then you might consider modifying the CreateRandomDoor function so that it only creates open doors. I haven't implemented lock-picking or searching for secret doors, so you might get stuck otherwise.