V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
elsagong
V2EX  ›  程序员

求一个生成迷宫的思路(无限及复杂)

  •  
  •   elsagong · 2019-10-19 22:26:00 +08:00 · 3241 次点击
    这是一个创建于 1622 天前的主题,其中的信息可能已经有所发展或是发生改变。
    可爱的大家,晚上好,

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

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

    不过可能太过简单?有没有大神指导一二,简述即可,灰常感谢
    13 条回复    2019-10-21 09:26:41 +08:00
    elsagong
        1
    elsagong  
    OP
       2019-10-19 22:56:01 +08:00
    捞一下
    socradi
        2
    socradi  
       2019-10-19 23:25:23 +08:00 via Android
    之前看到一个迷宫算法就是你这种思路,https://github.com/joewing/maze
    imn1
        3
    imn1  
       2019-10-19 23:33:12 +08:00
    其实这些题都是很简单的,思路过程也几乎一致的:
    就是从“答案”开始
    1.先设置一个环境,不存在任何谜题的环境
    2.设定唯一解,并根据唯一解设定相应条件
    3.设定迷惑解,根据迷惑解设定相应条件,并反向重置其中一个或多个条件,让这个迷惑解无效,不能成为真正的解
    4.补充修饰内容

    这就是制作任意谜题的思路
    across
        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
    v4ex4b
        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
    taogen
        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 时结束递归,打印迷宫矩阵。
    elsagong
        7
    elsagong  
    OP
       2019-10-20 09:52:05 +08:00
    @imn1 非常非常感谢你给到的思路🙏🙏祝你和家人周末愉快哦🍀
    elsagong
        8
    elsagong  
    OP
       2019-10-20 09:52:51 +08:00
    @across 太感谢你给到的关键词、链接及检索方法🙏🙏祝你和家人周末愉快哦🍀
    elsagong
        9
    elsagong  
    OP
       2019-10-20 09:53:35 +08:00
    @v4ex4b 感谢你给到的思路和链接🙏🙏祝你和家人周末愉快哦🍀
    elsagong
        10
    elsagong  
    OP
       2019-10-20 09:54:46 +08:00
    @taogen 假装自己明白了🤣感谢你给到的更深层的思路🙏🙏祝你和家人周末愉快哦🍀
    CrazyRundong
        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)
    necomancer
        12
    necomancer  
       2019-10-20 19:26:20 +08:00
    这不是自避无规行走模型吗……走 n 步的二维均方末端距应该是 R^2~n^(0.75)...直接做矩阵你可能需要一个很大的矩阵……我有个思路,你做连续空间的无规行走,每走一个单位的时候和之前所有粒子做个判定,距离小于步长则重走,总共走 N 步,和之前的 o(N^2) 循环可以考虑加个 linked-cell list,走完以后你用步长取个 histogram 就完事了。
    vicalloy
        13
    vicalloy  
       2019-10-21 09:26:41 +08:00
    https://github.com/vicalloy/lb-maze
    以前写的迷宫生成器,里面有 JS 和 Python 的实现。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1536 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 17:16 · PVG 01:16 · LAX 10:16 · JFK 13:16
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.