Developing a Dungeon-Building algorithm has been a personal project for quite a while, but I've always spent more time writing the code than thinking of the theory. Unsurprisingly, I ended up writing inefficient, boring tunelling algorithms.

In this blog post, we will dive into the subject and try to develop a new idea, from the theory to the implementation in C.

## Goals

The algorithm should generate random maps suitable for a Roguelike game. Generated maps should not necessarily be composed of interconnected rooms like NetHack does: They could also look like caverns or mines, e.g. the ones used in Cavern or Possession.

*suitable for a roguelike game* means that generated maps should be
connected (connected
as in graph theory: each point of the map should be accessible to the player).

Furthermore, the algorithm should be scalable (it should work fine on low power devices but should also take advantage of more powerful machines) and modular (it should be possible to generate a variety of maps using the same code base).

## First idea

```
function fill_map(Map* map, Float filling_coefficient, Float room_size):
fill map with empty characters
Point point
do
point = select point at random in the map
while !is_suitable_initial_point(map, point)
Integer filled = 0
do
filled += generate_room(map, &point, max_room_size)
while filled < filling_coefficient * map.size
function generate_room(Map* map, Point* point, Float room_size):
// Used as a black box. It should:
// Generate a rectangular room in passed map around passed point. Return
// the number of points newly marked in the map. Select coordinates in
// generated room and update point.
// Also, room doesn't have to be rectangular, it can have any shape as
// long as it is random
function is_suitable_initial_point(Map* map, Point initial_point):
if initial_point.y < 1 or map.height - initial_point.y <= 1 or
map.width - initial_point.x <= 1 or initial_point.x < 1:
return false
return true
```

This algorithm chooses coordinates in the empty map and uses them as
initial point to generate a room. Then, as long as the desired size isn't
reached, new coordinates are chosen in the previously generated room
and used as initial point to generate *another* room, so on and so forth.

### Suitability

Any map generated in this way is necessarily connected since we always
choose the *next* initial point in the *previously* generated room. It is
*inplace* because we don't need any buffer, which is a very interesting quality
for embedded devices.

Also, we can be sure that the algorithm ends. In fact, as long as the desired size is smaller than the map, there will always be 'enough place to fill', and even if the algorithm may loop some time over previously marked points, it will always 'find' the remaining unmarked coordinates. I didn't try to find its worst case bound, but it could be interesting to do it.

## Implementation

I have implemented the algorithm in C for the following reasons:

- I want to use the generator for Arduboy games, which limits the choice to C and C++.
- In my opinion, object oriented programming doesn't bring anything interesting here. The algorithm is pretty straightforward and I except to write something more efficient in C than in C++.

I have written two `generate_room()`

functions which allow the generation
of rectangular and elliptic rooms.

The implementation is certainly perfectible, but for the moment it does the job in a sufficiently efficient way. You can find the source code on GitHub.

## Some examples

You can find some examples of generated maps here, with different parameters.

## Complexity and speed

The arguments of the `fill_map`

function are interesting for modularity and
scalability.

`room_size`

allows control over the maximal size of generated rooms. Small
values will produce fine-grained maps, at the cost of a higher computational
overhead (more loop cycles are required to achieve the desired filling).
On the other hand, the `filling_coefficient`

variable allows control over the
map's filling (for example a filling coefficient of 0.9 will produce a map which
will have *at most* 10% of empty space).

Together, these two parameters allow to generate maps with a pre-defined filling lower bound
regardless of the available hardware, with `room_size`

being the variable parameter. Please
note that high values of `room_size`

do have an impact on the final result. We will discuss this point later.

The following chart represents the average number of CPU cycles needed to
generate a map, in relation to the value of `room_size`

(with `filling_coefficient`

constant 0.4).

As you can see, the computational overhead increases exponentially as `room_size`

approaches zero. This is because the probability that a newly generated room is
fully included in the already filled space is higher when `room_size`

is small.

## Room size upper bound and final result

So, the room size upper bound has an impact on the computation costs, but what is its impact on the final result ?

In fact, running the current C implementation with `room_size`

= 0.05 on modern
personal computers is fast (1-2*ms* in average with a core i5-5200U). On (very?)
low power devices however, the higher computational overhead might be a
problem. For that reason, it would be a good idea to study the effects of
`room_size`

on the final result, in order to maximize it and make
computation costs as small as possible with the best map quality possible.

Statistical experiment shows that higher values of `room_size`

imply:

- more big rooms (trivial)
- increased impact of
`generate_room()`

on the final result (less trivial) - poorer (less natural) result when mixing several room generators

Lessons I learned from the C implementation:

- elliptic room generators should be preferred for natural results with high
values of
`room_size`

. - rectangular room generators might be of interest with high values of
`room_size`

but results are less predictable and very big rooms may be problematic because more frequent.

These results are of course only experimental and potentially subjective. Interested users may have to play around with the parameters to find the most appropriated ones for their specific usages.

You can find some result examples here with the algorithm using only rectangular/elliptic room generators.

## Other ideas

In the end, this algorithm works well. It is fully usable and produces very nice
results for small values of `room_size`

. `generate_room()`

may be studied
further to find optimal solutions, but this is not critical as long as the
implementation is run on modern hardware.

I'm probably going to work on other blog posts about random map generation. I think it is a very interesting subject and I have other ideas I'd still like to develop. For example, I've thought of generating a big map and then randomly removing parts of it until we reach the desired size.

In this case it would be fairly easy to guarantee the connection property, since the map can be represented as a graph, with each coordinates being a node: Using graph theory we can make sure that removing a node won't dis-connect the graph, for example by removing leaves of its spanning tree.

This algorithm would have a linear worst case bound.

## Credits & further reading

I have used Valgrind and kcachegrind as profiling tools.

*Some interesting links:*

- Procedural Content Generation Wiki: Dungeon Generation
- Memory optimization: The Lost Art of C Structure Packing

*Heading image from Wikimedia Commons.*