如何产生与一个以上的成功完全路径迷宫？ [英] How to generate a maze with more than one success full path?

问题描述

哪个算法可以被用来产生与一个以上的成功完全路径迷宫，如果算法被修改版本的一些公知的算法然后解释或添加链接。

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

我使用的二维数组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. 细分迷宫分为三组：启动的（intially抱着刚开始小区）的目标的（最初只持有目标细胞），而未被发现（所有其他）。
2. 在随机细胞间除去墙的启动的或目标的设置和单元格的未被发现的设置，然后将新发现的细胞相应的设置。
3. 在重复，直到每个单元要么是在启动的或目标的设置。
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. 通过将所有的细胞都更接近于一开始进入的启动的设置，所有细胞都更接近球门进的目标的设置。
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屋！