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

一个完美的算法,生成完美的迷宫

  •  
  •   sillydaddy · 2020-09-24 11:12:14 +08:00 · 2473 次点击
    这是一个创建于 1506 天前的主题,其中的信息可能已经有所发展或是发生改变。

    算法生成的迷宫非常均匀,均匀的意思就是:这个算法能达到的效果就相当于是,把所有的迷宫都枚举出来,然后随机选取一个。不过真实中是不可能全部枚举再选取的,因为数据量太大。

    既然是均匀的,那么,就有可能迷宫非常复杂,也可能比较简单,当然复杂的比较少,简单的比较多,就看运气了。

    思路和算法就是 v 友 @mathzhaoliang 的文章: https://v2ex.com/t/709718#reply2

    7 条回复    2020-09-26 10:19:06 +08:00
    mathzhaoliang
        1
    mathzhaoliang  
       2020-09-24 11:27:24 +08:00 via Android
    对的,在一个超大的集合(大到全世界的计算机都装不下)里面随机取样不是一件简单的事情。但是巧妙的算法可以生长出一个来。随机生成树后面的数学可以非常复杂,当然也非常有趣。
    jaoyina
        2
    jaoyina  
       2020-09-24 12:44:27 +08:00 via iPhone
    好深奥。
    littlewing
        3
    littlewing  
       2020-09-24 12:57:15 +08:00
    佩服,对我来说太难了
    jedihy
        4
    jedihy  
       2020-09-24 13:44:22 +08:00
    我几年前写过一个用并查集,好像不复杂。
    https://github.com/csujedihy/pythonTkMaze/blob/master/MazeGenerator.py
    mathzhaoliang
        5
    mathzhaoliang  
       2020-09-24 14:06:35 +08:00 via Android
    @jedihy 这里的关键是生成的迷宫是完全随机的,每个迷宫被选中的概率相等。kruskal prim 算法都做不到。而且那个代码可以一秒钟生成几千帧的 gif 动图。
    lxfcool
        6
    lxfcool  
       2020-09-25 08:29:55 +08:00
    新思路 感谢
    WordGe2020
        7
    WordGe2020  
       2020-09-26 10:19:06 +08:00
    既然是随机选,似乎不需要枚举所有,直接随机枚举一个就是了。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1777 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 33ms · UTC 16:43 · PVG 00:43 · LAX 08:43 · JFK 11:43
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.