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

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

  •  
  •   elsagong · 33 天前 · 1709 次点击
    这是一个创建于 33 天前的主题,其中的信息可能已经有所发展或是发生改变。
    可爱的大家,晚上好,

    想请教各位一个生成迷宫的思路,不知道「无限」的描述是否到位,英文单词是「 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
        1
    elsagong   33 天前
    捞一下
        2
    socradi   33 天前 via Android
    之前看到一个迷宫算法就是你这种思路,https://github.com/joewing/maze
        3
    imn1   33 天前
    其实这些题都是很简单的,思路过程也几乎一致的:
    就是从“答案”开始
    1.先设置一个环境,不存在任何谜题的环境
    2.设定唯一解,并根据唯一解设定相应条件
    3.设定迷惑解,根据迷惑解设定相应条件,并反向重置其中一个或多个条件,让这个迷惑解无效,不能成为真正的解
    4.补充修饰内容

    这就是制作任意谜题的思路
        4
    across   33 天前
    术语叫
    过程化生成 Procedural Generation

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

    参考这个 https://learn.unity.com/project/procedural-cave-generation-tutorial
        5
    v4ex4b   33 天前
    之前写迷宫类游戏的时候,了解过迷宫生成算法,最后找到一个博客介绍的算法来生成,Eller’s algorithm (具体已经忘得七七八八了

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

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

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

    3. 进行回溯,每走一步 pos+1,无路可走回溯 pos - 1。结束条件当 pos = N*N 时结束递归,打印迷宫矩阵。
        7
    elsagong   33 天前
    @imn1 非常非常感谢你给到的思路🙏🙏祝你和家人周末愉快哦🍀
        8
    elsagong   33 天前
    @across 太感谢你给到的关键词、链接及检索方法🙏🙏祝你和家人周末愉快哦🍀
        9
    elsagong   33 天前
    @v4ex4b 感谢你给到的思路和链接🙏🙏祝你和家人周末愉快哦🍀
        10
    elsagong   33 天前
    @taogen 假装自己明白了🤣感谢你给到的更深层的思路🙏🙏祝你和家人周末愉快哦🍀
        11
    CrazyRundong   32 天前
    专门有一本书讲迷宫生成算法的哈:[J. Buck. Mazes for programmers, code your own twisty little passages. 2015]( https://download.csdn.net/download/leeming0503/10038716)
        12
    necomancer   32 天前
    这不是自避无规行走模型吗……走 n 步的二维均方末端距应该是 R^2~n^(0.75)...直接做矩阵你可能需要一个很大的矩阵……我有个思路,你做连续空间的无规行走,每走一个单位的时候和之前所有粒子做个判定,距离小于步长则重走,总共走 N 步,和之前的 o(N^2) 循环可以考虑加个 linked-cell list,走完以后你用步长取个 histogram 就完事了。
        13
    vicalloy   32 天前
    https://github.com/vicalloy/lb-maze
    以前写的迷宫生成器,里面有 JS 和 Python 的实现。
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   3512 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 41ms · UTC 05:26 · PVG 13:26 · LAX 21:26 · JFK 00:26
    ♥ Do have faith in what you're doing.