秀一个 Python 脚本生成的新作品

[mathzhaoliang]

请看动态图： https://github.com/neozhaoliang/pywonderland/raw/master/img/wilson.gif

这个图演示的是概率论中的一个随机算法，叫做 Wilson 算法，它生成一个完美迷宫（即一个生成树），而且这个迷宫是在所有完美迷宫中等概率地随机选取的，UST 这个单词的意思是 uniform spanning tree 的简写，即服从一致分布的生成树。

生成迷宫后根据每个顶点与起点的距离对迷宫进行染色，使用的是宽度优先搜索算法。

整个动态图是用 python 一次生成的，不调用任何外部程序和第三方模块。（字体文件没有办法，这是必须的，不过如果不嵌入文本，只生成迷宫的话则不需要此文件）。只要你安装了纯净版的 python2 或者 python3，那么不需要安装任何依赖即可运行。

程序运行时间一般不超过半分钟，生成的动态图一般在 1M 左右，一般包含 1000 - 5000 帧。（是的你没看错，就是这么拽）

项目之前在论坛上发过，不过这次玩了一点新花样。当然最精彩的永远在后面。下一个项目双曲蜂巢正在紧张制作中。

[z0z]

我除了回复还能干什么

[mathzhaoliang]

@z0z 术业有专攻啊。每个人用 python 干的事情是不一样的，我只是选了一个比较少有人玩的方向。

[lieh222]

一脸蒙蔽的进来，一脸蒙蔽的出去

[z0z]

@mathzhaoliang 多谢安慰啊。突然想起来了，大神请移步到这里 https://www.v2ex.com/t/395736#reply3 可否点拨一下文中的那个连接实现计算极限功能的大概原理?

[BBCCBB]

cool

[mathzhaoliang]

@z0z 它那个网站只是调用了后台的一个程序（我猜他是用了 mathematica，不过也可能用的是自己写的其它程序）
。

处理多项式，微分，积分这些属于符号计算的领域（记得吴文俊的机器证明吗？），符号计算有一套自己的算法来表示和研究数学对象，它与通常进行数值计算的科学计算器很不一样。比如分解多项式，它就是先在有限域上计算（有限域运算比较慢，但是不存在精度损失的问题），然后回到实数域上。插值的方法也很常用，但是不是你想的那种用法。

[xrlin]

厉害

[ipwx]

@z0z Python 的话，有 SimPy，有 Sage Math。

[vtwoextb]

一脸蒙蔽的进来，一脸蒙蔽的出去

[SakuraSa]

很 cool，不知道能不能放出源码供大家学习一下？

[z0z]

@mathzhaoliang 多谢，我按照这个思路先去查查，目前我还不能就此问题回复，因为我还不知道该说什么，我是不是暴露了我的数学还很不好.......

@ipwx 多谢啊，这个我也去查查。

[shingle]

@SakuraSa 根据 gif 图的路径看不出来 github 项目地址么 ╮(╯_╰)╭

[CEBBCAT]

好棒！我要在我们 Minecraft 服务器用这个做多层迷宫

[dalang]

cool

[malkavia]

github 已 star
好厉害

[SakuraSa]

@shingle 我没注意到...
点进去居然发现是我以前 star 过的...

[mathzhaoliang]

@CEBBCAT 这个方法比常用的 Prim, Kruskal 算法要慢，它的关键在于生成的迷宫服从一致分布。你在游戏里面用这个算法估计会很慢 。。。

[CEBBCAT]

@mathzhaoliang #17 (●'◡'●)，人工识图盖迷宫

[Mcatt]

厉害

[liyang803]

一脸蒙蔽的进来，一脸蒙蔽的出去