![Gif showing the steps to generate an ASCII-character tiled dungeon in R. First, a map is created with four randomly-placed floor tiles, then they're connected with corridors, then the tiles around the floor tiles are converted from wall to floor tiles, randomly, for three iterations.](/post/2022-04-30-dungeon_files/r.oguelike-generate.gif)
Three iterations to expand four randomly-placed floor tiles into a cavern.
tl;dr
I wrote a (very!) basic procedure to generate randomised ASCII-character tile-based dungeons for {r.oguelike}, an in-development roguelike-game-in-a-package for R.
Generate to accumulate
I wrote recently about the {r.oguelike} R package, which contains the beginnings of a roguelike game written entirely in R.
A key element of roguelike games is that the dungeons should be procedurally generated1 so that the player gets a different one each time they play.
There are many algorithmic systems for dungeon creation, like wave function collapse, perlin noise, binary space partitioning, cellular automata, etc.2 See the talk by Herbert Wolverson at Roguelike Celebration, for example.
I plan to take a look at these approaches in future, but I wanted to start with something a bit more… naïve. I just want a simple interconnected space that spawns with randomised rooms, corridors and galleries.
Excavations
Note
The {r.oguelike} package is a work in progress and is developing at pace. Many things explained below may have been superseded or changed by the time you read this.
Install/launch
You can install the (currently work-in-progress) {r.oguelike} package from GitHub, via {remotes}.
# install.packages("remotes") # if not already installed
install_github("matt-dray/r.oguelike")
You can also launch RStudio in the browser with {r.oguelike} preinstalled, thanks to Binder3 (may take a couple of minutes to load):
Prepare
Before we begin, note that we can talk about generative ‘dungeons’ in the context of connected rooms, like in The Binding of Isaac, or more freeform structures, like world maps in Dwarf Fortress. We’re going for the latter, which amounts to interconnected caverns.
The function we’ll be using is called generate_dungeon()
, which prints to the console a cavern that differs each time you run it.4 You can alter the output using the arguments:
iterations
is the number of times to ‘grow’ the cavernsn_row
andn_col
give the map dimensionsn_rooms
is the number of rooms to spawnis_snake
for a cavern that is continuous from left to right and wigglyis_organic
for a more freeform vs ‘square’ look to the cavernscolour
to print the output in colour
You can always run set.seed()
before generate_dungeon()
to create the same dungeon every time you run the function with the same parameters.
Demo
So here’s a smallish dungeon with 3 growth iterations for 4 starting rooms, on a map with tile dimensions of 20 rows by 30 columns.
dungeon <- r.oguelike::generate_dungeon(3, 20, 30, 4)
Here’s a screenshot of the output so you can see it in colour.
Click for the actual console output.
| - - - - - - - - - - - - - - - - - - - - - - - - - - - - |
| # # # # # # . # # # # # # # # # # # # # # # # # # # # # |
| # # . # . . . . # # # # # . # # # # # # # # # # # # # # |
| # . . . . # . . # # # . . . . # # # # # # # # # # # # # |
| # . . . . . . . . . . . . . . . # # # # # # # # # # # # |
| . . . # . . # . . # # . . . . . # # # # # # # # # # # # |
| . . . . # # # . # # # # # . . # # # # # # # # # # # # # |
| . . # # # # # # # # # # # . # # # # # # # # # # # # # # |
| . . . . # # # # # # # # . . . # # # # # # # # # # # # # |
| . . . . # # # # # # # # # . . # # # # # # # # # # # # # |
| . . . # # # # # # # . # . . . # # # # # # # # # # # # # |
| . . . # # # # # # . . . . . . . # # # # # # # # # # # # |
| . . . # # . . # . . # . . . . . . . . . # . . . # # # # |
| . . . . . . . . . . . . . . . . . . . . . . . . # # # # |
| . . # # . . . # . # . . . # . . . # # . . # . . # # # # |
| # # # # . . . # . # # # # # . # . # # # # . . . # # # # |
| # # # # # # # # # # # # # # # # # # # # . . . . # # # # |
| # # # # # # # # # # # # # # # # # # # # . . . # # # # # |
| # # # # # # # # # # # # # # # # # # # # # # . # # # # # |
| - - - - - - - - - - - - - - - - - - - - - - - - - - - - |
So, in this example you can see we have a little cavern with some interconnected areas and a dead-end in the lower right. The tiles represent:
- cavern-floor tiles (black periods), which is where the character can traverse
- cave wall tiles (red hashmarks, which can’t be passed through)
- a boundary around the edge (yellow hyphens and pipe symbols)
Note that the actual output from the function—a matrix that represents the dungeon tiles—is returned invisibly.
Click for a preview of for the returned matrix.
# Preview first 10 rows and columns
dungeon[1:10, 1:10]
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
[1,] "|" "-" "-" "-" "-" "-" "-" "-" "-" "-"
[2,] "|" "#" "#" "#" "#" "#" "#" "." "#" "#"
[3,] "|" "#" "#" "." "#" "." "." "." "." "#"
[4,] "|" "#" "." "." "." "." "#" "." "." "#"
[5,] "|" "#" "." "." "." "." "." "." "." "."
[6,] "|" "." "." "." "#" "." "." "#" "." "."
[7,] "|" "." "." "." "." "#" "#" "#" "." "#"
[8,] "|" "." "." "#" "#" "#" "#" "#" "#" "#"
[9,] "|" "." "." "." "." "#" "#" "#" "#" "#"
[10,] "|" "." "." "." "." "#" "#" "#" "#" "#"
More examples
I think this process works best with a larger map grid (i.e. higher n_row
and n_col
values), more randomly-selected room start-points (higher n_rooms
) and more growth steps (higher iterations
).
Here’s a larger maze-like dungeon:
This one came out more like a doughnut, with a central ‘pillar’ of rock-wall tiles:
And this one is the result of using is_snake = TRUE
, which creates a single, long snaking cavern:
Here’s what happens if we set is_organic = FALSE
and is_snake = TRUE
. You get much obvious ‘rooms’ connected by small corridors:
And if we set is_organic = FALSE
and is_snake = FALSE
we get something interconnected, but looks more ‘artificial’ or manmade with its mostly square walls:
You can see how the shape of these dungeons can be used as part of the storytelling. Is the player in a big cavern, hollowed out long ago by natural processes? Or perhaps in an underground city, chiselled-out by dwarves?
The procedure
What’s the actual process for generating these maps? The procedure is very simple: lay a map made entirely of wall tiles; select random sites for rooms5 and replace with floor tiles; connect them with floor-tile corridors; expand the floor tiles generatively.
The corridors are particularly important. Laying corridors is a cheap way of making all areas of the dungeon accessible, which maximises the opportunity for exploration. Vanilla implementations of some other approaches, like using perlin noise, would need post-processing to make sure isolated caves are connected up.
Update
After publishing this post, I had a quick play around with perlin noise for seeding dungeons. I put code and an example output in a small GitHub Gist. It uses noise_perlin()
from the {ambient} package.
Functions
These steps are handled in the generate_dungeon()
function by a few sub-functions, which looks a bit like this:
m <- .create_dungeon(n_row, n_col, n_rooms)
m <- .connect_dungeon(m, is_snake)
i <- 0
while (i < iterations) {
m <- .grow_dungeon(m)
i <- i + 1
}
.draw_dungeon(m, colour)
Not much right? But what’s actually happening?
- First,
.create_dungeon()
:- prepares a matrix with dimensions
n_row
andn_col
- fills the matrix with tiles that represent non-traversable rocky cave walls (
#
) - selects randomly an
n_rooms
number of non-edge tiles in that map and replaces them with traversable cavern-floor tiles (.
)
- prepares a matrix with dimensions
- Then
.connect_dungeon()
(this function is run now ifis_organic = TRUE
, otherwise after.grow_dungeon()
in the next step):- connects rooms with straight, right-angled corridors made of floor tiles (connected from lowest to highest if
is_snake = TRUE
, otherwise randomly)
- connects rooms with straight, right-angled corridors made of floor tiles (connected from lowest to highest if
- Now the iterative bit,
.grow_dungeon()
, which happens in a while-loop whoseiterations
are determined, which:- spawns randomly with
sample()
a new cavern-floor tile to the north, south, east or west or current floor tiles - performs one round of spawning for the number of
iterations
provided
- spawns randomly with
- Finally,
.draw_dungeon()
:- prints to the console, using
cat()
, each line of the matrix in turn - colours the output with the {crayon} package, if requested
- prints to the console, using
And we can look at the output at each step to see what’s going on:
So, the map started with four randomly-selected floor tiles; these were joined with straight, right-angled corridors; then three iterations expanded out the floor space from the existing floor tiles.
Sampling
What does it mean to ‘expand out the floor space’? Let’s focus on the little bit of the .grow_dungeon()
function that actually does this.
Here’s a tiny example matrix of wall tiles with a floor tile in the middle:
m <- matrix("#", 3, 3) # wall tiles
m[2, 2] <- "." # floor tiles
m
## [,1] [,2] [,3]
## [1,] "#" "#" "#"
## [2,] "#" "." "#"
## [3,] "#" "#" "#"
Now we find the adjacent tiles and sample a random number of them to also become floor tiles.
start_tile <- which(m == ".")
adjacent_tiles <- c(
start_tile - 1, # north
start_tile + 1, # south
start_tile - ncol(m), # east
start_tile + ncol(m) # west
)
change_to_floor <- sample(
adjacent_tiles,
sample(1:length(adjacent_tiles), 1)
)
m[change_to_floor] <- "."
m
## [,1] [,2] [,3]
## [1,] "#" "#" "#"
## [2,] "." "." "#"
## [3,] "#" "." "#"
So one, two, three, or all of the adjacent tiles could be turned to a floor tile.
This is then repeated for the number of iterations
provided by the user.
Going deeper
So! I encourage you to play with this. Mess around with the arguments and see what you can come up with.
What now for developing the package? Well, the {r.oguelike} package already has the rudiments of gameplay in the start_game()
function, so the next step is to place the player, enemies and items into these dungeon spaces and let the player explore them.
Update
Just after writing this post, I added code from generate_dungeon()
into start_game()
, so new games will now start with a procedural dungeon. It seems to work pretty well.
Ideally we can also create a system to place certain objects in certain spaces, like treasure in the far reaches of a dead-end, or a monster that’s in a narrow corridor and must be defeated to advance. Stuff like locked doors would be great too.
That’s much more roguelike-like, like, amirite?
Session info
## ─ Session info ───────────────────────────────────────────────────────────────
## setting value
## version R version 4.1.1 (2021-08-10)
## os macOS Mojave 10.14.6
## system x86_64, darwin17.0
## ui X11
## language (EN)
## collate en_GB.UTF-8
## ctype en_GB.UTF-8
## tz Europe/London
## date 2022-05-09
##
## ─ Packages ───────────────────────────────────────────────────────────────────
## package * version date lib source
## blogdown 1.5 2021-09-02 [1] CRAN (R 4.1.0)
## bookdown 0.25 2022-03-16 [1] CRAN (R 4.1.2)
## bslib 0.3.1 2021-10-06 [1] CRAN (R 4.1.0)
## cli 3.2.0 2022-02-14 [1] CRAN (R 4.1.2)
## digest 0.6.29 2021-12-01 [1] CRAN (R 4.1.0)
## evaluate 0.15 2022-02-18 [1] CRAN (R 4.1.2)
## fastmap 1.1.0 2021-01-25 [1] CRAN (R 4.1.0)
## fontawesome 0.2.2 2021-07-02 [1] CRAN (R 4.1.0)
## htmltools 0.5.2 2021-08-25 [1] CRAN (R 4.1.0)
## jquerylib 0.1.4 2021-04-26 [1] CRAN (R 4.1.0)
## jsonlite 1.8.0 2022-02-22 [1] CRAN (R 4.1.2)
## knitr 1.38 2022-03-25 [1] CRAN (R 4.1.2)
## magrittr 2.0.3 2022-03-30 [1] CRAN (R 4.1.2)
## r.oguelike * 0.0.0.9005 2022-05-05 [1] local
## R6 2.5.1 2021-08-19 [1] CRAN (R 4.1.0)
## rlang 1.0.2 2022-03-04 [1] CRAN (R 4.1.2)
## rmarkdown 2.13 2022-03-10 [1] CRAN (R 4.1.2)
## rstudioapi 0.13 2020-11-12 [1] CRAN (R 4.1.0)
## sass 0.4.1 2022-03-23 [1] CRAN (R 4.1.2)
## sessioninfo 1.1.1 2018-11-05 [1] CRAN (R 4.1.0)
## stringi 1.7.6 2021-11-29 [1] CRAN (R 4.1.0)
## stringr 1.4.0 2019-02-10 [1] CRAN (R 4.1.0)
## withr 2.5.0 2022-03-03 [1] CRAN (R 4.1.2)
## xfun 0.30 2022-03-02 [1] CRAN (R 4.1.2)
## yaml 2.3.5 2022-02-21 [1] CRAN (R 4.1.2)
##
## [1] /Users/matt.dray/Library/R/x86_64/4.1/library
## [2] /Library/Frameworks/R.framework/Versions/4.1/Resources/library
I’m not a computer scientist, but Wikipedia says ‘procedural’ involves ‘creating data algorithmically as opposed to manually, typically through a combination of human-generated assets and algorithms coupled with computer-generated randomness and processing power’. The page specifically points out roguelikes as having these properties, so I assume what I’ve done can be described as ‘procedural’?↩︎
Definitely one of these should be the name for your new band.↩︎
There’s no such thing as a free launch, unless it’s with Binder (why have I not thought of this incredible wordplay before and how much should I charge the Binder team for its use?).↩︎
In future, this function will be integrated into the
start_game()
function, but I may still export it so people (i.e. me) can use it for fun.↩︎Akshually, it’s not just a case of choosing a random set of four points within the length of the matrix. The 1D matrix is split
n_rooms
times and we sample from within each of those chunks. This, hopefully, should keep the dungeons relatively-well spread out.↩︎