无需登录 数据私有 本地保存

迷宫生成器 - 算法随机迷宫Canvas绘制

30
0
0
0
常见问题与知识点

迷宫生成算法是一种程序化创建迷宫的方法。它从一个封闭的网格开始（所有墙壁都存在），然后按照特定规则逐步移除墙壁，最终形成一个从起点到终点有且仅有一条路径的"完美迷宫"（任意两个单元格之间恰好只有一条通路）。常见算法包括递归回溯（DFS）、Prim算法和Kruskal算法，它们生成的迷宫在分支密度、曲折程度和视觉风格上各有特色。

递归回溯算法（Recursive Backtracking）使用深度优先搜索策略。它从一个单元格开始，随机选择一个未访问的相邻单元格，移除它们之间的墙壁，然后移动到新单元格继续探索。当遇到死胡同（所有邻居都已访问）时，算法沿着之前的路径回溯，直到找到有未访问邻居的单元格。这种方法生成的迷宫路径较为曲折，长走廊较少，分支丰富。它本质上是对图进行深度优先遍历的随机化版本。

Prim算法从已访问区域向外"生长"，每次从边界中随机选择一个单元格加入迷宫，生成的迷宫分支均匀、短死胡同较多。它维护一个"前沿"集合，类似于从种子点不断扩展。

Kruskal算法随机遍历所有可能的墙壁，使用并查集（Union-Find）数据结构确保移除墙壁不会形成环路。它生成的迷宫分支分布非常均匀，视觉上更加"公正"，没有明显的偏向性。两种算法都保证生成完美迷宫。

本工具使用广度优先搜索（BFS）算法求解迷宫。从起点（左上角）开始，逐层探索所有可到达的单元格，记录每个单元格的前驱节点，直到找到终点（右下角）。由于生成的迷宫是完美迷宫（任意两点间只有一条路径），BFS找到的路径就是唯一路径，也是最短路径。求解结果以金黄色高亮显示在迷宫上。

完美迷宫（Perfect Maze）是指任意两个单元格之间恰好只有一条通路的迷宫。这意味着迷宫中没有环路，也没有无法到达的区域。本工具生成的所有迷宫都是完美迷宫。完美迷宫的一个有趣特性是：从起点到终点的路径是唯一的，因此求解算法找到的就是唯一正确路径。
🔧 相关工具