I've been playing roguelikes for the last twenty years or so, and one thing that has consistently annoyed me is that dungeons, on the whole, tend to be rectangular rooms connected with long, straight corridors that turn at right angles. I've never came across a roguelike that has complex, chaotic looking cave systems with twisting corridors and misshapen rooms, and that has annoyed me so much I decided to put together a simple algoritm in C# to generate such a system. Here's an example of a complex cave systems generated by my code, and below that I discuss the code used to generate it.
This algorithm works by using a modified form of Conway's Game of Life where:
- Each cell in the map is visited and a randomly probability is used to determine if that cell is closed,
- Cells are randomly visited and the number of neighbours that cell has is used to determine whether to close it or open it.
By repeating the second step thousands of times, "blobs" or "caves" start to form which. By adjusting various available properties the characteristics of the caves formed can change considerably, which can lead to some very interesting cave systems being formed.
After caves have been generated, a flood fill based algorithm locates each cave and the data for each cave into a generic list. With this list of caves they can be easily connected together with a dumb corridor building routine is used to try and connect the caves. This works by randomly selecting a cave and growing a corridor in a random direction and seeing if it hits another cave within a time period determined by a series of properties. If sucessful the two connected caves are placed in a list, and a further attempt is made to connect one of those caves to another, and so on.
You can find a simple C# application which demos the algorithm I've written here, and below is a screenshot of it.
The app consists of three areas:
- Property grid - the properties which govern the generation of the cave system.
- Picturebox - displays the generated cave system.
- Build Caves - click to build a cave system.
- Connect Caves - click to connect the caves.
- Reset Properties - click the reset the property values to their default state.
Simply put, to build a cave system click the Build Caves button, and to change the appearance of a cave system fiddle with the properties.
This application has a number of properties which can be adjusted to determine the appearance of the generated generated cave system:
- Cave Cleaning
- Filling - Fills in holes within caves: an open cell with this number closed neighbours is closed.
- Lower Limit - the minimum size of caves allowed. If a cave is smaller than this number, it will be removed.
- Smoothing - Removes single cells from cave edges: a cell with this number of empty neighbours is removed
- Upper Limit - the maximum size of caves allowed. If a cave is larger than this number, it will be removed.
- Cave Generation
- Close Cell Prob - this value determines the chance of closing a visited cell.
- Cells to visit - the number of cells to visit during the generation process.
- Map Size - guess what this does.
- Neighbours - when this value is equalled or exceeded, change the cell state.
- Breakout - a counter value, that when exceeded stops attempting to generate corridors. Stops the corridor building process from getting stuck.
- 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.
- Generated Map
- Caves - the number of caves in the generated system.
The code used to generate a caver system is contained within the class csCaveGenerator.cs, which sits in a standard C# form with a few controls on it which can manipulate that class.
For an overview of the class csCaveGenerator.cs, click here.
For a more detailed look at using the class csCaveGenerator.cs, click here.
To view the class csCaveGenerator.cs in GitHub click here.
Playing around with the properties can produce cave systems with markedly different appearances, here are a few interesting systems that can be produced.
Several Large Caves
Setting the properties to:
- MaxSizeToRemove: 1500
- MinSizeToRemove: 450
- EmptyCells > EmptyCellNeighbours: 3
and clicking build a few times produced these three lovely caves.
Many small chunky caves
Setting the properties to:
- Iterations: 10,000
And clicking build, produces lots of little chunky caves with straight edges, packed closer together.
One Massive Cave
Setting the properties to:
- Caves > MaxSizeToRemove: 10000
- Cells > CloseCellProb: 55
And clicking Go a few times will produce a lovely, humongous cave, as shown below.
Github: To view the class csCaveGenerator.cs, which is used to generate the cave system, click here.
To download a C# app which demos the Cave Generator algorithm click here.
This post contains a more detailed look at the class csCaveGenerator.cs, whose layout is discussed here, and can be viewed on GitHub here.
Within the class csCaveGenerator.cs, the source code is fully commented and easy to follow, and because I'm lazy I'm not going to copy those comments again :). However I will tell you how to use the class. Refer to the section below called Using the Class.
Using the class
This is simple enough:
csCaveGenerator cavgen = new csCaveGenerator();
To build a cave system:
Connecting rooms is also simple:
The Generated Map
The publicly exposed property Map is a 2d array which contains the generated map - a value of 1 indicates a closed cell.
This article describes the layout of the class csCaveGenerator.cs which is used to generate a cave system, and can be viewed on GitHub here. Within this class are several regions which are used to group together related methods, properties, data structures etc. These regions are:
- Map Structures
- Cave Related
- Corridor Related
- Direction Related
- Cell Related
Contains the properties used to control the appearance of the cave system being generated. Discussed in detail in part 1.
Contains the class constructor and the method Build() which generates the caves.
Map Structures Region
This contains the generic lists used to hold cave system data: Caves, Corridors and Map.
Contains two lists of points which contain directions:
- Directions: four points which represent North, South, East and West.
- Directions1: 8 points which represent North, South, East, West, North East, North West, South East and South West.
These lists are used to examine the neighbours of a cell for the cave generation, smoothing and filling operations.
Cave Related Region
Contains the code used to generate caves, and subdivided into three regions:
- Make Caves
- Locate Caves
- Connect Caves
This contains the method BuildCaves() which generates the cave system
This contains three methods used to locate discrete caves on the map and place them in the generic list Caves. The method GetCaves() is called to do this - which uses a recursive flood fill algorithm.
Contains the method ConnectCaves(), a brute force method which randomly attempts to connect caves. Dependant upon methods in the Cave Related Region.
Corridor Related Region
Contains the methods:
Which are all used by the method ConnectCaves().
Direction Related Region
This region contains a series of methods using in locating the neighbours of a cell, generating a randomly direction etc
Cell Related Region
A series of methods used for manipulating map cells.
In a RogueLike the game view (GV) is a rectangular area of the map occupied by the player that is displayed on screen, an example of which is shown below. A gameview consists of two parts: a size and an origin (the x and y coordinates which define the top left corner). The origin is calculated from the player's current coordinates by subtracting half the GV width from player X and half the GV height from player Y, and making adjustments to them under certain conditions described below.
This article describes how to calculate the coordinates required for a game view.
The following terms are required in order to calculate the GV origin coordinates GVOriginX and GVOriginY:
- PlayerX, PlayerY - The coordinates of the player's current location
- GVWidth, GVHeight - The size of the game view
- MapWidth, MapHeight - The size of the map the player is exploring.
It is assumed that MapWidth > GVWidth and MapHeight > GVHeight.
For the player to be displayed dead centre in the GV GVWidth and GVHeight must be odd numbers.
This origin of the GV is defined as:
- GVOriginX = playerX - GVWidth / 2
- GVOriginY = playerY - GVHeight / 2
Therefore, the bottom right corners coordinates of the GV are GVOriginX + GVWidth and GVOriginY + GVHeight.
However, there are obvious conditions where GVOriginX and / or GVOriginY are less than 0, or the bottom right coordinates exceed the MapHeight and / or MapWidth, so we need to make the followings checks and correct as appropriate after calculating generating GVOriginX and GVOriginY:
|Check||Correction if true|
|GVOriginX < 0||GVOriginX = 0|
|GVOriginY < 0||GVOriginY = 0|
|GVOriginX + GVWidth > MapWidth||GVOriginX -= (GVOriginX + iViewWidth - MapWidth)|
|GVOriginY + GWHeigtht > MapHeight||GVOriginY -= (GVOriginY + iViewHeight - MapHeight)|
The effect of making these changes will cause the player to be displayed off centre and closer to the edge being moved towards, as shown below. If none of the above corrections are required, the player will be shown in centre of GV as shown in the picture at the start of this article.
A Visual Studio demonstrating the above method in a simple demo which allows a player to explore a map using the keys Q,W,E,A,S,D,Z,X and C can be found here.
Have I seen this before?
The observant amongst you will notice that this code comes from my Evil Science article Field of Vision using recursive shadow casting: C# .Net 3.5 implementation, but I thought I'd use the code again with emphasis on how to draw the Game View.
This is a simple generating routine I developed in C# whilst experimenting whilst playing around with the algorithms for Conway's Game of Life.By adjusting the properties it can produce "island" or "labyrinth " type maps. I "discovered" this algorithm
Here's a few examples of maps it can generate, with the property values used to create them. Explanations of the properties are given later in the article.
Using the App
Load up the app, fiddle with the properties and click the Go button.
How it Works
Map generation is controlled by the following variables:
- p (int) - close cell probability. Between 0 and 100.
- h (bool) - cell operation specifier.
- i (int) - counter.
- n (int) - number of cell's neighbours.
- c (int) - examined cell's closed neighbours. Between 0 and 8.
Calling the method go() in the class csIslandMaze will generate a map using the following logic:
- Randomly choose a cell from map
- If the cell is open use a p to determine whether we close it.
- Get c
- h = true: If c > n close the cell, else open it.
- h = false: If c > n open the cell, else close it.
- Repeat steps1 - 3 i number of times.
Varying the above mentioned variables will produce maps of surprisingly different appearances.
You can download the C# source code here.
A working field-of-view (FOV) algorithm is one of the essential parts in any roguelike, it is used to calculate which mapcells, within a given radius, that can be seen by seen by the player. This article describes a C# implementation of such an algorithm, known as recursive shadow casting which is described in more detail in the article FOV using recursive shadowcasting - improved.
Shadowcasting divides the FOV calculations into eight octants and visits the mapcells of each row by row or column by column, starting with the nearest row or column and working it's way outward.
------> 6 row 6 last -----> 5 . ----> 4 . ---> 3 . --> 2 row 2 second -> 1 row 1 is scanned first @ @ this is the starting point
When a scan comes across a cell that blocks the players line of sight it calculates which other cells in rows/columns farther away that isn't visible because of the blocker. Those cells are "in shadow", hence the term shadowcasting.
-...--- - = visible cells -..--- # = blocking cell -#--- . = cells in blocker's shadow ---- --- -- @
The above text is taken from this article, from the website RogueBasin. I have shamelessly lifted this text, as I feel it is a very clear description of how shadowcasting works, and I can't improve upon it.
Below are several pictures of the application which demonstrate that algorithm. The lighter squares represent the cells visible to the player, and the darker ones are those which the player cannot see. The maze displayed in the map has been generated using another algorithm (which I'll post soon) and is loaded when the application starts up.
The keys q,w,e,a,d,z,x and c control the player move the player. W is up, S down, d right, A left right etc
Github: the code for the class FOVRecurse.
What's Going On?
The class FOVRecurse.cs contains the FOV algorithm, and the methods are GetVisibleCells and ScanOctant are where the magic happens.
When the player moves, the method GetVisibleCells is called which in turn calls the method ScanOctant for each of the 8 areas surrounding the player and all the cells that the player can see are stored in a generic list. Upon completion of this scan the the event playerMoved is fired, which causes the map to be redrawn in the form event pictureBox1_Paint.
There really isn't that much to say about it as the code speaks for itself, but if you're stuck with anything please add a comment and I'll get back to you.
This post takes text from the RogueBasin articles:
I have used the take from the above as I feel these are the best explanations of how the shadow casting technique works, and I can't really improve upon them.
I completely forgot about it until I came across a reference to it on http://pcg.wikidot.com and thought "this looks familiar"
The most fundamental thing in a roguelike is line of sight (LOS), that is, the determination of what the player (and monsters) can see in their environment.
The method I am using for LOS is ray casting. This is where a line is drawn between two points using Bresenham's Line Algorithm.
Calculating a sight zone
In a roguelike the area that a player can "see" is commonly within the boundaries of a circle which the player is the centre of. This application, called circle and pictured below, contains an example of this using an implementation of Bresenham's alogrithm. The blue square represents the player, the white circle surrounding it is the area the player can see , the black blocks are barriers that the player cannot see through.
It works by calculating all the points that lie within a circle of radius r around the player (x,y). If a point is within a circle whose centre point is the player the formula ((x1-x)^2 + (y1-y)^2) < r^2 is true.
Then a Bresenham line (BL) is drawn from the player to the location being examined, one point at a time. If that point is unoccupied it is added to a list and the next point is examined; if it is occupied it not added to the list and BL is abandoned, and so on. Upon completion or abandoning of a line, the points can be seen by the player and are drawn.
Using the application
Compile and run the application using C# express.
The spinbox in the top right hand corner is used to adjust the radius of the player sight.
Pressing the W key moves the player up, S moves the player down, A moves the player left and D moves the player right.
Right click anywhere within the form to add a barrier, and right click it again to remove it.
Observe how the player sight zone changes when you add and remove barriers and move around.
Bresenham's line algorithm is the corner stone of any Roguelike game that uses raycasting as a means of determining what the player can see. It is used to draw an approximation of a straight line between two points. Wikipedia has a more detailed article.
You can download my simple app (bres) demonstrating this algorithm here. Bres contains a form representing a 25 by 25 grid, in which a Bresenham's line is drawn between two points. To run it you'll need to get hold of C# Express and compile the programme. I just don't think having executables to download is a reassuring thing to have
Using the application
Compile and run the application using C# express.
Move the mouse around on the form and a line will be drawn between the start point (a blue square) and the current mouse position (a red square). Left click to place a new start point. Right click to place a barrier (a black block). To remove it, right click again. A barrier placed between the start and end point will stop a line being drawn between them; the line will begin at the start point and stop at the barrier (pictured below).
This section is about my occasional attempts to develop a roguelike game in C#. Stuff will appear sporadically.