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

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

教育工具 趣味工具 Canvas 生成 迷宫
128
0
0
0
「迷宫」：由一系列相互连通的单元格和分隔墙壁组成的二维网格结构，通常包含一个起点和一个终点。迷宫的核心目标是让求解者找到从起点到终点的可行路径。在计算机科学中，迷宫可以被建模为图（Graph），单元格对应节点，打通的墙壁对应边。 「递归回溯算法」：一种基于深度优先搜索（DFS）策略的迷宫生成算法。该算法从随机选择的起点开始，标记为已访问，然后随机选择一个未访问的相邻单元格并打通两者之间的墙壁，移动到新单元格后递归执行相同操作。当所有相邻单元格均已被访问时执行回溯。该算法生成的迷宫通常具有较长的走廊和较少的分支。 「Prim算法」：一种基于最小生成树（MST）思想的迷宫生成算法。维护一个「前沿列表」存储所有与已访问区域相邻的未访问单元格，每步从列表中随机选取一个单元格并打通墙壁。该算法生成的迷宫分支密集、结构均匀，死胡同分布更加分散。 「Kruskal算法」：另一种基于最小生成树思想的生成算法，通过随机打乱所有墙壁的顺序并逐一检查是否可以打通来构建迷宫。使用并查集（Union-Find）数据结构来管理连通分量，确保不形成回路。与 Prim 算法相比，Kruskal 算法生成的迷宫随机性更强，连通性更均匀。 「完美迷宫」：指迷宫中任意两个单元格之间恰好只有一条通路的迷宫结构，不存在回路、封闭区域或孤立单元格。在图论中，完美迷宫等价于网格图的一棵生成树。本工具默认生成的迷宫均为完美迷宫。 「BFS广度优先搜索」：一种系统性的图遍历算法，从起点出发逐层向外扩展，优先访问距离起点最近的未访问节点。用于迷宫求解时，BFS 保证找到从起点到终点的最短路径（即经过最少单元格数的路径），但需要较多内存来维护队列和访问记录。 「DFS深度优先搜索」：一种图遍历算法，沿当前路径尽可能深入探索，直到到达终点或无法继续时回溯。用于迷宫求解时，DFS 找到的路径不一定是最短的，但内存消耗较小，搜索过程更具随机性和观赏性。 「单元格」：迷宫网格中最小的基本组成单位，每个单元格占据网格中的一个位置。单元格有四个方向的墙壁（上、下、左、右），可以被选择性地打通以与相邻单元格建立连通关系。在算法中，每个单元格通常用坐标 (行, 列) 来标识。 「墙壁」：分隔两个相邻单元格之间的边界结构。打通墙壁意味着将两个相邻单元格连通，使其可以相互到达。迷宫生成的过程本质上就是逐步打通墙壁的过程，而迷宫求解的过程则是寻找一条由已打通墙壁构成的单元格序列。 「走廊」：由多个连续打通墙壁的单元格线性排列组成的通道。走廊是迷宫中可供行走的主要路径类型，走廊的长度和分布直接影响迷宫的视觉风格和求解难度。递归回溯算法倾向于生成较长的走廊。 「死胡同」：只有一个方向可以通行的单元格结构，走进去后只能原路返回。死胡同是迷宫设计中的重要元素，增加了迷宫的复杂度和探索的趣味性。Prim 算法生成的迷宫通常包含更多的死胡同。 「前沿列表」：Prim 算法中维护的核心数据结构，动态存储所有与已访问区域相邻但自身尚未被访问的单元格。算法每一步从前沿列表中随机选取一个单元格进行处理，并在处理后更新列表内容。前沿列表的管理效率直接影响算法的执行性能。 「并查集」：Kruskal 算法中使用的关键数据结构（Union-Find），用于高效地管理节点之间的连通关系。它支持两个核心操作：「查找」（Find）用于确定元素所属的连通分量，「合并」（Union）用于将两个连通分量合并为一个。通过路径压缩和按秩合并等优化技术，操作的时间复杂度接近常数级别。
🔧 相关工具