迷宫/地宫生成
关于本教程
本教程是免费且开源的，所有代码均使用 MIT 许可证 - 因此您可以随意使用。 我希望您会喜欢本教程，并制作出色的游戏！
如果您喜欢这个教程并希望我继续写作，请考虑支持我的 Patreon。
地牢爬行游戏的一个主要内容是古老的迷宫，通常以弥诺陶洛斯为特色。《地牢爬行：石汤 (Dungeon Crawl: Stone Soup)》 有一个字面意义上的弥诺陶洛斯迷宫，《托姆 4 (Tome 4)》 有沙虫迷宫，《独 Knight (One Knight)》 有精灵树篱迷宫。这些关卡可能会让玩家感到恼火，应该谨慎使用：很多玩家并不真正喜欢为了找到出口而进行的乏味探索。本章将向您展示如何制作迷宫！
脚手架 (Scaffolding)
和之前一样，我们将使用上一章作为脚手架 (scaffolding) - 并将我们的 “随机” 构建器设置为使用新的设计。在 map_builders/maze.rs 中，放置以下代码：
#![allow(unused)] fn main() { use super::{MapBuilder, Map, TileType, Position, spawner, SHOW_MAPGEN_VISUALIZER, remove_unreachable_areas_returning_most_distant, generate_voronoi_spawn_regions}; use rltk::RandomNumberGenerator; use specs::prelude::*; use std::collections::HashMap; pub struct MazeBuilder { map : Map, starting_position : Position, depth: i32, history: Vec<Map>, noise_areas : HashMap<i32, Vec<usize>> } impl MapBuilder for MazeBuilder { 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 MazeBuilder { pub fn new(new_depth : i32) -> MazeBuilder { MazeBuilder{ 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(); // 找到一个起始点；从中间开始向左走，直到找到一个空地块 // Find a starting point; start at the middle and walk left until we find an open tile self.starting_position = Position{ x: self.map.width / 2, y : self.map.height / 2 }; let mut start_idx = self.map.xy_idx(self.starting_position.x, self.starting_position.y); while self.map.tiles[start_idx] != TileType::Floor { self.starting_position.x -= 1; start_idx = self.map.xy_idx(self.starting_position.x, self.starting_position.y); } self.take_snapshot(); // 找到所有我们可以从起点到达的地块 // Find all tiles we can reach from the starting point let exit_tile = remove_unreachable_areas_returning_most_distant(&mut self.map, start_idx); self.take_snapshot(); // 放置楼梯 // Place the stairs self.map.tiles[exit_tile] = TileType::DownStairs; self.take_snapshot(); // 现在我们构建一个噪声图，以便稍后在生成实体时使用 // Now we build a noise map for use in spawning entities later self.noise_areas = generate_voronoi_spawn_regions(&self.map, &mut rng); } } }
在 random_builder (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, 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)) }*/ Box::new(MazeBuilder::new(new_depth)) } }
实际构建迷宫
有很多优秀的迷宫构建算法，所有这些算法都保证给你一个完美可解的迷宫。在《独 Knight in the Dungeon》中，我的迷宫构建代码是基于一个相对标准的实现 - Cyucelen 的 mazeGenerator。这是一个有趣的算法，因为 - 像许多迷宫算法一样 - 它假设墙壁是地块网格的一部分，而不是拥有单独的墙壁实体。这不适用于我们正在使用的地块地图类型，因此我们在实际地图一半的分辨率下生成网格，并根据网格中的墙壁邻接信息生成墙壁。
该算法最初是带有到处都是指针的 C++ 代码，并且花了一些时间移植。算法中最基本的结构：Cell。单元格 (Cells) 是地图上的地块：
#![allow(unused)] fn main() { const TOP : usize = 0; const RIGHT : usize = 1; const BOTTOM : usize = 2; const LEFT : usize = 3; #[derive(Copy, Clone)] struct Cell { row: i32, column: i32, walls: [bool; 4], visited: bool, } }
我们定义了四个常量：TOP、RIGHT、BOTTOM 和 LEFT，并将它们分配给数字 0..3。当算法想要引用方向时，我们会使用这些常量。查看 Cell，它相对简单：
row和column定义了单元格 (cell) 在地图上的位置。walls是一个array，为我们定义的每个方向都有一个bool。Rust 数组（静态的，你不能像vector那样调整它们的大小）使用语法[TYPE ; NUMBER_OF_ELEMENTS]定义。大多数时候我们只使用 vectors，因为我们喜欢动态大小调整；在这种情况下，元素的数量是预先知道的，因此使用低开销类型是有意义的。visited- 一个布尔值，指示我们是否之前查看过该单元格 (cell)。
Cell 还定义了一些方法。第一个是它的构造函数：
#![allow(unused)] fn main() { impl Cell { fn new(row: i32, column: i32) -> Cell { Cell{ row, column, walls: [true, true, true, true], visited: false } } ... }
这是一个简单的构造函数：它创建一个在每个方向都有墙壁，且之前未访问过的单元格 (cell)。Cells 还定义了一个名为 remove_walls 的函数：
#![allow(unused)] fn main() { fn remove_walls(&mut self, next : &mut Cell) { let x = self.column - next.column; let y = self.row - next.row; if x == 1 { self.walls[LEFT] = false; next.walls[RIGHT] = false; } else if x == -1 { self.walls[RIGHT] = false; next.walls[LEFT] = false; } else if y == 1 { self.walls[TOP] = false; next.walls[BOTTOM] = false; } else if y == -1 { self.walls[BOTTOM] = false; next.walls[TOP] = false; } } }
哦，哦，这里有一些新东西：
- 我们将
x设置为 我们 的column值，减去下一个单元格 (cell) 的column值。 - 我们对
y做同样的事情 - 但使用row值。 - 如果
x等于 1，那么next的列必须大于我们的列值。换句话说，next单元格 (cell) 位于我们当前位置的右侧。所以我们移除了右侧的墙壁。 - 同样，如果
x是-1，那么我们一定是向左移动 - 所以我们移除了左侧的墙壁。 - 再次，如果
y是1，我们一定是向上移动。所以我们移除了上方的墙壁。 - 最后，如果
y是-1，我们一定是向下移动 - 所以我们移除了下方的墙壁。
呼！Cell 完成了。现在实际使用它。在我们的迷宫算法中，Cell 是 Grid 的一部分。这是 Grid 的基本定义：
#![allow(unused)] fn main() { struct Grid<'a> { width: i32, height: i32, cells: Vec<Cell>, backtrace: Vec<usize>, current: usize, rng : &'a mut RandomNumberGenerator } }
关于 Grid 的一些注释：
<'a>是一个 生命周期 (lifetime) 说明符。我们必须指定一个，以便 Rust 的借用检查器 (borrow checker) 可以确保Grid在我们删除RandomNumberGenerator之前不会过期。因为我们将 可变引用 (mutable reference) 传递给调用者的 RNG，所以 Rust 需要这个来确保 RNG 在我们完成使用之前不会消失。这种类型的错误经常影响 C/C++ 用户，因此 Rust 使其非常难以出错。不幸的是，使其难以出错的代价是一些丑陋的语法！- 我们有定义迷宫大小的
width和height。 - Cells 只是我们之前定义的
Cell类型的Vector。 backtrace由算法用于递归回溯 (back-tracking)，以确保每个单元格 (cell) 都已被处理。它只是单元格 (cell) 索引的vector-cellsvector 的索引。current由算法使用，以告知我们当前正在处理哪个Cell。rng是导致丑陋的生命周期 (lifetime) 存在的原因；我们想使用在build函数中构建的随机数生成器，所以我们在这里存储对它的引用。由于获取随机数会更改变量的内容，因此我们必须存储可变引用 (mutable reference)。真正丑陋的&'a mut表明它是一个引用，具有生命周期 (lifetime)'a（如上定义）并且是可变的/可更改的。
Grid 实现了相当多的方法。首先是构造函数：
#![allow(unused)] fn main() { impl<'a> Grid<'a> { fn new(width: i32, height:i32, rng: &mut RandomNumberGenerator) -> Grid { let mut grid = Grid{ width, height, cells: Vec::new(), backtrace: Vec::new(), current: 0, rng }; for row in 0..height { for column in 0..width { grid.cells.push(Cell::new(row, column)); } } grid } ... }
请注意，我们再次不得不为生命周期 (lifetime) 使用一些丑陋的语法！构造函数本身非常简单：它创建一个新的 Grid 结构，其中包含指定的 width 和 height，一个新的单元格 (cells) vector，一个新的（空的）backtrace vector，将 current 设置为 0 并存储随机数生成器引用。然后它迭代网格的行和列，将新的 Cell 结构推送到 cells vector，并按其位置编号。
Grid 还实现了 calculate_index：
#![allow(unused)] fn main() { fn calculate_index(&self, row: i32, column: i32) -> i32 { if row < 0 || column < 0 || column > self.width-1 || row > self.height-1 { -1 } else { column + (row * self.width) } } }
这与我们 map 的 xy_idx 函数非常相似：它接受行和列坐标，并返回可以在其中找到单元格 (cell) 的数组索引。它还进行一些边界检查 (bounds checking)，如果坐标无效，则返回 -1。接下来，我们提供 get_available_neighbors：
#![allow(unused)] fn main() { fn get_available_neighbors(&self) -> Vec<usize> { let mut neighbors : Vec<usize> = Vec::new(); let current_row = self.cells[self.current].row; let current_column = self.cells[self.current].column; let neighbor_indices : [i32; 4] = [ self.calculate_index(current_row -1, current_column), self.calculate_index(current_row, current_column + 1), self.calculate_index(current_row + 1, current_column), self.calculate_index(current_row, current_column - 1) ]; for i in neighbor_indices.iter() { if *i != -1 && !self.cells[*i as usize].visited { neighbors.push(*i as usize); } } neighbors } }
此函数提供从 current 单元格 (cell) 可用的出口。它的工作原理是获取当前单元格 (cell) 的 row 和 column 坐标，然后将对 calculate_index 的调用放入一个数组（对应于我们用 Cell 定义的方向）。最后，它迭代该数组，如果值有效（大于 -1），并且我们之前没有去过那里（visited 检查），则将其推送到 neighbors 列表。然后它返回 neighbors。对任何单元格 (cell) 地址的调用都将返回一个 vector，其中列出了我们可以到达的所有相邻单元格 (cells)（忽略墙壁）。我们首先在 find_next_cell 中使用它：
#![allow(unused)] fn main() { fn find_next_cell(&mut self) -> Option<usize> { let neighbors = self.get_available_neighbors(); if !neighbors.is_empty() { if neighbors.len() == 1 { return Some(neighbors[0]); } else { return Some(neighbors[(self.rng.roll_dice(1, neighbors.len() as i32)-1) as usize]); } } None } }
此函数很有趣，因为它返回一个 Option。当前单元格 (cell) 可能无路可走 - 在这种情况下，它返回 None。否则，它返回 Some 以及下一个目的地的数组索引。它的工作原理是：
- 获取当前单元格 (cell) 的邻居列表。
- 如果有邻居：
- 如果只有一个邻居，则返回它。
- 如果有多个邻居，则随机选择一个并返回它。
- 如果没有邻居，则返回
None。
我们在 generate_maze 中使用它：
#![allow(unused)] fn main() { fn generate_maze(&mut self, generator : &mut MazeBuilder) { loop { self.cells[self.current].visited = true; let next = self.find_next_cell(); match next { Some(next) => { self.cells[next].visited = true; self.backtrace.push(self.current); // __lower_part__ __higher_part_ // / \ / \ // --------cell1------ | cell2----------- let (lower_part, higher_part) = self.cells.split_at_mut(std::cmp::max(self.current, next)); let cell1 = &mut lower_part[std::cmp::min(self.current, next)]; let cell2 = &mut higher_part[0]; cell1.remove_walls(cell2); self.current = next; } None => { if !self.backtrace.is_empty() { self.current = self.backtrace[0]; self.backtrace.remove(0); } else { break; } } } self.copy_to_map(&mut generator.map); generator.take_snapshot(); } } }
所以现在我们进入了实际的算法！让我们逐步了解它是如何工作的：
- 我们从一个
loop开始。我们以前没有用过这个（你可以在 这里 阅读有关它们的信息）。基本上，一个loop永远运行 - 直到它遇到break语句。 - 我们将
current单元格 (cell) 中的visited值设置为true。 - 我们将当前单元格 (cell) 添加到
backtrace列表的开头。 - 我们调用
find_next_cell并将其索引设置在变量next中。如果这是我们第一次运行，我们将从起始单元格 (cell) 获得一个随机方向。否则，我们将从我们正在访问的current单元格 (cell) 获得一个出口。 - 如果
next有一个值，那么：- 将 cells 分割为两个可变引用 (mutable references)。我们将需要对同一个切片进行两个可变引用 (mutable references)，Rust 通常不允许这样做，但是我们可以将我们的切片分割为两个不重叠的部分。这是一个常见的用例，Rust 提供了安全的函数来完全做到 这一点。
- 从第一部分获取索引较低的单元格 (cell) 的可变引用 (mutable reference)，从第二部分的开头获取第二个单元格 (cell) 的可变引用 (mutable reference)。
- 我们在 cell1 单元格 (cell) 上调用
remove_walls，引用 cell2 单元格 (cell)。
- 如果
next没有值（它等于None），我们：- 如果
backtrace不为空，我们将current设置为backtrace列表中的第一个值。 - 如果
backtrace为空，我们就完成了 - 所以我们break跳出循环。
- 如果
- 最后，我们调用
copy_to_map- 它将迷宫复制到地图（稍后会详细介绍），并为迭代地图生成渲染器拍摄快照 (snapshot)。
那么为什么它会起作用呢？
- 前几次迭代将获得一个未访问的邻居，在迷宫中开辟一条清晰的路径。沿途的每一步，我们访问过的单元格 (cell) 都会被添加到
backtrace中。这实际上是在迷宫中醉酒行走，但确保我们无法返回到单元格 (cell)。 - 当我们到达一个没有邻居的点（我们到达迷宫的尽头）时，算法会将
current更改为我们backtrace列表中的第一个条目。然后它将从那里随机行走，填充更多单元格 (cells)。 - 如果那个点无处可去，它会回溯
backtrace列表。 - 这种情况会重复发生，直到每个单元格 (cell) 都被访问过，这意味着
backtrace和neighbors都为空。我们就完成了！
理解这一点的最好方法是观看它的实际操作：
.
最后，还有 copy_to_map 函数：
#![allow(unused)] fn main() { fn copy_to_map(&self, map : &mut Map) { // 清空地图 // Clear the map for i in map.tiles.iter_mut() { *i = TileType::Wall; } for cell in self.cells.iter() { let x = cell.column + 1; let y = cell.row + 1; let idx = map.xy_idx(x * 2, y * 2); map.tiles[idx] = TileType::Floor; if !cell.walls[TOP] { map.tiles[idx - map.width as usize] = TileType::Floor } if !cell.walls[RIGHT] { map.tiles[idx + 1] = TileType::Floor } if !cell.walls[BOTTOM] { map.tiles[idx + map.width as usize] = TileType::Floor } if !cell.walls[LEFT] { map.tiles[idx - 1] = TileType::Floor } } } }
这就是 Grid/Cell 和我们的地图格式之间的不匹配得到解决的地方：迷宫结构中的每个 Cell 都可以在四个主要方向中的任何一个方向上都有墙壁。我们的地图不是那样工作的：墙壁不是地块的一部分，它们是地块。所以我们将 Grid 的大小加倍，并在没有墙壁的地方雕刻地板。让我们逐步了解这个函数：
- 我们将地图中的所有单元格 (cells) 设置为实心墙。
- 对于网格中的每个单元格 (cell)，我们执行以下操作：
- 将
x计算为单元格 (cell) 的column值，加一。 - 将
y计算为单元格 (cell) 的row值，加一。 - 将
idx设置为 两倍x和y值的map.xy_idx：因此展开每个单元格 (cell)。 - 我们将
idx处的地图地块设置为地板。 - 如果我们引用的
Cell没有TOP墙壁，我们将idx地块上方的地图地块设置为地板。 - 我们对其他方向重复该操作。
- 将
加速生成器
通过在每次迭代时进行快照 (snapshot)，我们浪费了大量时间 - 我们正在构建一个巨大的快照 (snapshot) 地图列表。这对于学习算法来说很棒，但在玩游戏时只是花费的时间太长了。我们将修改我们的 generate_maze 函数来计算迭代次数，并且仅每 10 次记录一次：
#![allow(unused)] fn main() { fn generate_maze(&mut self, generator : &mut MazeBuilder) { let mut i = 0; loop { self.cells[self.current].visited = true; let next = self.find_next_cell(); match next { Some(next) => { self.cells[next].visited = true; self.backtrace.push(self.current); unsafe { let next_cell : *mut Cell = &mut self.cells[next]; let current_cell = &mut self.cells[self.current]; current_cell.remove_walls(next_cell); } self.current = next; } None => { if !self.backtrace.is_empty() { self.current = self.backtrace[0]; self.backtrace.remove(0); } else { break; } } } if i % 50 == 0 { self.copy_to_map(&mut generator.map); generator.take_snapshot(); } i += 1; } } }
这使生成器的速度提高到一个合理的水平，您仍然可以观看迷宫的形成。
找到出口
幸运的是，我们当前的算法将从 Cell (1,1) 开始 - 这对应于地图位置 (2,2)。所以在 build 中，我们可以轻松地指定一个起点：
#![allow(unused)] fn main() { self.starting_position = Position{ x: 2, y : 2 }; let start_idx = self.map.xy_idx(self.starting_position.x, self.starting_position.y); self.take_snapshot(); }
然后我们可以使用我们在最后两个示例中使用的相同代码来找到出口：
#![allow(unused)] fn main() { // 找到所有我们可以从起点到达的地块 // Find all tiles we can reach from the starting point let exit_tile = remove_unreachable_areas_returning_most_distant(&mut self.map, start_idx); self.take_snapshot(); // 放置楼梯 // Place the stairs self.map.tiles[exit_tile] = TileType::DownStairs; self.take_snapshot(); // 现在我们构建一个噪声图，以便稍后在生成实体时使用 // Now we build a noise map for use in spawning entities later self.noise_areas = generate_voronoi_spawn_regions(&self.map, &mut rng); }
这也是对库的 Dijkstra 地图代码的出色测试。它可以非常快速地解决迷宫！
恢复随机性
再一次，我们应该恢复 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, 8); 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)), 7 => Box::new(MazeBuilder::new(new_depth)), _ => Box::new(SimpleMapBuilder::new(new_depth)) } } }
总结 (Wrap-Up)
在本章中，我们构建了一个迷宫。这是一个保证可解的迷宫，因此不存在无法通关的关卡的风险。您仍然必须谨慎使用这种类型的地图：它们可以制作出色的单次地图，并且真的会惹恼玩家！
本章的源代码可以在这里找到
在您的浏览器中使用 Web Assembly 运行本章的示例（需要 WebGL2）
版权 (Copyright) (C) 2019, Herbert Wolverson.