求一个生成迷宫的思路（无限及复杂）

[elsagong]

可爱的大家，晚上好，

想请教各位一个生成迷宫的思路，不知道「无限」的描述是否到位，英文单词是「 infinite 」，希望能考虑到例外和稀奇古怪的状况，因此我了解到的下面生成迷宫的思路

"""
1.将迷宫地图分成多个房间，每个房间都有四面墙。
2.让“人”从地图任意一点 A 出发，开始在迷宫里游荡。从 A 房间的 1/2/3/4 个方向中的任选一个方向前进。在从 A 房间走到 B 房间的过程中，推倒 A/B 房间之间的墙。
3.如果方向 x 对面的房间已经走过，则选择其他方向。如果所有方向的房间都已经走过，则退回上一个房间看是否还有可选道路。
4.走到真正无路可走时，说明已经走过了所有房间，迷宫也生成好了。
"""

不过可能太过简单？有没有大神指导一二，简述即可，灰常感谢

[elsagong]

捞一下

[socradi]

之前看到一个迷宫算法就是你这种思路，https://github.com/joewing/maze

[imn1]

其实这些题都是很简单的，思路过程也几乎一致的：
就是从“答案”开始
1.先设置一个环境，不存在任何谜题的环境
2.设定唯一解，并根据唯一解设定相应条件
3.设定迷惑解，根据迷惑解设定相应条件，并反向重置其中一个或多个条件，让这个迷惑解无效，不能成为真正的解
4.补充修饰内容

这就是制作任意谜题的思路

[across]

术语叫
过程化生成 Procedural Generation
或
过程化处理 Procedural Process
或者搜 dungeon generation、roguelike 之类的关键词吧。暗黑类型的随机地牢。

参考这个 https://learn.unity.com/project/procedural-cave-generation-tutorial

[v4ex4b]

之前写迷宫类游戏的时候，了解过迷宫生成算法，最后找到一个博客介绍的算法来生成，Eller’s algorithm （具体已经忘得七七八八了

那个博客有一系列专门研究迷宫生成算法的文章，楼主可以去参考下
http://weblog.jamisbuck.org/2010/12/29/maze-generation-eller-s-algorithm

[taogen]

回溯

1. 定义迷宫节点结构体，包含四面墙四个布尔变量。

2. 初始化二维迷宫矩阵 N*N，定义访问二维数组 visited，定义步数变量 pos。

3. 进行回溯，每走一步 pos+1，无路可走回溯 pos - 1。结束条件当 pos = N*N 时结束递归，打印迷宫矩阵。

[elsagong]

@imn1 非常非常感谢你给到的思路🙏🙏祝你和家人周末愉快哦🍀

[elsagong]

@across 太感谢你给到的关键词、链接及检索方法🙏🙏祝你和家人周末愉快哦🍀

[elsagong]

@v4ex4b 感谢你给到的思路和链接🙏🙏祝你和家人周末愉快哦🍀

[elsagong]

@taogen 假装自己明白了🤣感谢你给到的更深层的思路🙏🙏祝你和家人周末愉快哦🍀

[CrazyRundong]

专门有一本书讲迷宫生成算法的哈：[J. Buck. Mazes for programmers, code your own twisty little passages. 2015]( https://download.csdn.net/download/leeming0503/10038716)

[necomancer]

这不是自避无规行走模型吗……走 n 步的二维均方末端距应该是 R^2~n^(0.75)...直接做矩阵你可能需要一个很大的矩阵……我有个思路，你做连续空间的无规行走，每走一个单位的时候和之前所有粒子做个判定，距离小于步长则重走，总共走 N 步，和之前的 o(N^2) 循环可以考虑加个 linked-cell list，走完以后你用步长取个 histogram 就完事了。

[vicalloy]

https://github.com/vicalloy/lb-maze
以前写的迷宫生成器，里面有 JS 和 Python 的实现。