未分類
26 9 月 2020

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

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

資深大佬 : sillydaddy 0

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

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

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

大佬有話說 (7)

  • 資深大佬 : mathzhaoliang

    对的，在一个超大的集合（大到全世界的计算机都装不下）里面随机取样不是一件简单的事情。但是巧妙的算法可以生长出一个来。随机生成树后面的数学可以非常复杂，当然也非常有趣。

  • 資深大佬 : jaoyina

    好深奥。

  • 資深大佬 : littlewing

    佩服，对我来说太难了

  • 資深大佬 : jedihy

    我几年前写过一个用并查集，好像不复杂。
    https://github.com/csujedihy/pythonTkMaze/blob/master/MazeGenerator.py

  • 資深大佬 : mathzhaoliang

    @jedihy 这里的关键是生成的迷宫是完全随机的，每个迷宫被选中的概率相等。kruskal prim 算法都做不到。而且那个代码可以一秒钟生成几千帧的 gif 动图。

  • 資深大佬 : lxfcool

    新思路 感谢

  • 資深大佬 : WordGe2020

    既然是随机选，似乎不需要枚举所有，直接随机枚举一个就是了。