随机迷宫生成：深度优先回溯法
副标题 / 摘要 随机迷宫生成常用深度优先回溯法。本文解释思路并提供可运行实现。 目标读者 学习图算法的开发者 想做程序化生成的工程师 算法入门学习者 背景 / 动机 迷宫生成是图遍历与随机化的经典结合。 它能帮助理解 DFS、回溯与边界处理。 核心概念 网格图：迷宫格点和通道 DFS 回溯：随机探索与回退 墙与通路：用字符表示结构 实践指南 / 步骤 初始化全墙网格 从起点开始 DFS 随机选择未访问邻居并打通墙 回溯直到全部访问完成 可运行示例 import random def maze(w, h): grid = [["#"] * (2 * w + 1) for _ in range(2 * h + 1)] visited = [[False] * w for _ in range(h)] def carve(x, y): visited[y][x] = True dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)] random.shuffle(dirs) for dx, dy in dirs: nx, ny = x + dx, y + dy if 0 <= nx < w and 0 <= ny < h and not visited[ny][nx]: grid[y * 2 + 1 + dy][x * 2 + 1 + dx] = " " grid[y * 2 + 1][x * 2 + 1] = " " grid[ny * 2 + 1][nx * 2 + 1] = " " carve(nx, ny) carve(0, 0) return "\n".join("".join(row) for row in grid) if __name__ == "__main__": print(maze(6, 4)) 解释与原理 DFS 回溯保证每个格子被访问一次，随机方向带来多样性。 打通墙壁即可形成迷宫通路。 ...