醉汉漫步地图
关于本教程
本教程是免费且开源的，所有代码均使用 MIT 许可证 - 因此您可以随意使用它。 我希望您会喜欢本教程，并制作出色的游戏！
如果您喜欢这个教程并希望我继续写作，请考虑支持我的 Patreon。
有没有想过，如果一只掘地虫 (Umber Hulk)（或其他隧道生物）真的喝醉了，并且开始了一场地下城雕刻狂欢，会发生什么？ 醉汉漫步算法回答了这个问题 - 或者更准确地说，如果一大群怪物喝了太多酒会发生什么。 听起来很疯狂，但这确实是制作自然地下城的好方法。
初始脚手架
和往常一样，我们将从之前地图教程中的脚手架开始。 我们已经做过很多次了，现在应该轻车熟路了！ 在 map_builders/drunkard.rs 中，构建一个新的 DrunkardsWalkBuilder 类。 我们将保留来自细胞自动机的基于区域的放置方式 - 但删除地图构建代码。 这是脚手架代码：
#![allow(unused)] fn main() { use super::{MapBuilder, Map, TileType, Position, spawner, SHOW_MAPGEN_VISUALIZER}; use rltk::RandomNumberGenerator; use specs::prelude::*; use std::collections::HashMap; pub struct DrunkardsWalkBuilder { map : Map, starting_position : Position, depth: i32, history: Vec<Map>, noise_areas : HashMap<i32, Vec<usize>> } impl MapBuilder for DrunkardsWalkBuilder { fn get_map(&self) -> Map { self.map.clone() } fn get_starting_position(&self) -> Position { self.starting_position.clone() } fn get_snapshot_history(&self) -> Vec<Map> { self.history.clone() } fn build_map(&mut self) { self.build(); } fn spawn_entities(&mut self, ecs : &mut World) { for area in self.noise_areas.iter() { spawner::spawn_region(ecs, area.1, self.depth); } } fn take_snapshot(&mut self) { if SHOW_MAPGEN_VISUALIZER { let mut snapshot = self.map.clone(); for v in snapshot.revealed_tiles.iter_mut() { *v = true; } self.history.push(snapshot); } } } impl DrunkardsWalkBuilder { pub fn new(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)] fn build(&mut self) { let mut rng = RandomNumberGenerator::new(); // 设置中心起始点 self.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); // 查找从起始点可以到达的所有图块 let 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); let mut exit_tile = (0, 0.0f32); for (i, tile) in self.map.tiles.iter_mut().enumerate() { if *tile == TileType::Floor { let distance_to_start = dijkstra_map.map[i]; // 我们无法到达此图块 - 因此我们将其设为墙壁 if distance_to_start == std::f32::MAX { *tile = TileType::Wall; } else { // 如果它比我们当前的出口候选更远，则移动出口 if distance_to_start > exit_tile.1 { exit_tile.0 = i; exit_tile.1 = distance_to_start; } } } } self.take_snapshot(); // 放置楼梯 self.map.tiles[exit_tile.0] = TileType::DownStairs; self.take_snapshot(); // 现在我们构建一个噪声地图，用于稍后生成实体 let mut noise = rltk::FastNoise::seeded(rng.roll_dice(1, 65536) as u64); noise.set_noise_type(rltk::NoiseType::Cellular); noise.set_frequency(0.08); noise.set_cellular_distance_function(rltk::CellularDistanceFunction::Manhattan); for y in 1 .. self.map.height-1 { for x in 1 .. self.map.width-1 { let idx = self.map.xy_idx(x, y); if self.map.tiles[idx] == TileType::Floor { let cell_value_f = noise.get_noise(x as f32, y as f32) * 10240.0; let cell_value = cell_value_f as i32; if self.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]); } } } } } } }
我们保留了来自细胞自动机章节的大部分工作，因为它在这里也能帮助我们。 我们还进入 map_builders/mod.rs 并再次强制“随机”系统选择我们的新代码：
#![allow(unused)] fn main() { pub fn random_builder(new_depth: i32) -> Box<dyn MapBuilder> { /*let mut rng = rltk::RandomNumberGenerator::new(); let builder = rng.roll_dice(1, 4); match builder { 1 => Box::new(BspDungeonBuilder::new(new_depth)), 2 => Box::new(BspInteriorBuilder::new(new_depth)), 3 => Box::new(CellularAutomataBuilder::new(new_depth)), _ => Box::new(SimpleMapBuilder::new(new_depth)) }*/ Box::new(DrunkardsWalkBuilder::new(new_depth)) } }
不要重复自己 (DRY 原则)
由于我们正在重用来自细胞自动机的完全相同的代码，我们应该将通用代码放入 map_builders/common.rs 中。 这样可以节省打字时间，并节省编译器重复重新制作相同代码的时间（从而减小程序的大小）。 因此，在 common.rs 中，我们将通用代码重构为一些函数。 在 common.rs 中，我们创建一个新函数 - remove_unreachable_areas_returning_most_distant：
#![allow(unused)] fn main() { /// 搜索地图，删除无法到达的区域并返回最远的图块。 pub fn remove_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 as usize, map.height as usize, &map_starts , map, 200.0); let mut 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]; // 我们无法到达此图块 - 因此我们将其设为墙壁 if distance_to_start == std::f32::MAX { *tile = TileType::Wall; } else { // 如果它比我们当前的出口候选更远，则移动出口 if distance_to_start > exit_tile.1 { exit_tile.0 = i; exit_tile.1 = distance_to_start; } } } } exit_tile.0 } }
我们将创建第二个函数 generate_voronoi_spawn_regions：
#![allow(unused)] fn main() { /// 生成区域的 Voronoi/细胞噪声地图，并将其划分为生成区域。 #[allow(clippy::map_entry)] pub fn generate_voronoi_spawn_regions(map: &Map, rng : &mut rltk::RandomNumberGenerator) -> HashMap<i32, Vec<usize>> { let mut noise_areas : HashMap<i32, Vec<usize>> = HashMap::new(); let mut noise = rltk::FastNoise::seeded(rng.roll_dice(1, 65536) as u64); noise.set_noise_type(rltk::NoiseType::Cellular); noise.set_frequency(0.08); noise.set_cellular_distance_function(rltk::CellularDistanceFunction::Manhattan); for y in 1 .. map.height-1 { for x in 1 .. map.width-1 { let idx = map.xy_idx(x, y); if map.tiles[idx] == TileType::Floor { let cell_value_f = noise.get_noise(x as f32, y as f32) * 10240.0; let cell_value = cell_value_f as i32; 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 } }
将这些函数插入到我们的 build 函数中，可以大大减少样板代码部分：
#![allow(unused)] fn main() { // 查找从起始点可以到达的所有图块 let exit_tile = remove_unreachable_areas_returning_most_distant(&mut self.map, start_idx); self.take_snapshot(); // 放置楼梯 self.map.tiles[exit_tile] = TileType::DownStairs; self.take_snapshot(); // 现在我们构建一个噪声地图，用于稍后生成实体 self.noise_areas = generate_voronoi_spawn_regions(&self.map, &mut rng); }
在示例中，我回到了 cellular_automata 部分并做了同样的操作。
这基本上是我们之前拥有的相同代码（因此，此处不再解释），但包装在一个函数中（并接受可变地图引用 - 因此它会更改您给它的地图，并将起始点作为参数）。
醉汉漫步
该算法背后的基本思想很简单：
- 选择一个中心起始点，并将其转换为地板。
- 我们计算地图上有多少地板空间，并迭代直到我们将一定百分比（在示例中使用 50%）的地图转换为地板。
- 在起始点生成一个醉汉。 醉汉具有“生命周期”和“位置”。
- 当醉汉还活着时：
- 减少醉汉的生命周期（我喜欢认为他们昏过去睡着了）。
- 掷一个四面骰子。
- 如果我们掷出 1，则将醉汉向北移动。
- 如果我们掷出 2，则将醉汉向南移动。
- 如果我们掷出 3，则将醉汉向东移动。
- 如果我们掷出 4，则将醉汉向西移动。
- 醉汉落脚的图块变成地板。
这就是全部：我们不断生成醉汉，直到我们有足够的地图覆盖率。 这是一个实现：
#![allow(unused)] fn main() { // 设置中心起始点 self.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) as usize; let mut floor_tile_count = self.map.tiles.iter().filter(|a| **a == TileType::Floor).count(); let mut digger_count = 0; let mut active_digger_count = 0; while floor_tile_count < desired_floor_tiles { let mut did_something = false; let mut drunk_x = self.starting_position.x; let mut drunk_y = self.starting_position.y; let mut drunk_life = 400; while drunk_life > 0 { let drunk_idx = self.map.xy_idx(drunk_x, drunk_y); if self.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 in self.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)); }
这个实现扩展了很多东西，并且可以更短 - 但为了清晰起见，我们将其保留得很大且很明显。 我们还将很多东西变成了可以成为常量的变量 - 它更容易阅读，并且旨在易于“玩弄”值。 它还在控制台中打印状态更新，显示发生了什么。
如果您现在 cargo run，您将获得一张非常漂亮的开放地图：
.
管理挖掘者的酗酒问题
有很多方法可以调整“醉汉漫步”算法以生成不同的地图类型。 由于这些方法可以产生完全不同的地图，因此让我们自定义算法的接口，以提供几种不同的运行方式。 我们将首先创建一个 struct 来保存参数集：
#![allow(unused)] fn main() { #[derive(PartialEq, Copy, Clone)] pub enum DrunkSpawnMode { StartingPoint, Random } pub struct DrunkardSettings { pub spawn_mode : DrunkSpawnMode } }
现在我们将修改 new 和结构本身以接受它：
#![allow(unused)] fn main() { pub struct DrunkardsWalkBuilder { map : Map, starting_position : Position, depth: i32, history: Vec<Map>, noise_areas : HashMap<i32, Vec<usize>>, settings : DrunkardSettings } ... impl DrunkardsWalkBuilder { pub fn new(new_depth : i32, settings: DrunkardSettings) -> DrunkardsWalkBuilder { DrunkardsWalkBuilder{ map : Map::new(new_depth), starting_position : Position{ x: 0, y : 0 }, depth : new_depth, history: Vec::new(), noise_areas : HashMap::new(), settings } } ... }
我们还将修改“随机”构建器以接受设置：
#![allow(unused)] fn main() { Box::new(DrunkardsWalkBuilder::new(new_depth, DrunkardSettings{ spawn_mode: DrunkSpawnMode::StartingPoint })) }
现在我们有了一个调整挖掘者醉酒程度的机制！
改变醉酒漫步者的起始点
我们在上一节中通过创建 DrunkSpawnMode 暗示了这一点 - 我们将看看如果我们更改醉酒挖掘者（在第一个之后）的生成方式会发生什么。 将 random_builder 更改为 DrunkSpawnMode::Random，然后修改 build（在 drunkard.rs 中）以使用它：
#![allow(unused)] fn main() { ... while floor_tile_count < desired_floor_tiles { let mut did_something = false; let mut drunk_x; let mut drunk_y; match self.settings.spawn_mode { DrunkSpawnMode::StartingPoint => { drunk_x = self.starting_position.x; drunk_y = self.starting_position.y; } DrunkSpawnMode::Random => { if digger_count == 0 { drunk_x = self.starting_position.x; drunk_y = self.starting_position.y; } else { drunk_x = rng.roll_dice(1, self.map.width - 3) + 1; drunk_y = rng.roll_dice(1, self.map.height - 3) + 1; } } } let mut drunk_life = 400; ... }
这是一个相对容易的更改：如果我们在“随机”模式下，则第一个挖掘者的起始位置是地图的中心（以确保我们在楼梯周围有一些空间），然后对于每个后续迭代，起始位置是随机地图位置。 它生成这样的地图：
.
这是一个更加分散的地图。 更少的大型中心区域，更像是一个广阔的洞穴。 一个方便的变体！
修改醉汉昏倒所需的时间
另一个可以调整的参数是醉汉保持清醒的时间。 这会严重改变生成地图的特性。 我们将其添加到设置中：
#![allow(unused)] fn main() { pub struct DrunkardSettings { pub spawn_mode : DrunkSpawnMode, pub drunken_lifetime : i32 } }
我们将告诉 random_builder 函数使用较短的生命周期：
#![allow(unused)] fn main() { Box::new(DrunkardsWalkBuilder::new(new_depth, DrunkardSettings{ spawn_mode: DrunkSpawnMode::Random, drunken_lifetime: 100 })) }
我们将修改 build 代码以实际使用它：
#![allow(unused)] fn main() { let mut drunk_life = self.settings.drunken_lifetime; }
这是一个简单的更改 - 并且极大地改变了生成地图的性质。 每个挖掘者只能走之前挖掘者距离的四分之一（更烈的啤酒！），因此他们倾向于挖掘的地图区域更少。 这导致更多的迭代，并且由于它们是随机开始的，因此您倾向于看到形成更多明显的地图区域 - 并希望它们连接起来（如果它们没有连接起来，它们将在最后被剔除）。
使用 100 生命周期的 cargo run，随机放置的醉汉会产生类似这样的结果：
.
更改期望的填充百分比
最后，我们将调整我们希望用地板覆盖地图多少百分比。 数字越低，您生成的墙壁越多（开放区域越少）。 我们将再次修改 DrunkardSettings：
#![allow(unused)] fn main() { pub struct DrunkardSettings { pub spawn_mode : DrunkSpawnMode, pub drunken_lifetime : i32, pub floor_percent: f32 } }
我们还更改了构建器中的一行代码：
#![allow(unused)] fn main() { let desired_floor_tiles = (self.settings.floor_percent * total_tiles as f32) as usize; }
我们之前将 desired_floor_tiles 设置为 total_tiles / 2 - 这在新系统中将表示为 0.5。 让我们尝试在 random_builder 中将其更改为 0.4：
#![allow(unused)] fn main() { Box::new(DrunkardsWalkBuilder::new(new_depth, DrunkardSettings{ spawn_mode: DrunkSpawnMode::Random, drunken_lifetime: 200, floor_percent: 0.4 })) }
如果您现在 cargo run，您将看到我们形成的开放区域甚至更少：
.
构建一些预设构造器
现在我们有了这些参数可以玩，让我们制作更多构造器，以消除 mod.rs 中的调用者了解算法细节的需求：
#![allow(unused)] fn main() { pub fn new(new_depth : i32, settings: DrunkardSettings) -> DrunkardsWalkBuilder { DrunkardsWalkBuilder{ map : Map::new(new_depth), starting_position : Position{ x: 0, y : 0 }, depth : new_depth, history: Vec::new(), noise_areas : HashMap::new(), settings } } pub fn open_area(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(), settings : DrunkardSettings{ spawn_mode: DrunkSpawnMode::StartingPoint, drunken_lifetime: 400, floor_percent: 0.5 } } } pub fn open_halls(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(), settings : DrunkardSettings{ spawn_mode: DrunkSpawnMode::Random, drunken_lifetime: 400, floor_percent: 0.5 } } } pub fn winding_passages(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(), settings : DrunkardSettings{ spawn_mode: DrunkSpawnMode::Random, drunken_lifetime: 100, floor_percent: 0.4 } } } }
现在我们可以修改我们的 random_builder 函数，使其再次随机 - 并提供三种不同的地图类型：
#![allow(unused)] fn main() { pub fn random_builder(new_depth: i32) -> Box<dyn MapBuilder> { let mut rng = rltk::RandomNumberGenerator::new(); let builder = rng.roll_dice(1, 7); match builder { 1 => Box::new(BspDungeonBuilder::new(new_depth)), 2 => Box::new(BspInteriorBuilder::new(new_depth)), 3 => Box::new(CellularAutomataBuilder::new(new_depth)), 4 => Box::new(DrunkardsWalkBuilder::open_area(new_depth)), 5 => Box::new(DrunkardsWalkBuilder::open_halls(new_depth)), 6 => Box::new(DrunkardsWalkBuilder::winding_passages(new_depth)), _ => Box::new(SimpleMapBuilder::new(new_depth)) } } }
总结
我们完成了醉酒地图构建（我从没想过会打出这些词……）！ 这是一种非常灵活的算法，可用于制作许多不同的地图类型。 它也与其他算法很好地结合，我们将在以后的章节中看到。
本章的源代码可以在这里找到
在您的浏览器中使用 WebAssembly 运行本章的示例（需要 WebGL2）
版权 (C) 2019, Herbert Wolverson.