这是一个创建于 1853 天前的主题，其中的信息可能已经有所发展或是发生改变。
可爱的大家，晚上好，
想请教各位一个生成迷宫的思路，不知道「无限」的描述是否到位，英文单词是「 infinite 」，希望能考虑到例外和稀奇古怪的状况，因此我了解到的下面生成迷宫的思路
"""
1.将迷宫地图分成多个房间，每个房间都有四面墙。
2.让“人”从地图任意一点 A 出发，开始在迷宫里游荡。从 A 房间的 1/2/3/4 个方向中的任选一个方向前进。在从 A 房间走到 B 房间的过程中，推倒 A/B 房间之间的墙。
3.如果方向 x 对面的房间已经走过，则选择其他方向。如果所有方向的房间都已经走过，则退回上一个房间看是否还有可选道路。
4.走到真正无路可走时，说明已经走过了所有房间，迷宫也生成好了。
"""
不过可能太过简单？有没有大神指导一二，简述即可，灰常感谢
想请教各位一个生成迷宫的思路，不知道「无限」的描述是否到位，英文单词是「 infinite 」，希望能考虑到例外和稀奇古怪的状况，因此我了解到的下面生成迷宫的思路
"""
1.将迷宫地图分成多个房间，每个房间都有四面墙。
2.让“人”从地图任意一点 A 出发，开始在迷宫里游荡。从 A 房间的 1/2/3/4 个方向中的任选一个方向前进。在从 A 房间走到 B 房间的过程中，推倒 A/B 房间之间的墙。
3.如果方向 x 对面的房间已经走过，则选择其他方向。如果所有方向的房间都已经走过，则退回上一个房间看是否还有可选道路。
4.走到真正无路可走时，说明已经走过了所有房间，迷宫也生成好了。
"""
不过可能太过简单？有没有大神指导一二，简述即可，灰常感谢
 |
1
elsagong OP 捞一下
|
 |
2
socradi 2019-10-19 23:25:23 +08:00 via Android
之前看到一个迷宫算法就是你这种思路，https://github.com/joewing/maze
|
 |
3
imn1 2019-10-19 23:33:12 +08:00
其实这些题都是很简单的，思路过程也几乎一致的：
就是从“答案”开始 1.先设置一个环境，不存在任何谜题的环境 2.设定唯一解，并根据唯一解设定相应条件 3.设定迷惑解，根据迷惑解设定相应条件，并反向重置其中一个或多个条件，让这个迷惑解无效，不能成为真正的解 4.补充修饰内容 这就是制作任意谜题的思路 |
 |
4
across 2019-10-19 23:43:56 +08:00
术语叫
过程化生成 Procedural Generation 或 过程化处理 Procedural Process 或者搜 dungeon generation、roguelike 之类的关键词吧。暗黑类型的随机地牢。 参考这个 https://learn.unity.com/project/procedural-cave-generation-tutorial |
 |
5
v4ex4b 2019-10-20 00:02:52 +08:00
之前写迷宫类游戏的时候，了解过迷宫生成算法，最后找到一个博客介绍的算法来生成，Eller’s algorithm （具体已经忘得七七八八了
那个博客有一系列专门研究迷宫生成算法的文章，楼主可以去参考下 http://weblog.jamisbuck.org/2010/12/29/maze-generation-eller-s-algorithm |
 |
6
taogen 2019-10-20 08:27:34 +08:00 via iPhone
回溯
1. 定义迷宫节点结构体，包含四面墙四个布尔变量。 2. 初始化二维迷宫矩阵 N*N，定义访问二维数组 visited，定义步数变量 pos。 3. 进行回溯，每走一步 pos+1，无路可走回溯 pos - 1。结束条件当 pos = N*N 时结束递归，打印迷宫矩阵。 |
 |
11
CrazyRundong 2019-10-20 18:41:28 +08:00
专门有一本书讲迷宫生成算法的哈：[J. Buck. Mazes for programmers, code your own twisty little passages. 2015]( https://download.csdn.net/download/leeming0503/10038716)
|
 |
12
necomancer 2019-10-20 19:26:20 +08:00
这不是自避无规行走模型吗……走 n 步的二维均方末端距应该是 R^2~n^(0.75)...直接做矩阵你可能需要一个很大的矩阵……我有个思路，你做连续空间的无规行走，每走一个单位的时候和之前所有粒子做个判定，距离小于步长则重走，总共走 N 步，和之前的 o(N^2) 循环可以考虑加个 linked-cell list，走完以后你用步长取个 histogram 就完事了。
|
 |
13
vicalloy 2019-10-21 09:26:41 +08:00
https://github.com/vicalloy/lb-maze
以前写的迷宫生成器，里面有 JS 和 Python 的实现。 |
Select Language