细胞自动机地图

关于本教程

本教程是免费且开源的，所有代码均使用 MIT 许可证 - 因此您可以随意使用它。我希望您会喜欢本教程，并制作出色的游戏！

如果您喜欢这个教程并希望我继续写作，请考虑支持我的 Patreon。

有时候，您需要从矩形房间中解脱出来。您可能想要一个漂亮的、看起来自然的洞穴；一条蜿蜒的森林小径，或是一个阴森的采石场。《地牢骑士》（One Knight in the Dungeon）使用了细胞自动机来实现这个目的，其灵感来源于这篇优秀的文章。本章将帮助您创建看起来自然的地图。

脚手架

再一次，我们将从之前的教程中提取大量代码，并将其重新用于新的生成器。创建一个新文件 map_builders/cellular_automata.rs，并将以下内容放入其中：

#![allow(unused)]
fn main() {
use super::{MapBuilder, Map, Rect, apply_room_to_map,
    TileType, Position, spawner, SHOW_MAPGEN_VISUALIZER};
use rltk::RandomNumberGenerator;
use specs::prelude::*;

const MIN_ROOM_SIZE : i32 = 8;

pub struct CellularAutomataBuilder {
    map : Map,
    starting_position : Position,
    depth: i32,
    history: Vec<Map>
}

impl MapBuilder for CellularAutomataBuilder {
    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) {
        // 我们也需要重写这个。
    }

    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 CellularAutomataBuilder {
    pub fn new(new_depth : i32) -> CellularAutomataBuilder {
        CellularAutomataBuilder{
            map : Map::new(new_depth),
            starting_position : Position{ x: 0, y : 0 },
            depth : new_depth,
            history: Vec::new(),
        }
    }
}
}

再一次，我们将使名称 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, 3);
    match builder {
        1 => Box::new(BspDungeonBuilder::new(new_depth)),
        2 => Box::new(BspInteriorBuilder::new(new_depth)),
        _ => Box::new(SimpleMapBuilder::new(new_depth))
    }*/
    Box::new(CellularAutomataBuilder::new(new_depth))
}
}

组合基本的地图

第一步是使地图完全混乱，大约 55% 的地块是实心的。您可以调整这个数字以获得不同的效果，但我非常喜欢这个结果。这是 build 函数：

#![allow(unused)]
fn main() {
fn build(&mut self) {
        let mut rng = RandomNumberGenerator::new();

        // 首先，我们完全随机化地图，将其中的 55% 设置为地板。
        for y in 1..self.map.height-1 {
            for x in 1..self.map.width-1 {
                let roll = rng.roll_dice(1, 100);
                let idx = self.map.xy_idx(x, y);
                if roll > 55 { self.map.tiles[idx] = TileType::Floor }
                else { self.map.tiles[idx] = TileType::Wall }
            }
        }
        self.take_snapshot();
}
}

这制造了一个乱七八糟的、无法使用的关卡。墙壁和地板到处都是，没有任何规律可循 - 而且完全无法游玩。这没关系，因为细胞自动机旨在从噪声中生成关卡。它的工作原理是迭代每个单元格，计算邻居的数量，并根据密度将墙壁变成地板或墙壁。这是一个可工作的生成器：

#![allow(unused)]
fn main() {
fn build(&mut self) {
    let mut rng = RandomNumberGenerator::new();

    // 首先，我们完全随机化地图，将其中的 55% 设置为地板。
    for y in 1..self.map.height-1 {
        for x in 1..self.map.width-1 {
            let roll = rng.roll_dice(1, 100);
            let idx = self.map.xy_idx(x, y);
            if roll > 55 { self.map.tiles[idx] = TileType::Floor }
            else { self.map.tiles[idx] = TileType::Wall }
        }
    }
    self.take_snapshot();

    // 现在我们迭代地应用细胞自动机规则
    for _i in 0..15 {
        let mut newtiles = self.map.tiles.clone();

        for y in 1..self.map.height-1 {
            for x in 1..self.map.width-1 {
                let idx = self.map.xy_idx(x, y);
                let mut neighbors = 0;
                if self.map.tiles[idx - 1] == TileType::Wall { neighbors += 1; }
                if self.map.tiles[idx + 1] == TileType::Wall { neighbors += 1; }
                if self.map.tiles[idx - self.map.width as usize] == TileType::Wall { neighbors += 1; }
                if self.map.tiles[idx + self.map.width as usize] == TileType::Wall { neighbors += 1; }
                if self.map.tiles[idx - (self.map.width as usize - 1)] == TileType::Wall { neighbors += 1; }
                if self.map.tiles[idx - (self.map.width as usize + 1)] == TileType::Wall { neighbors += 1; }
                if self.map.tiles[idx + (self.map.width as usize - 1)] == TileType::Wall { neighbors += 1; }
                if self.map.tiles[idx + (self.map.width as usize + 1)] == TileType::Wall { neighbors += 1; }

                if neighbors > 4 || neighbors == 0 {
                    newtiles[idx] = TileType::Wall;
                }
                else {
                    newtiles[idx] = TileType::Floor;
                }
            }
        }

        self.map.tiles = newtiles.clone();
        self.take_snapshot();
    }
}
}

这实际上非常简单：

我们如上所述随机化地图。
我们从 0 数到 9，进行 10 次算法迭代。
对于每次迭代：
1. 我们复制地图地块，将其放入 newtiles 中。我们这样做是为了不写入我们正在计数的地块，这会产生非常奇怪的地图。
2. 我们迭代地图上的每个单元格，并计算与该地块相邻的墙壁地块数量。
3. 如果有超过 4 个或 0 个相邻的墙壁 - 那么该地块（在 newtiles 中）变成墙壁。否则，它变成地板。
4. 我们将 newtiles 复制回 map。
5. 我们拍摄快照。

这是一个非常简单的算法 - 但产生了非常漂亮的结果。这是它的实际效果：

Screenshot .

选择一个起始点

为玩家选择一个起始点比之前的章节要稍微困难一些。我们没有房间列表可以查询！相反，我们将从中间开始，然后向左移动，直到我们找到一些开放空间。这段代码非常简单：

#![allow(unused)]
fn main() {
// 找到一个起始点；从中间开始向左走，直到找到一个开放的地块
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);
}
}

放置出口 - 并剔除无法到达的区域

我们希望出口离玩家相当远。我们也不想保留玩家绝对无法到达的区域。幸运的是，找到出口的过程和找到孤立区域的过程非常相似。我们可以使用 Dijkstra 地图。如果您还没有读过，我建议您阅读 Dijkstra 地图的不可思议的力量。幸运的是，RLTK 为您实现了一个非常快速的 Dijkstra 版本，因此您不必与该算法作斗争。这是代码：

#![allow(unused)]
fn main() {
// 找到我们可以从起始点到达的所有地块
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();
}

这是一段密集的代码，它做了很多事情，让我们逐步了解它：

我们创建一个名为 map_starts 的向量，并为其提供一个单一值：玩家开始所在的地块索引。Dijkstra 地图可以有多个起点（距离为 0），因此即使只有一个选择，这也必须是一个向量。
我们要求 RLTK 为我们制作一个 Dijkstra 地图。它的尺寸与主地图匹配，使用起点，具有对地图本身的读取访问权限，并且我们将停止计数 200 步（以防失控的安全功能！）
我们将 exit_tile tuple 设置为 0 和 0.0。第一个零是出口的地块索引，第二个零是到出口的距离。
我们迭代地图地块，使用 Rust 的超棒的枚举功能。通过在范围迭代的末尾添加 .enumerate()，它将单元格索引作为元组中的第一个参数添加。然后我们解构以获得地块和索引。
如果地块是地板，
我们从 Dijkstra 地图获得到起点的距离。
如果距离是 f32 的最大值（Dijkstra 地图用于“无法到达”的标记），那么它根本不需要是地板 - 没人能到达那里。所以我们把它变成墙壁。
如果距离大于 exit_tile 元组中的距离，我们将新距离和新地块索引都存储起来。
一旦我们访问了每个地块，我们就会拍摄快照以显示移除的区域。
我们将 exit_tile 处的地块（最远的可到达的地块）设置为向下楼梯。

如果您 cargo run，您实际上现在拥有了一个相当可玩的游戏地图！只是有一个问题：地图上没有其他实体。

填充我们的洞穴：将生成系统从房间中解放出来。

如果我们感到懒惰，我们可以简单地迭代地图 - 找到开放空间并随机生成一些东西。但这真的不是很有趣。怪物成群结队地出现，留出一些“死亡空间”让您喘口气（并恢复一些生命值）更有意义。

第一步，我们将重新审视我们如何生成实体。现在，几乎所有不是玩家的东西都是通过 spawner.rs 提供的 spawn_room 函数进入世界的。到目前为止，它已经很好地为我们服务，但我们希望更加灵活；我们可能想在走廊中生成，我们可能想在不适合矩形的半开放区域中生成，等等。此外，查看 spawn_room 会发现它在一个函数中做了几件事 - 这不是最好的设计。最终目标是保持 spawn_room 接口可用 - 这样我们仍然可以使用它，但也提供更详细的选项。

我们要做的第一件事是将实际生成分离出来：

#![allow(unused)]
fn main() {
/// 在（tuple.0）的位置生成一个命名的实体（tuple.1 中的名称）
fn spawn_entity(ecs: &mut World, spawn : &(&usize, &String)) {
    let x = (*spawn.0 % MAPWIDTH) as i32;
    let y = (*spawn.0 / MAPWIDTH) as i32;

    match spawn.1.as_ref() {
        "Goblin" => goblin(ecs, x, y),
        "Orc" => orc(ecs, x, y),
        "Health Potion" => health_potion(ecs, x, y),
        "Fireball Scroll" => fireball_scroll(ecs, x, y),
        "Confusion Scroll" => confusion_scroll(ecs, x, y),
        "Magic Missile Scroll" => magic_missile_scroll(ecs, x, y),
        "Dagger" => dagger(ecs, x, y),
        "Shield" => shield(ecs, x, y),
        "Longsword" => longsword(ecs, x, y),
        "Tower Shield" => tower_shield(ecs, x, y),
        "Rations" => rations(ecs, x, y),
        "Magic Mapping Scroll" => magic_mapping_scroll(ecs, x, y),
        "Bear Trap" => bear_trap(ecs, x, y),
        _ => {}
    }
}
}

现在我们可以用以下内容替换 spawn_room 中的最后一个 for 循环：

#![allow(unused)]
fn main() {
// 实际生成怪物
for spawn in spawn_points.iter() {
    spawn_entity(ecs, &spawn);
}
}

现在，我们将用一个简化的版本替换 spawn_room，该版本调用我们的理论函数：

#![allow(unused)]
fn main() {
pub fn spawn_room(ecs: &mut World, room : &Rect, map_depth: i32) {
    let mut possible_targets : Vec<usize> = Vec::new();
    { // 借用作用域 - 保持对地图的访问分离
        let map = ecs.fetch::<Map>();
        for y in room.y1 + 1 .. room.y2 {
            for x in room.x1 + 1 .. room.x2 {
                let idx = map.xy_idx(x, y);
                if map.tiles[idx] == TileType::Floor {
                    possible_targets.push(idx);
                }
            }
        }
    }

    spawn_region(ecs, &possible_targets, map_depth);
}
}

此函数保持与先前调用相同的接口/签名 - 因此我们的旧代码仍然可以工作。它不是实际生成任何东西，而是构建一个房间中所有地块的向量（检查它们是否是地板 - 我们之前没有做过；墙壁中的怪物不再可能！）。然后它调用一个新函数 spawn_region，该函数接受类似的签名 - 但需要一个可用于生成事物的可用地块列表。这是新函数：

#![allow(unused)]
fn main() {
pub fn spawn_region(ecs: &mut World, area : &[usize], map_depth: i32) {
    let spawn_table = room_table(map_depth);
    let mut spawn_points : HashMap<usize, String> = HashMap::new();
    let mut areas : Vec<usize> = Vec::from(area);

    // 作用域以保持借用检查器满意
    {
        let mut rng = ecs.write_resource::<RandomNumberGenerator>();
        let num_spawns = i32::min(areas.len() as i32, rng.roll_dice(1, MAX_MONSTERS + 3) + (map_depth - 1) - 3);
        if num_spawns == 0 { return; }

        for _i in 0 .. num_spawns {
            let array_index = if areas.len() == 1 { 0usize } else { (rng.roll_dice(1, areas.len() as i32)-1) as usize };
            let map_idx = areas[array_index];
            spawn_points.insert(map_idx, spawn_table.roll(&mut rng));
            areas.remove(array_index);
        }
    }

    // 实际生成怪物
    for spawn in spawn_points.iter() {
        spawn_entity(ecs, &spawn);
    }
}
}

这与之前的生成代码类似，但并不完全相同（尽管结果基本上是相同的！）。我们将仔细研究它，以确保我们理解我们正在做什么：

我们获得当前地图深度的生成表。
我们设置一个名为 spawn_points 的 HashMap，列出我们已决定生成的所有内容的成对数据（地图索引和名称标签）。
我们创建一个新的 Vector 区域，从传入的切片复制而来。（切片是数组或向量的“视图”）。我们正在创建一个新的，这样我们就不会修改父区域列表。调用者可能想将该数据用于其他用途，并且避免在未经请求的情况下更改人们的数据是件好事。在没有警告的情况下更改数据称为“副作用”，通常最好避免它们（除非您实际上想要它们）。
我们创建一个新的作用域，因为 Rust 不喜欢我们使用 ECS 来获取随机数生成器，然后在稍后使用它来生成实体。作用域使 Rust 在作用域结束后立即“忘记”我们的第一次借用。
我们从 ECS 获取一个随机数生成器。
我们计算要生成的实体的数量。这与我们之前使用的随机函数相同，但我们添加了一个 i32::min 调用：我们想要可用地块数量或随机计算中的较小者。这样，我们永远不会尝试生成超过我们有空间的实体。
如果要生成的数量为零，我们退出函数（这里无事可做！）。
对于从零到生成数量的重复（减 1 - 我们没有使用包含范围）：
1. 我们从区域中选择一个 array_index。如果只有一个条目，我们使用它。否则，我们掷骰子（从 1 到条目数，减一是因为数组是基于零的）。
2. map_idx（地图地块数组中的位置）是位于数组的 array_index 索引处的值。所以我们获得它。
3. 我们将一个生成项插入 spawn_points 地图中，列出索引和生成表上的随机掷骰。
4. 我们从 areas 中删除我们刚刚使用的条目 - 这样，我们不会意外地再次选择它。请注意，我们没有检查数组是否为空：在上面的步骤 6 中，我们保证我们生成的实体不会超过我们有空间的数量，因此（至少在理论上）那个特定的错误不会发生！

测试这个的最佳方法是取消注释 random_builder 代码（并注释掉 CellularAutomataBuilder 条目），然后试用一下。它应该像以前一样正常运行。一旦您测试过它，请返回到始终生成我们正在处理的地图类型。

在我们的地图中分组放置 - 进入 Voronoi！

Voronoi 图是非常有用的数学工具。给定一组点，它构建了一个围绕每个点的区域图（这些点可以是随机的，也可能意味着某些东西；这就是数学的魅力，这取决于您！） - 没有空白空间。我们希望为我们的地图做类似的事情：将地图细分为随机区域并在这些区域内部生成。幸运的是，RLTK 提供了一种噪声来帮助实现这一点：细胞噪声。

首先，什么是噪声。在这种情况下，“噪声”不是指您在凌晨 2 点不小心从庭院扬声器中播放出来的响亮重金属音乐，同时想知道您在新房子里找到的立体声接收器是做什么的（真实故事...）；它指的是随机数据 - 就像您没有调谐到频道时旧模拟电视上的噪声一样（好吧，我在这里暴露我的年龄了）。像大多数随机事物一样，有很多方法可以使其不是真正随机的，并将其分组为有用的模式。噪声库提供了许多类型的噪声。Perlin/Simplex 噪声可以很好地近似景观。白噪声看起来像有人随机地将油漆扔到一张纸上。细胞噪声在网格上随机放置点，然后在它们周围绘制 Voronoi 图。我们对后者感兴趣。

这是一种有点复杂的方法，因此我们将逐步进行。首先，让我们向 CellularAutomataBuilder 结构添加一个结构来存储生成的区域：

#![allow(unused)]
fn main() {
pub struct CellularAutomataBuilder {
    map : Map,
    starting_position : Position,
    depth: i32,
    history: Vec<Map>,
    noise_areas : HashMap<i32, Vec<usize>>
}
}

在 new 中，我们还必须初始化它：

#![allow(unused)]
fn main() {
impl CellularAutomataBuilder {
    pub fn new(new_depth : i32) -> CellularAutomataBuilder {
        CellularAutomataBuilder{
            map : Map::new(new_depth),
            starting_position : Position{ x: 0, y : 0 },
            depth : new_depth,
            history: Vec::new(),
            noise_areas : HashMap::new()
        }
    }
    ...
}

这里的想法是我们有一个 HashMap（其他语言中的字典），以区域的 ID 号为键。该区域由地块 ID 号的 vector 组成。理想情况下，我们将生成 20-30 个不同的区域，所有区域都有空间来生成实体。

这是 build 代码的下一部分：

#![allow(unused)]
fn main() {
// 现在我们构建一个噪声地图，用于稍后生成实体
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]);
            }
        }
    }
}
}

由于这相当复杂，让我们逐步了解它：

我们从 RLTK 的 Auburns 优秀 FastNoise 库的端口创建一个新的 FastNoise 对象。
我们指定我们想要细胞噪声。在这种情况下，这与 Voronoi 噪声相同。
我们指定频率为 0.08。这个数字是通过尝试不同的值找到的！
我们指定 Manhattan 距离函数。有三种可以选择，它们给出不同的形状。曼哈顿倾向于偏爱细长的形状，我喜欢将其用于此目的。尝试所有三种，看看您喜欢哪种。
我们迭代整个地图：
1. 我们获取地块的 idx，在地图的 tiles 向量中。
2. 我们检查以确保它是地板 - 如果不是，则跳过。
3. 我们查询 FastNoise 坐标的噪声值（将它们转换为 f32 浮点数，因为该库喜欢浮点数）。我们将结果乘以 10240.0，因为默认值是非常小的数字 - 这使其达到合理的范围。
4. 我们将结果转换为整数。
5. 如果 noise_areas 地图包含我们刚刚生成的区域编号，我们将地块索引添加到向量中。
6. 如果 noise_areas 地图不包含我们刚刚生成的区域编号，我们创建一个新的地块索引向量，其中包含地图索引号。

这相当一致地生成 20 到 30 个区域，并且它们仅包含有效的地板地块。因此，最后剩下的工作是实际生成一些实体。我们更新我们的 spawn_entities 函数：

#![allow(unused)]
fn main() {
fn spawn_entities(&mut self, ecs : &mut World) {
    for area in self.noise_areas.iter() {
        spawner::spawn_region(ecs, area.1, self.depth);
    }
}
}

这非常简单：它迭代每个区域，并使用该区域的可用地图地块向量调用新的 spawn_region。

游戏现在在这些新地图上非常可玩：

Screenshot .

恢复随机性

再一次，我们应该恢复地图构建的随机性。在 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))
    }
}
}

总结

我们制作了一个非常不错的地图生成器，并修复了我们对房间的依赖。细胞自动机是一种非常灵活的算法，可以用于各种看起来自然的地图。通过对规则进行一些调整，您可以制作出各种各样的地图。

本章的源代码可以在这里找到

使用 Rust 开发肉鸽游戏教程