Procedural dungeon generation is a fun exercise for programmers. Despite the crude interface, such games continue to spark interest. A quarter century ago, I wrote a dungeon generator in procedural Pascal; now I’ve taken that old code and converted it to C#. (It’s amazing just how fast it runs on a five-year-old i7 950 PC with 16GB of RAM.) If you want to follow along, you can find my code for the project on SourceForge.  The first part of the program generates the rooms in a multilevel dungeon. Each level is based on a 150 x 150 grid and can have up to 40 rooms. Rather than just render boring old rectangular rooms, there are also circular rooms. (Rooms that combine two shapes into a single design would be pretty interesting, but I’ll leave that to you.) Check out the latest jobs involving C#. Each room is generated at a random location, so every location within the room is checked to make sure nothing’s been placed there already. If something else is present, the program shreds that room and tries again somewhere else, up to 100 times. Once the generator can place a room in a totally empty space, it writes it to the map. (Each location on the map contains a location type, a corridor object and a room object. When a location is a corridor, the corridor object in the map is the actual corridor object. Likewise for rooms: Every location in a room's room object is set to that room.)

How to Generate Circular Rooms

The file CircleData.cs contains data used to draw rings around a point. There are 35 concentric rings with three arrays holding:

• The number of points in each ring
• The offset into the points x,y array where the rings starts
• The x,y offsets of the points in each ring relative to the center point

This data was generated years ago from a text file that I built by hand, adding each ring with a different character 0-9 and then A-Y. I wrote a program to process that file and generate this file.

Rooms Are Okay, But…

…not much use without corridors. ("You appear in a room in the dungeon. There are no doors and the oxygen runs out pretty quickly. You are dead.") We not only need corridors, but for all the rooms to connect to each other, which is a slightly harder problem. We want the player to leave a room, wander the corridors, and eventually reach every room in the level. Every room can have up to eight doors, and each is nonexistent (null) or linked to a corridor. Doors are defined as a List<Corridor> and initialized to eight nulls; these are accessed via a room as Doors[3] etc. Every corridor starts from a room and holds a reference to the room. Grid Points occur every six pixels in both dimensions and are held as a flag in the DungeonLocation class. Corridors run along them, but feel free to change the grid point interval, which will affect the character of the corridors. As corridors grow, each is given a segment length of 3-6 locations. If a corridor hits a gridline at the end of the segment, it picks a random direction: left, right or straight ahead.

Sets

The key to it all is using Sets, more specifically the generic HashSet<T>Class type. HashSets provide an Add method for adding items to the set, as well as a Contains method to check if the item is in the set. A HashSet is a container, so HashSet<Corridor> provides an easy way to check the attachments between corridors. For rooms, there's a HashSet<DungeonRoom>. This holds a set of all rooms that can currently be reached from a particular room. When two corridors meet, the two start rooms do a HashSet.UnionWith() with each other; so if room 1 and room 2 get connected, and room 1 is already connected to rooms 3, 5 and 7, and room 2 to rooms 4, 6 and 8, rooms 1-8 are now connected. The level is constructed by adding corridors until all rooms are linked together. Note that when a room is created, it adds itself to the linked rooms. That's this odd-looking line in the DungeonRoom Constructor:

ConnectedRooms.Add(this);

This is a convenience, so when two rooms are linked, there's no need to explicitly add them to each others' ConnectedRooms set.

Program Architecture

There are classes for dungeon rooms, levels, corridors and the dungeon itself, but the bulk of the work is done at the dungeon level and the corridors. Corridors are constructed with a reference to the Map, and the Map holds every corridor location (thanks to the LocationType of Corridor as well as links to the corridor objects). As corridors grow, the program places temporary corridor markers. If a corridor can’t link to another room or corridor, the program considers the attempt a failure and removes it. If it succeeds, the corridor is made final, and the temporary marker replaced with a permanent one.

Conclusion

Looking back at my original code, I'm amazed I got it working in the first place. The conversion was thrown together very quickly and is not a shining example of C#. For instance, I use a class Atts for holding some common functions and a little bit of global data; there are also a couple of places where corridor placement could have been optimized better. However, the dungeon generation is still very fast, and could provide a good programming example for anyone exploring what C# can do. Image: David Bolton