Tweet
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.
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.
Comment