使用 Rust 生成迷宫

在 Rust 中生成迷宫有多种算法可以选择，下面我将介绍几种常见的方法并提供实现示例。

1. 递归回溯算法 (深度优先搜索)

这是最简单直观的迷宫生成算法之一。

use rand::Rng;
use std::fmt;

#[derive(Debug, Clone, Copy, PartialEq)]
enum Cell {
    Wall,
    Path,
}

struct Maze {
    width: usize,
    height: usize,
    cells: Vec<Vec<Cell>>,
}

impl Maze {
    fn new(width: usize, height: usize) -> Self {
        // 确保宽高都是奇数以便有完整的墙壁
        let width = if width % 2 == 0 { width + 1 } else { width };
        let height = if height % 2 == 0 { height + 1 } else { height };
        
        // 初始化所有单元格为墙壁
        let cells = vec![vec![Cell::Wall; height]; width];
        
        Maze { width, height, cells }
    }
    
    fn generate(&mut self, start_x: usize, start_y: usize) {
        let mut stack = vec![(start_x, start_y)];
        self.cells[start_x][start_y] = Cell::Path;
        
        let mut rng = rand::thread_rng();
        
        while let Some((x, y)) = stack.pop() {
            // 获取未访问的邻居
            let mut neighbors = Vec::new();
            
            // 检查四个方向
            let directions = [(2, 0), (-2, 0), (0, 2), (0, -2)];
            for &(dx, dy) in directions.iter() {
                let nx = x as isize + dx;
                let ny = y as isize + dy;
                
                if nx > 0 && nx < self.width as isize - 1 && 
                   ny > 0 && ny < self.height as isize - 1 {
                    let nx = nx as usize;
                    let ny = ny as usize;
                    
                    if self.cells[nx][ny] == Cell::Wall {
                        neighbors.push((nx, ny));
                    }
                }
            }
            
            if !neighbors.is_empty() {
                // 随机选择一个邻居
                let idx = rng.gen_range(0..neighbors.len());
                let (nx, ny) = neighbors[idx];
                
                // 打通墙壁
                self.cells[(x + nx) / 2][(y + ny) / 2] = Cell::Path;
                self.cells[nx][ny] = Cell::Path;
                
                stack.push((x, y));
                stack.push((nx, ny));
            }
        }
    }
}

impl fmt::Display for Maze {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        for y in 0..self.height {
            for x in 0..self.width {
                let c = match self.cells[x][y] {
                    Cell::Wall => '█',
                    Cell::Path => ' ',
                };
                write!(f, "{}", c)?;
            }
            writeln!(f)?;
        }
        Ok(())
    }
}

fn main() {
    let mut maze = Maze::new(21, 21);
    maze.generate(1, 1);
    println!("{}", maze);
}

2. Prim 算法

Prim 算法也可以用于迷宫生成，它会产生不同风格的迷宫。

use rand::Rng;
use std::collections::HashSet;

impl Maze {
    fn generate_prim(&mut self, start_x: usize, start_y: usize) {
        let mut frontier = HashSet::new();
        let mut in_maze = HashSet::new();
        
        self.cells[start_x][start_y] = Cell::Path;
        in_maze.insert((start_x, start_y));
        
        // 添加初始边界
        self.add_frontier(start_x, start_y, &mut frontier);
        
        let mut rng = rand::thread_rng();
        
        while !frontier.is_empty() {
            // 随机选择一个边界单元格
            let idx = rng.gen_range(0..frontier.len());
            let current = *frontier.iter().nth(idx).unwrap();
            frontier.remove(&current);
            
            let (x, y) = current;
            
            // 找到一个已连接的邻居
            let neighbors = [
                (x.wrapping_sub(2), y),
                (x + 2, y),
                (x, y.wrapping_sub(2)),
                (x, y + 2),
            ];
            
            if let Some((nx, ny)) = neighbors.iter().find(|&(nx, ny)| {
                *nx < self.width && *ny < self.height && in_maze.contains(&(*nx, *ny))
            }) {
                // 打通墙壁
                self.cells[(x + nx) / 2][(y + ny) / 2] = Cell::Path;
                self.cells[x][y] = Cell::Path;
                in_maze.insert((x, y));
                
                // 添加新的边界
                self.add_frontier(x, y, &mut frontier);
            }
        }
    }
    
    fn add_frontier(&self, x: usize, y: usize, frontier: &mut HashSet<(usize, usize)>) {
        let candidates = [
            (x.wrapping_sub(2), y),
            (x + 2, y),
            (x, y.wrapping_sub(2)),
            (x, y + 2),
        ];
        
        for (nx, ny) in candidates {
            if nx < self.width && ny < self.height && self.cells[nx][ny] == Cell::Wall {
                frontier.insert((nx, ny));
            }
        }
    }
}

3. Kruskal 算法

Kruskal 算法通常用于生成最小生成树，但也可以用于迷宫生成。

use rand::seq::SliceRandom;

struct UnionFind {
    parent: Vec<usize>,
    rank: Vec<usize>,
}

impl UnionFind {
    fn new(size: usize) -> Self {
        UnionFind {
            parent: (0..size).collect(),
            rank: vec![0; size],
        }
    }
    
    fn find(&mut self, x: usize) -> usize {
        if self.parent[x] != x {
            self.parent[x] = self.find(self.parent[x]);
        }
        self.parent[x]
    }
    
    fn union(&mut self, x: usize, y: usize) {
        let x_root = self.find(x);
        let y_root = self.find(y);
        
        if x_root == y_root {
            return;
        }
        
        if self.rank[x_root] < self.rank[y_root] {
            self.parent[x_root] = y_root;
        } else if self.rank[x_root] > self.rank[y_root] {
            self.parent[y_root] = x_root;
        } else {
            self.parent[y_root] = x_root;
            self.rank[x_root] += 1;
        }
    }
}

impl Maze {
    fn generate_kruskal(&mut self) {
        let width = (self.width + 1) / 2;
        let height = (self.height + 1) / 2;
        let mut uf = UnionFind::new(width * height);
        
        // 收集所有墙壁
        let mut walls = Vec::new();
        
        for x in 0..width {
            for y in 0..height {
                let idx = y * width + x;
                
                // 右边的墙
                if x < width - 1 {
                    walls.push((idx, idx + 1, x * 2 + 1, y * 2));
                }
                
                // 下边的墙
                if y < height - 1 {
                    walls.push((idx, idx + width, x * 2, y * 2 + 1));
                }
            }
        }
        
        // 随机打乱墙壁顺序
        let mut rng = rand::thread_rng();
        walls.shuffle(&mut rng);
        
        // 初始化所有单元格为路径（中间会有墙）
        for x in 0..self.width {
            for y in 0..self.height {
                if x % 2 == 1 || y % 2 == 1 {
                    self.cells[x][y] = Cell::Wall;
                } else {
                    self.cells[x][y] = Cell::Path;
                }
            }
        }
        
        // 处理墙壁
        for (a, b, wx, wy) in walls {
            if uf.find(a) != uf.find(b) {
                uf.union(a, b);
                self.cells[wx][wy] = Cell::Path;
            }
        }
    }
}

使用示例

fn main() {
    // 递归回溯算法示例
    let mut maze = Maze::new(21, 21);
    maze.generate(1, 1);
    println!("递归回溯算法生成的迷宫:");
    println!("{}", maze);
    
    // Prim 算法示例
    let mut maze = Maze::new(21, 21);
    maze.generate_prim(1, 1);
    println!("\nPrim 算法生成的迷宫:");
    println!("{}", maze);
    
    // Kruskal 算法示例
    let mut maze = Maze::new(21, 21);
    maze.generate_kruskal();
    println!("\nKruskal 算法生成的迷宫:");
    println!("{}", maze);
}

依赖

在 Cargo.toml 中添加：

[dependencies]
rand = "0.8"

扩展功能

1. 添加入口和出口：可以在迷宫的边缘随机选择两个点作为入口和出口。
2. 可视化：可以使用 piston_window 或 ggez 等库创建图形界面。
3. 求解算法：实现 A* 或 Dijkstra 算法来求解生成的迷宫。
4. 3D 迷宫：扩展为三维迷宫生成。

这些算法生成的迷宫都是完美迷宫（即任意两点之间有且只有一条路径），但具有不同的特征。递归回溯生成的迷宫通常有长而直的通道，Prim 算法生成的迷宫有更多分支，而 Kruskal 算法生成的迷宫则有更多短通道和死胡同。