扩散限制聚集

关于本教程

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

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

扩散限制聚集 (Diffusion-Limited Aggregation, DLA) 是对受限的醉汉漫步 (drunken walk) 的一种更花哨的称呼。它可以生成看起来更自然的地图，更侧重于中心区域和从中延伸出来的“臂状”结构。通过一些技巧，它可以看起来非常外星化 - 或者非常真实。请参阅 Rogue Basin 上关于扩散限制聚集的优秀文章。

脚手架

我们将创建一个新文件 map_builders/dla.rs，并将之前项目中的脚手架代码放入其中。我们将构建器命名为 DLABuilder。我们还将保留 Voronoi 生成代码，它在此应用中可以正常工作。我们将直接进入正题，而不是重复之前章节中的脚手架代码块。如果您遇到困难，可以查看本章的源代码这里。

算法调整旋钮 (Algorithm Tuning Knobs)

在上一章中，我们介绍了向构建器添加参数的想法。我们将再次为 DLA 执行相同的操作 - 有一些算法变体可以产生不同的地图样式。我们将引入以下枚举：

#![allow(unused)]
fn main() {
#[derive(PartialEq, Copy, Clone)]
pub enum DLAAlgorithm { WalkInwards, WalkOutwards, CentralAttractor }

#[derive(PartialEq, Copy, Clone)]
pub enum DLASymmetry { None, Horizontal, Vertical, Both }
}

我们的构建器将再包含一个，笔刷大小 (brush size)：

#![allow(unused)]
fn main() {
pub struct DLABuilder {
    map : Map,
    starting_position : Position,
    depth: i32,
    history: Vec<Map>,
    noise_areas : HashMap<i32, Vec<usize>>,
    algorithm : DLAAlgorithm,
    brush_size: i32,
    symmetry: DLASymmetry,
    floor_percent: f32
}
}

如果您已经阅读过其他章节，那么现在这应该是不言自明的：

我们支持三种算法，WalkInwards、WalkOutwards、CentralAttractor。我们将在稍后详细介绍这些算法。
我们添加了 symmetry，它可以是 None、Horizontal、Vertical 或 Both。对称性可以用于使用此算法生成一些精美的结果，我们将在本文后面介绍。
我们还添加了 brush_size，它指定我们一次在地图上“绘制”多少个地板瓦片 (floor tiles)。我们将在本章末尾介绍这一点。
我们包含了来自醉汉漫步章节的 floor_percent。

我们的 new 函数需要包含这些参数：

#![allow(unused)]
fn main() {
pub fn new(new_depth : i32) -> DLABuilder {
    DLABuilder{
        map : Map::new(new_depth),
        starting_position : Position{ x: 0, y : 0 },
        depth : new_depth,
        history: Vec::new(),
        noise_areas : HashMap::new(),
        algorithm: DLAAlgorithm::WalkInwards,
        brush_size: 1,
        symmetry: DLASymmetry::None,
        floor_percent: 0.25
    }
}
}

一旦我们掌握了算法及其变体，我们将制作一些类型构造器 (type constructors)！

向内行走 (Walking Inwards)

扩散限制聚集 (Diffusion-Limited Aggregation) 最基本的形式如下：

在您的中心起始点周围挖掘一个“种子 (seed)”区域。
当地板瓦片 (floor tiles) 的数量少于您期望的总数时：
1. 为您的挖掘者随机选择一个起始点。
2. 使用“醉汉漫步 (drunkard's walk)”算法随机移动。
3. 如果挖掘者撞击到地板瓦片 (floor tile)，则他们之前所在的瓦片也会变成地板，并且挖掘者停止。

非常简单，并且不太难实现：

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

    // 雕刻一个起始种子 (Carve a starting seed)
    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.take_snapshot();
    self.map.tiles[start_idx] = TileType::Floor;
    self.map.tiles[start_idx-1] = TileType::Floor;
    self.map.tiles[start_idx+1] = TileType::Floor;
    self.map.tiles[start_idx-self.map.width as usize] = TileType::Floor;
    self.map.tiles[start_idx+self.map.width as usize] = TileType::Floor;

    // 随机行走者 (Random walker)
    let total_tiles = self.map.width * self.map.height;
    let desired_floor_tiles = (self.floor_percent * total_tiles as f32) as usize;
    let mut floor_tile_count = self.map.tiles.iter().filter(|a| **a == TileType::Floor).count();
    while floor_tile_count  < desired_floor_tiles {

        match self.algorithm {
            DLAAlgorithm::WalkInwards => {
                let mut digger_x = rng.roll_dice(1, self.map.width - 3) + 1;
                let mut digger_y = rng.roll_dice(1, self.map.height - 3) + 1;
                let mut prev_x = digger_x;
                let mut prev_y = digger_y;
                let mut digger_idx = self.map.xy_idx(digger_x, digger_y);
                while self.map.tiles[digger_idx] == TileType::Wall {
                    prev_x = digger_x;
                    prev_y = digger_y;
                    let stagger_direction = rng.roll_dice(1, 4);
                    match stagger_direction {
                        1 => { if digger_x > 2 { digger_x -= 1; } }
                        2 => { if digger_x < self.map.width-2 { digger_x += 1; } }
                        3 => { if digger_y > 2 { digger_y -=1; } }
                        _ => { if digger_y < self.map.height-2 { digger_y += 1; } }
                    }
                    digger_idx = self.map.xy_idx(digger_x, digger_y);
                }
                self.paint(prev_x, prev_y);
            }
            _ => {}
            ...
}

这里唯一的新内容是对 paint 的调用。我们稍后将对其进行扩展（以处理笔刷大小 (brush sizes)），但这是一个临时实现：

#![allow(unused)]
fn main() {
fn paint(&mut self, x: i32, y: i32) {
    let digger_idx = self.map.xy_idx(x, y);
    self.map.tiles[digger_idx] = TileType::Floor;
}
}

如果您 cargo run 运行此代码，您将获得一个非常酷的地牢：

Screenshot .

向外行走 (Walking outwards)

此算法的第二个变体颠倒了部分过程：

在您的中心起始点周围挖掘一个“种子 (seed)”区域。
当地板瓦片 (floor tiles) 的数量少于您期望的总数时：
1. 将挖掘者设置为中心起始位置。
2. 使用“醉汉漫步 (drunkard's walk)”算法随机移动。
3. 如果挖掘者撞击到墙壁瓦片 (wall tile)，则该瓦片变为地板 - 并且挖掘者停止。

因此，我们勇敢的挖掘者不是向内行进，而是向外行进。实现这一点非常简单，并且可以添加到 build 中算法的 match 序列中：

#![allow(unused)]
fn main() {
...
DLAAlgorithm::WalkOutwards => {
    let mut digger_x = self.starting_position.x;
    let mut digger_y = self.starting_position.y;
    let mut digger_idx = self.map.xy_idx(digger_x, digger_y);
    while self.map.tiles[digger_idx] == TileType::Floor {
        let stagger_direction = rng.roll_dice(1, 4);
        match stagger_direction {
            1 => { if digger_x > 2 { digger_x -= 1; } }
            2 => { if digger_x < self.map.width-2 { digger_x += 1; } }
            3 => { if digger_y > 2 { digger_y -=1; } }
            _ => { if digger_y < self.map.height-2 { digger_y += 1; } }
        }
        digger_idx = self.map.xy_idx(digger_x, digger_y);
    }
    self.paint(digger_x, digger_y);
}
_ => {}
}

这段代码中没有任何新概念，如果您理解了醉汉漫步 (Drunkard's Walk) - 它应该是相当不言自明的。如果您调整构造器以使用它，并调用 cargo run 运行它，它看起来会很不错：

Screenshot .

中心吸引子 (Central Attractor)

此变体再次非常相似，但略有不同。您的粒子不是随机移动，而是从随机点向中心路径移动：

在您的中心起始点周围挖掘一个“种子 (seed)”区域。
当地板瓦片 (floor tiles) 的数量少于您期望的总数时：
1. 为您的挖掘者随机选择一个起始点。
2. 绘制一条到地图中心的线，并保留它。
3. 遍历该线。如果挖掘者撞击到地板瓦片 (floor tile)，则他们之前所在的瓦片也会变成地板，并且挖掘者停止。

同样，这相对容易实现：

#![allow(unused)]
fn main() {
...
DLAAlgorithm::CentralAttractor => {
    let mut digger_x = rng.roll_dice(1, self.map.width - 3) + 1;
    let mut digger_y = rng.roll_dice(1, self.map.height - 3) + 1;
    let mut prev_x = digger_x;
    let mut prev_y = digger_y;
    let mut digger_idx = self.map.xy_idx(digger_x, digger_y);

    let mut path = rltk::line2d(
        rltk::LineAlg::Bresenham,
        rltk::Point::new( digger_x, digger_y ),
        rltk::Point::new( self.starting_position.x, self.starting_position.y )
    );

    while self.map.tiles[digger_idx] == TileType::Wall && !path.is_empty() {
        prev_x = digger_x;
        prev_y = digger_y;
        digger_x = path[0].x;
        digger_y = path[0].y;
        path.remove(0);
        digger_idx = self.map.xy_idx(digger_x, digger_y);
    }
    self.paint(prev_x, prev_y);
}
}

如果您调整构造器以使用此算法，并 cargo run 运行该项目，您将获得一个更集中于中心点的地图：

Screenshot .

实现对称性 (Implementing Symmetry)

Tyger Tyger, burning bright,
In the forests of the night;
What immortal hand or eye,
Could frame thy fearful symmetry?

(威廉·布莱克，《老虎》) (William Blake, The Tyger)

对称性可以将随机地图转变为看起来像是设计出来的东西 - 但非常外星化。它通常看起来很像昆虫或让人想起《太空侵略者 (Space Invaders)》的敌人。这可以制作一些看起来很有趣的关卡！

让我们修改 paint 函数以处理对称性：

#![allow(unused)]
fn main() {
fn paint(&mut self, x: i32, y:i32) {
    match self.symmetry {
        DLASymmetry::None => self.apply_paint(x, y),
        DLASymmetry::Horizontal => {
            let center_x = self.map.width / 2;
            if x == center_x {
                self.apply_paint(x, y);
            } else {
                let dist_x = i32::abs(center_x - x);
                self.apply_paint(center_x + dist_x, y);
                self.apply_paint(center_x - dist_x, y);
            }
        }
        DLASymmetry::Vertical => {
            let center_y = self.map.height / 2;
            if y == center_y {
                self.apply_paint(x, y);
            } else {
                let dist_y = i32::abs(center_y - y);
                self.apply_paint(x, center_y + dist_y);
                self.apply_paint(x, center_y - dist_y);
            }
        }
        DLASymmetry::Both => {
            let center_x = self.map.width / 2;
            let center_y = self.map.height / 2;
            if x == center_x && y == center_y {
                self.apply_paint(x, y);
            } else {
                let dist_x = i32::abs(center_x - x);
                self.apply_paint(center_x + dist_x, y);
                self.apply_paint(center_x - dist_x, y);
                let dist_y = i32::abs(center_y - y);
                self.apply_paint(x, center_y + dist_y);
                self.apply_paint(x, center_y - dist_y);
            }
        }
    }
}

为了清晰起见，这个函数比实际需要的要长。这是它的工作原理：

我们 match 当前的对称性设置。
如果是 None，我们只需使用目标瓦片调用 apply_paint。
如果是 Horizontal：
1. 我们检查是否在瓦片上 - 如果是，则只应用一次绘制。
2. 否则，获取到中心的水平距离。
3. 在 center_x - distance 和 center_x + distance 处绘制，以在 x 轴上对称绘制。
如果是 Vertical：
1. 我们检查是否在瓦片上 - 如果是，则只应用一次绘制（这有助于处理奇数个瓦片，从而减少舍入问题）。
2. 否则，获取到中心的垂直距离。
3. 在 center_y - distance 和 center_y + distance 处绘制。
如果是 Both - 则执行两个步骤。

您会注意到我们正在调用 apply_paint 而不是实际绘制。这是因为我们还实现了 brush_size：

#![allow(unused)]
fn main() {
fn apply_paint(&mut self, x: i32, y: i32) {
    match self.brush_size {
        1 => {
            let digger_idx = self.map.xy_idx(x, y);
            self.map.tiles[digger_idx] = TileType::Floor;
        }

        _ => {
            let half_brush_size = self.brush_size / 2;
            for brush_y in y-half_brush_size .. y+half_brush_size {
                for brush_x in x-half_brush_size .. x+half_brush_size {
                    if brush_x > 1 && brush_x < self.map.width-1 && brush_y > 1 && brush_y < self.map.height-1 {
                        let idx = self.map.xy_idx(brush_x, brush_y);
                        self.map.tiles[idx] = TileType::Floor;
                    }
                }
            }
        }
    }
}
}

这很简单：

如果笔刷大小 (brush size) 为 1，我们只需绘制一个地板瓦片 (floor tile)。
否则，我们循环遍历笔刷大小 (brush size) - 并进行绘制，执行边界检查以确保我们没有在地图外绘制。

在您的构造器中，使用 CentralAttractor 算法 - 并使用 Horizontal 启用对称性。如果您现在 cargo run 运行，您将获得一张与脾气暴躁的昆虫非常相似的地图：

Screenshot .

玩转笔刷大小 (Playing with Brush Sizes)

使用更大的笔刷 (brush) 可确保您不会获得太多 1x1 区域（这些区域可能难以导航），并使地图看起来更具规划性。既然我们已经实现了笔刷大小 (brush size)，请像这样修改您的构造器：

#![allow(unused)]
fn main() {
pub fn new(new_depth : i32) -> DLABuilder {
    DLABuilder{
        map : Map::new(new_depth),
        starting_position : Position{ x: 0, y : 0 },
        depth : new_depth,
        history: Vec::new(),
        noise_areas : HashMap::new(),
        algorithm: DLAAlgorithm::WalkInwards,
        brush_size: 2,
        symmetry: DLASymmetry::None,
        floor_percent: 0.25
    }
}
}

通过这个简单的更改，我们的地图看起来更加开阔：

Screenshot .

提供一些构造器 (Providing a few constructors)

与其使用算法细节污染 random_builder 函数，不如为我们在本章中使用的每个主要算法制作构造器 (constructors)：

#![allow(unused)]
fn main() {
pub fn walk_inwards(new_depth : i32) -> DLABuilder {
    DLABuilder{
        map : Map::new(new_depth),
        starting_position : Position{ x: 0, y : 0 },
        depth : new_depth,
        history: Vec::new(),
        noise_areas : HashMap::new(),
        algorithm: DLAAlgorithm::WalkInwards,
        brush_size: 1,
        symmetry: DLASymmetry::None,
        floor_percent: 0.25
    }
}

pub fn walk_outwards(new_depth : i32) -> DLABuilder {
    DLABuilder{
        map : Map::new(new_depth),
        starting_position : Position{ x: 0, y : 0 },
        depth : new_depth,
        history: Vec::new(),
        noise_areas : HashMap::new(),
        algorithm: DLAAlgorithm::WalkOutwards,
        brush_size: 2,
        symmetry: DLASymmetry::None,
        floor_percent: 0.25
    }
}

pub fn central_attractor(new_depth : i32) -> DLABuilder {
    DLABuilder{
        map : Map::new(new_depth),
        starting_position : Position{ x: 0, y : 0 },
        depth : new_depth,
        history: Vec::new(),
        noise_areas : HashMap::new(),
        algorithm: DLAAlgorithm::CentralAttractor,
        brush_size: 2,
        symmetry: DLASymmetry::None,
        floor_percent: 0.25
    }
}

pub fn insectoid(new_depth : i32) -> DLABuilder {
    DLABuilder{
        map : Map::new(new_depth),
        starting_position : Position{ x: 0, y : 0 },
        depth : new_depth,
        history: Vec::new(),
        noise_areas : HashMap::new(),
        algorithm: DLAAlgorithm::CentralAttractor,
        brush_size: 2,
        symmetry: DLASymmetry::Horizontal,
        floor_percent: 0.25
    }
}
}

再次随机化地图构建器 (Randomizing the map builder, once again)

现在我们可以修改 map_builders/mod.rs 中的 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, 12);
    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)),
        8 => Box::new(DLABuilder::walk_inwards(new_depth)),
        9 => Box::new(DLABuilder::walk_outwards(new_depth)),
        10 => Box::new(DLABuilder::central_attractor(new_depth)),
        11 => Box::new(DLABuilder::insectoid(new_depth)),
        _ => Box::new(SimpleMapBuilder::new(new_depth))
    }
}
}

总结 (Wrap-up)

本章介绍了另一种非常灵活的地图构建器 (map builder)，供您使用。非常适合制作感觉像是从岩石中雕刻出来的地图（或从森林中砍伐、从小行星中开采等），这是为您的游戏引入多样性的另一种绝佳方式。

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

使用 Rust 开发肉鸽游戏教程

扩散限制聚集

脚手架

算法调整旋钮 (Algorithm Tuning Knobs)

向内行走 (Walking Inwards)

向外行走 (Walking outwards)

中心吸引子 (Central Attractor)

实现对称性 (Implementing Symmetry)

玩转笔刷大小 (Playing with Brush Sizes)

提供一些构造器 (Providing a few constructors)

再次随机化地图构建器 (Randomizing the map builder, once again)

总结 (Wrap-up)

在您的浏览器中使用 WebAssembly 运行本章的示例（需要 WebGL2）