This tutorial is free and open source, and all code uses the MIT license - so you are free to do with it as you like. My hope is that you will enjoy the tutorial, and make great games!
If you enjoy this and would like me to keep writing, please consider supporting my Patreon.
Ever wondered what would happen if an Umber Hulk (or other tunneling creature) got really drunk, and went on a dungeon carving bender? The Drunkard's Walk algorithm answers the question - or more precisely, what would happen if a whole bunch of monsters had far too much to drink. As crazy it sounds, this is a good way to make organic dungeons.
As usual, we'll start with scaffolding from the previous map tutorials. We've done it enough that it should be old hat by now! In map_builders/drunkard.rs, build a new DrunkardsWalkBuilder class. We'll keep the zone-based placement from Cellular Automata - but remove the map building code. Here's the scaffolding:
#![allow(unused)]fnmain() {
use super::{MapBuilder, Map,
TileType, Position, spawner, SHOW_MAPGEN_VISUALIZER};
use rltk::RandomNumberGenerator;
use specs::prelude::*;
use std::collections::HashMap;
pubstructDrunkardsWalkBuilder {
map : Map,
starting_position : Position,
depth: i32,
history: Vec<Map>,
noise_areas : HashMap<i32, Vec<usize>>
}
impl MapBuilder for DrunkardsWalkBuilder {
fnget_map(&self) -> Map {
self.map.clone()
}
fnget_starting_position(&self) -> Position {
self.starting_position.clone()
}
fnget_snapshot_history(&self) -> Vec<Map> {
self.history.clone()
}
fnbuild_map(&mutself) {
self.build();
}
fnspawn_entities(&mutself, ecs : &mut World) {
for area inself.noise_areas.iter() {
spawner::spawn_region(ecs, area.1, self.depth);
}
}
fntake_snapshot(&mutself) {
if SHOW_MAPGEN_VISUALIZER {
letmut snapshot = self.map.clone();
for v in snapshot.revealed_tiles.iter_mut() {
*v = true;
}
self.history.push(snapshot);
}
}
}
impl DrunkardsWalkBuilder {
pubfnnew(new_depth : i32) -> DrunkardsWalkBuilder {
DrunkardsWalkBuilder{
map : Map::new(new_depth),
starting_position : Position{ x: 0, y : 0 },
depth : new_depth,
history: Vec::new(),
noise_areas : HashMap::new()
}
}
#[allow(clippy::map_entry)]fnbuild(&mutself) {
letmut rng = RandomNumberGenerator::new();
// Set a central starting pointself.starting_position = Position{ x: self.map.width / 2, y: self.map.height / 2 };
let start_idx = self.map.xy_idx(self.starting_position.x, self.starting_position.y);
// Find all tiles we can reach from the starting pointlet map_starts : Vec<usize> = vec![start_idx];
let dijkstra_map = rltk::DijkstraMap::new(self.map.width, self.map.height, &map_starts , &self.map, 200.0);
letmut exit_tile = (0, 0.0f32);
for (i, tile) inself.map.tiles.iter_mut().enumerate() {
if *tile == TileType::Floor {
let distance_to_start = dijkstra_map.map[i];
// We can't get to this tile - so we'll make it a wallif distance_to_start == std::f32::MAX {
*tile = TileType::Wall;
} else {
// If it is further away than our current exit candidate, move the exitif distance_to_start > exit_tile.1 {
exit_tile.0 = i;
exit_tile.1 = distance_to_start;
}
}
}
}
self.take_snapshot();
// Place the stairsself.map.tiles[exit_tile.0] = TileType::DownStairs;
self.take_snapshot();
// Now we build a noise map for use in spawning entities laterletmut noise = rltk::FastNoise::seeded(rng.roll_dice(1, 65536) asu64);
noise.set_noise_type(rltk::NoiseType::Cellular);
noise.set_frequency(0.08);
noise.set_cellular_distance_function(rltk::CellularDistanceFunction::Manhattan);
for y in1 .. self.map.height-1 {
for x in1 .. self.map.width-1 {
let idx = self.map.xy_idx(x, y);
ifself.map.tiles[idx] == TileType::Floor {
let cell_value_f = noise.get_noise(x asf32, y asf32) * 10240.0;
let cell_value = cell_value_f asi32;
ifself.noise_areas.contains_key(&cell_value) {
self.noise_areas.get_mut(&cell_value).unwrap().push(idx);
} else {
self.noise_areas.insert(cell_value, vec![idx]);
}
}
}
}
}
}
}
We've kept a lot of the work from the Cellular Automata chapter, since it can help us here also. We also go into map_builders/mod.rs and once again force the "random" system to pick our new code:
Since we're re-using the exact code from Cellular Automata, we should take the common code and put it into map_builders/common.rs. This saves typing, saves the compiler from repeatedly remaking the same code (increasing your program size). So in common.rs, we refactor the common code into some functions. In common.rs, we create a new function - remove_unreachable_areas_returning_most_distant:
#![allow(unused)]fnmain() {
/// Searches a map, removes unreachable areas and returns the most distant tile.pubfnremove_unreachable_areas_returning_most_distant(map : &mut Map, start_idx : usize) -> usize {
map.populate_blocked();
let map_starts : Vec<usize> = vec![start_idx];
let dijkstra_map = rltk::DijkstraMap::new(map.width asusize, map.height asusize, &map_starts , map, 200.0);
letmut exit_tile = (0, 0.0f32);
for (i, tile) in map.tiles.iter_mut().enumerate() {
if *tile == TileType::Floor {
let distance_to_start = dijkstra_map.map[i];
// We can't get to this tile - so we'll make it a wallif distance_to_start == std::f32::MAX {
*tile = TileType::Wall;
} else {
// If it is further away than our current exit candidate, move the exitif distance_to_start > exit_tile.1 {
exit_tile.0 = i;
exit_tile.1 = distance_to_start;
}
}
}
}
exit_tile.0
}
}
We'll make a second function, generate_voronoi_spawn_regions:
#![allow(unused)]fnmain() {
/// Generates a Voronoi/cellular noise map of a region, and divides it into spawn regions.#[allow(clippy::map_entry)]pubfngenerate_voronoi_spawn_regions(map: &Map, rng : &mut rltk::RandomNumberGenerator) -> HashMap<i32, Vec<usize>> {
letmut noise_areas : HashMap<i32, Vec<usize>> = HashMap::new();
letmut noise = rltk::FastNoise::seeded(rng.roll_dice(1, 65536) asu64);
noise.set_noise_type(rltk::NoiseType::Cellular);
noise.set_frequency(0.08);
noise.set_cellular_distance_function(rltk::CellularDistanceFunction::Manhattan);
for y in1 .. map.height-1 {
for x in1 .. map.width-1 {
let idx = map.xy_idx(x, y);
if map.tiles[idx] == TileType::Floor {
let cell_value_f = noise.get_noise(x asf32, y asf32) * 10240.0;
let cell_value = cell_value_f asi32;
if noise_areas.contains_key(&cell_value) {
noise_areas.get_mut(&cell_value).unwrap().push(idx);
} else {
noise_areas.insert(cell_value, vec![idx]);
}
}
}
}
noise_areas
}
}
Plugging these into our build function lets us reduce the boilerplate section considerably:
#![allow(unused)]fnmain() {
// Find all tiles we can reach from the starting pointlet exit_tile = remove_unreachable_areas_returning_most_distant(&mutself.map, start_idx);
self.take_snapshot();
// Place the stairsself.map.tiles[exit_tile] = TileType::DownStairs;
self.take_snapshot();
// Now we build a noise map for use in spawning entities laterself.noise_areas = generate_voronoi_spawn_regions(&self.map, &mut rng);
}
In the example, I've gone back to the cellular_automata section and done the same.
This is basically the same code we had before (hence, it isn't explained here), but wrapped in a function (and taking a mutable map reference - so it changes the map you give it, and the starting point as parameters).
Pick a central starting point, and convert it to a floor.
We count how much of the map is floor space, and iterate until we have converted a percentage (we use 50% in the example) of the map to floors.
Spawn a drunkard at the starting point. The drunkard has a "lifetime" and a "position".
While the drunkard is still alive:
Decrement the drunkard's lifetime (I like to think that they pass out and sleep).
Roll a 4-sided dice.
If we rolled a 1, move the drunkard North.
If we rolled a 2, move the drunkard South.
If we rolled a 3, move the drunkard East.
If we rolled a 4, move the drunkard West.
The tile on which the drunkard landed becomes a floor.
That's really all there is to it: we keep spawning drunkards until we have sufficient map coverage. Here's an implementation:
#![allow(unused)]fnmain() {
// Set a central starting pointself.starting_position = Position{ x: self.map.width / 2, y: self.map.height / 2 };
let start_idx = self.map.xy_idx(self.starting_position.x, self.starting_position.y);
self.map.tiles[start_idx] = TileType::Floor;
let total_tiles = self.map.width * self.map.height;
let desired_floor_tiles = (total_tiles / 2) asusize;
letmut floor_tile_count = self.map.tiles.iter().filter(|a| **a == TileType::Floor).count();
letmut digger_count = 0;
letmut active_digger_count = 0;
while floor_tile_count < desired_floor_tiles {
letmut did_something = false;
letmut drunk_x = self.starting_position.x;
letmut drunk_y = self.starting_position.y;
letmut drunk_life = 400;
while drunk_life > 0 {
let drunk_idx = self.map.xy_idx(drunk_x, drunk_y);
ifself.map.tiles[drunk_idx] == TileType::Wall {
did_something = true;
}
self.map.tiles[drunk_idx] = TileType::DownStairs;
let stagger_direction = rng.roll_dice(1, 4);
match stagger_direction {
1 => { if drunk_x > 2 { drunk_x -= 1; } }
2 => { if drunk_x < self.map.width-2 { drunk_x += 1; } }
3 => { if drunk_y > 2 { drunk_y -=1; } }
_ => { if drunk_y < self.map.height-2 { drunk_y += 1; } }
}
drunk_life -= 1;
}
if did_something {
self.take_snapshot();
active_digger_count += 1;
}
digger_count += 1;
for t inself.map.tiles.iter_mut() {
if *t == TileType::DownStairs {
*t = TileType::Floor;
}
}
floor_tile_count = self.map.tiles.iter().filter(|a| **a == TileType::Floor).count();
}
rltk::console::log(format!("{} dwarves gave up their sobriety, of whom {} actually found a wall.", digger_count, active_digger_count));
}
This implementation expands a lot of things out, and could be much shorter - but for clarity, we've left it large and obvious. We've also made a bunch of things into variables that could be constants - it's easier to read, and is designed to be easy to "play" with values. It also prints a status update to the console, showing what happened.
If you cargo run now, you'll get a pretty nice open map:
There's a lot of ways to tweak the "drunkard's walk" algorithm to generate different map types. Since these can produce radically different maps, lets customize the interface to the algorithm to provide a few different ways to run. We'll start by creating a struct to hold the parameter sets:
We alluded to it in the previous section with the creation of DrunkSpawnMode - we're going to see what happens if we change the way drunken diggers - after the first - spawn. Change the random_builder to DrunkSpawnMode::Random, and then modify build (in drunkard.rs) to use it:
This is a relatively easy change: if we're in "random" mode, the starting position for the drunkard is the center of the map for the first digger (to ensure that we have some space around the stairs), and then a random map location for each subsequent iteration. It produces maps like this:
.
This is a much more spread out map. Less of a big central area, and more like a sprawling cavern. A handy variation!
Another parameter to tweak is how long the drunkard stays awake. This can seriously change the character of the resultant map. We'll add it into the settings:
That's a simple change - and drastically alters the nature of the resulting map. Each digger can only go one quarter the distance of the previous ones (stronger beer!), so they tend to carve out less of the map. That leads to more iterations, and since they start randomly you tend to see more distinct map areas forming - and hope they join up (if they don't, they will be culled at the end).
cargo run with the 100 lifespan, randomly placed drunkards produces something like this:
Lastly, we'll play with how much of the map we want to cover with floors. The lower the number, the more walls (and less open areas) you generate. We'll once again modify DrunkardSettings:
We previously had desired_floor_tiles as total_tiles / 2 - which would be represented by 0.5 in the new system. Lets try changing that to 0.4 in random_builder:
Now that we've got these parameters to play with, lets make a few more constructors to remove the need for the caller in mod.rs to know about the algorithm details:
And we're done with drunken map building (words I never expected to type...)! It's a very flexible algorithm, and can be used to make a lot of different map types. It also combines well with other algorithms, as we'll see in future chapters.
The source code for this chapter may be found here