Building a dungeon for your character to explore, along with being able to see that dungeon, is one of the most important parts of a Roguelike, and unlike sight algorithms there is a near infinite number of ways that a dungeon can be generated. This article describes a simple map building algorithm using rooms and corridors, which is written in C# 3.5 – links to the code are the bottom of this article.
Building a Map
Using the app is pretty simple: select one of the two options in the combobox in the top left corner and click the button Build and a map will be generated. The property grid on the left hand side can be used to adjust various map building properties, which are discussed in more detail below.
Two options are offered for building a map:
- Build_OneStartRoom – a start room is placed in the centre of a map as starting point, and rooms and corridors are built of it.
- Build_ConnectedStartRooms – two rooms are placed on opposite sides of the room and joined with a corridor as starting point, and rooms and corridors are built of it.
The difference between the two methods is that Build_OneStartRoom() produces a map with rooms and corridors clustered together, whilst Build_ConnectedStartRooms produces a more distributed map that fills more of the map area.
Adjusting the properties, which are discussed in more detail below, can produce maps with different appearances. Here are a few examples:
Build Probability: 100 - this will cause corridors to only be built of existing corridors.
Build Probability: 0 - this will cause corridors to only be built of existing existing rooms.
Rooms to Build: 5 and Maximum Corridor Turns: 25. Nice twisty corridors!
Corridor Spacing: 10, Break Out: 1000. Corridors must be a distance of 10 units away from other corridors. Break Out counter is increased to allow successful map generation.
Map Building Logic
Both of the map building options use the following logic to build a map:
- Place start room or rooms.
- Required number of rooms built? No, go to step 2, else quit.
- Get a random point on the edge of a room, or a corridor,
- Test if the only point is valid. Yes, go to step 3, else step 1.
- Attempt to build a corridor and examine the outcome of that method:
- The corridor has hit an existing room: build corridor
- The corridor has hit an existing corridor: build corridor.
- The corridor operation has completed: attempt to build a room on the end point of the corridor, and if successful build the corridor.
- If break out property exceeded exit the loop. Prevents the loop from getting stuck.
- Go to step 1.
Mapbuilder has a number of properties which can be adjusted to determine the appearance of the generated map:
- Corridor Related
- Corridor Spacing – the number of empty cells the corridor has to have on either side of it for it to be built. This is dependant upon the direction it is travelling. If travelling north, it must have that number of empty cells to the east and west of it.
- Minimum Length – the minimum length of a corridor.
- Maximum Length – the maximum length of a corridor.
- Maximum Turns – the maximum number of direction changes a corridor can make whilst it is being built.
- Map Size – the size of the rectangle containing the dungeon.
- Break Out – When this value is exceeded, exit the dungeon generating While loop.
- Select room – the value between 1 and 100, that when exceeded will cause a room to be selected as the starting point for a corridor build operation.
- Corridor Distance – the minimum distance a room can be placed from existing corridors.
- Distance from other rooms – the minimum distance a room can be from other rooms before it can be built.
- Maximum Size – the maximum size of a room.
- Minimum Size – the minimum size of a room.
- Rooms to build – the total number of rooms to build.
The process for finding a start point for a corridor is:
- To randomly choose a start point on a corridor or room and a direction the corridor will “grow” in using the method Corridor_GetStart. The property Select Room is used to determine the probability of choosing a corridor or room, by default it is set to 50%.
- If step 1 successful pass the start point and direction the method CorridorMake_Straight and examine the return value to determine what to build, some of the return values are:
- Completed: corridor has been completed without running into anything.
- Hit existing corridor: corridor has hit an existing corridor.
- Hit existing room
- Hit self
(All return types are described in the enum CorridorItemHit).
In the example method Build_ConnectedStartRooms() and Build_OneStartRoom(), if the corridor is completed, an attempt to build a room of it is made and if that is successful both the room and corridor are built. If the corridor hits an existing room, an existing corridor or itself the corridor is built.
Corridors are added to the map array, and also stored in the generic list lBuilltCorridors to enable additional tests when attempting to build other rooms or corridors. When a corridor is being built it is stored in the generic list lPotentialCorridor.
A room is a rectangle which is built of a corridor end point in the direction the corridor was moving. After a rectangle has been created using the properties Minimum Size and Maximum Size, it is tested in the method Room_Verify() for the following:
- Check it occupies legal, empty coordinates in the map 2d array.
- It is expanded by the property RoomDistance and tested to see if it makes contact with any current rooms stored in the generic list rctBuiltRooms.
- It is expanded by the property CorrdiorDistance and tested to see if it makes contact with any current rooms stored in the generic list lBuilltCorridors .
If the above criteria are met, the room is built – it is added to the 2d array map, and the rectangle which defines it is added to the generic list rctBuiltRooms.
When a corridor is being built a direction is chosen using one of the two methods:
- Direction_Get(Point dir) – get a random direction, as long as that direction is not the opposite of the one provided to the method. This prevents back tracking.
- Direction_Get(Point pDir, Point pDirExclude) - get a random direction, as long as that direction is not the opposite of the one provided to the method AND the direction specified in pDirExclude. The later direction is the first direction chosen when a corridor is built – this will stop a generating corridor from going in the opposite direction to the one it started with. Makes longer, less twisty corridors.
The corridor building method CorridorMake_Straight () offers a parameter called PreventBackTracking, that when set to to true will select the later option and when false the former. In all build_ examples, a value is selected randomly.
Break out, or getting stuck
Adjusting the properties will produce mazes with different characteristics, but may cause prevent the map from being built, for example if one specifies 100 rooms in a relatively small map the loop contained within the build method will never exit as 100 rooms won’t fit, so a counter is placed within the loop that will cause the loop to exit when the property Break Out is exceeded and the method will return false and in the provided application a messagebox will alert the user to this.
The Map Builder Code
The class csMapbuilder.cs contains the code used to build a map.
The public methods Build_ConnectedStartRooms() and Build_OneStartRoom() are called to build a map, and the boolean value returned indicates if building a map was successful; success occurs when the required number of rooms are built before the property Break Out is exceeded.
The public property Map, a two dimensional integer array contains the built map. A value of 1 indicates a solid cell and value of 0 is an empty space your adventurer can explore.
Here’s a bit of pseudo code demonstrating the above:
csMapbuilder mpbuild = new csMapbuilder(150, 150); //the numbers are the starting map size
if (mpbuild.Build_ConnectedStartRooms() == true)
//map drawing code to go here
Get the code
To download the C# source code click here.
Github: click here.