如何产生一条不止一条成功道路的迷宫? [英] How to generate a maze with more than one successful path?

问题描述

哪种算法可用于生成具有多个成功路径的迷宫，如果该算法是某些知名算法的修改版本，则说明或添加链接.

Which algorithm can be used to generate a maze with more than one successful path and if algorithm is modified version of some well known algorithm then explain or add a link .

我正在使用2D阵列A来存储迷宫的配置.

I am using 2D array A to store configuration of maze .

假设迷宫的大小为n * n，那么从A [0] [0]到A [n-1] [n-1]应该有多个路径.

Assume if the size of maze is n * n then more than one path should be there from A[0][0] to A[n-1][n-1] .

推荐答案

此算法应该能够生成从起点到目标具有独特的无环路径的迷宫:

This algorithms should be able to generate mazes with distinct loop-free paths from start to goal:

从一个空的迷宫(或一块坚硬的岩石)开始，只有起点和终点……

Starting with an empty maze (or a solid block of rock), with just the start and the goal...

1. 将迷宫细分为三组:开始(最初仅保留起始单元格)，目标(最初仅保留目标单元格)和未发现(其余所有).
2. 随机删除 start 或 goal 集中的单元格与 undiscovered 集中的单元格之间的壁，然后将新发现的单元格移至各自的集合.
3. 重复直到每个单元格位于 start 或 goal 集中.
4. 根据需要，从两个区域之间移除尽可能多的墙.

1. Subdivide the maze into three sets: Start (intially holding just the start cell), goal (initially holding just the goal cell), and undiscovered (all the rest).
2. Randomly remove walls between cells in the start or the goal set and cells in the undiscovered set, and move the newly discovered cell to the respective set.
3. Repeat until each cell is either in the start or the goal set.
4. Remove as many walls between the two regions as you want paths from the start to the goal.

或者，如果您已经有一个迷宫，且迷宫的路径是从单一路径开始的，请使用以下变体:

Alternatively, if you already have a maze with a single path form start to goal, use this variant:

1. 从起点和目标进行广度优先搜索，并为迷宫中的每个单元格记录单元距起点和目标的步数.
2. 通过将所有靠近起点的单元格放入 start 集中并将所有接近目标的单元格放入 goal 集中来细分迷宫.
li>
3. 在两个区域之间移开一堵墙，以增加一条从起点到目标的路径.

1. Do a Breadth First Search from both the start and the goal, and for each cell in the maze record the number of steps that cell is away from both the start and the goal.
2. Subdivide the maze by putting all cells that are closer to the start into the start set and all cells that are closer to the goal into the goal set.
3. Remove a wall between the two regions to add an additional path from start to goal.

生成的路径可能具有相同(甚至可能是实质性的)部分，但是从开始到目标，它们应该是唯一的无循环路径.这是第一种情况的说明:

The generated paths might have (maybe even substantial) parts in common, but they should be unique loop-free paths from start to goal. Here's an illustration of the first case:

这篇关于如何产生一条不止一条成功道路的迷宫?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！