用 Mathematica 生成迷宫

简介

人类创造迷宫的历史至少可以追溯到 5000 年前:1986 年人们在意大利西西里岛上发现了一幅绘制于公元前 3000 年的迷宫的史前壁画。希腊神话中,克里特岛国王米诺斯的儿子,半人半牛怪物的弥诺陶洛斯,就被关在克诺索斯的一座迷宫里。中世纪的英国则流行草坪迷宫,也就是把草坪栽种成迷宫的样式。清朝乾隆年间,圆明园里仿照欧洲的迷宫,用四尺高的雕花砖墙造了一座中西结合的迷宫花园:万花阵。下图是清内府宫廷满族画师伊兰泰所作的《西洋楼透视图铜版画》中的一幅,描绘的就是圆明园里的万花阵迷宫。

在这篇文章里,我将介绍如何利用 Mathematica 自身提供的和网格区域、图论、哈希表(关联)相关的各种函数,来创建形形色色的迷宫。

用图论算法构造迷宫

迷宫是指一种需要玩家从一个指定的起点出发,在用墙隔断形成的分叉道路中辨识选择,最终到达指定终点的游戏。迷宫可以有各种不同的形式和不同的构造方法,这里介绍的是一种很普适的,基于图论的构造方法。用这种方法构造的迷宫,一个显著的特点就是迷宫内部没有封闭区域,内部任意两处之间有且仅有一种走法。

基本原理

下面我们用较为常见的,外轮廓为矩形,分叉道路横平竖直的矩形迷宫为例,来说明这种构造方法的基本原理。下图就是一个典型的矩形迷宫。

要生成这样一个迷宫,首先就是要把这个矩形区域划分成一个个小的单元格,形成一片网格:

每个单元格现在都是互相隔断的,构造迷宫的过程就是"拆墙",让相邻单元格连通的过程。拆掉的墙要是少了,会有单元格仍然封闭不连通;拆掉的墙要是多了,那么两个单元格之间就可能有不止一种走法。这两种情况都不是我们想要的。要拆得恰到好处,我们需要图论相关的知识。

图论的研究对象就是图。一个图看起来是由一些小圆点(称为顶点)和连接这些圆点的直线或曲线(称之为边)组成的图形。从上面这个网格图形出发,我们可以构造一个图。具体构造方法是把每个单元格看作一个顶点,如果两个单元格相邻,也就是有共同的"墙",那么就在这两个单元格对应的顶点之间添加一条边。如下图所示,我们把暗红色的图和黑色的网格叠合在了一起:

这样通过去掉原图的部分边或顶点得到的新图,被称为原图的"子图"。上面图形的红色部分就是个子图。可以注意到,两个单元格(未必相邻)之间如果可以走通,那么子图的顶点之间,必然存在一条由边首尾相连形成的通路。

于是,我们之前说的迷宫的"墙要拆得恰到好处"所具备的两个特点,就可以翻译成子图的性质:没有封闭的单元格,就意味着子图顶点之间是连通的;两个单元格之间只有一种走法,意味着子图顶点之间的通路是唯一的。图论中,具备这两种性质的图被称为"树"。

除此之外,按照上述做法得到的子图还有一个性质:原图的顶点就是子图的顶点,一个都没少。具备这三种性质(连通、两点之间路径唯一、继承原图全部顶点)的子图被成为原图的"支撑树",也叫"生成树"。于是构造迷宫所需要的拆墙过程,就转变成了一个图论问题:找到根据单元格相邻关系构造的图的支撑树。

有了支撑树,拆掉支撑树每条边对应的墙,我们就得到了一个迷宫。最后需要标示出迷宫的起点和终点,由于支撑树具备任意顶点之间路径唯一的性质,所以不论怎么选起点和终点,总是只有一种走法。下面就是通过删掉最外围两处墙,从而标示出起点终点后的迷宫:

实现代码

根据前述的迷宫构造原理,我们可以把构造过程分成三个阶段:划分网格,生成网格对应的图及支撑树,拆墙得到迷宫。Mathematica 丰富的内建函数,让这三个阶段可以用很简短的代码编写实现。

划分网格

还是以前面的矩形迷宫为例来说明网格是如何实现的。比如要画一个 20*15 共 300 个单元格的网格,并不是纵横方向各划 16 和 21 条直线就算完成了的。后续阶段里,需要根据单元格的相邻关系生成图,要根据支撑树删掉一部分单元格的边,这都需要把各个单元格看成彼此独立而互相有联系的个体,这个联系就是它们之间的公共边。

换而言之,我们需要一种特别的数据结构来表示网格,不仅含有几何信息,还需要有彼此之间如何联系的组合信息。传统上表示这种平面分划的数据结构,如 Half-Edge Data Structure 之类的都比较复杂。但 Mathematica 从 10.0 开始提供了 MeshRegion(网格区域)这一函数用来表示各种网格结构,让我们不必自己实现复杂的数据结构。

除了 MeshRegion 之外,Mathematica 还提供了许多配套的函数用于查询网格区域相关的几何与组合信息。我们这里就用 MeshRegion 来表示网格。它接受两个参数,第一个参数是一组点的坐标列表,第二个参数是用点在坐标列表里的位置表示每个单元格,比如 Polygon[{1,2,3,4}] 就表示由第 1、2、3、4 个点组成的四边形。据此,我们利用一些下标技巧,定义矩形网格的函数如下:

rectRegion[20, 15]

生成网格对应的图及支撑树

Mathematica 里有 Graph 函数,只要提供一组边的两端顶点编号就可以生成一个图,而支撑树可以由函数 FindSpanningTree 直接生成。所以我们只要知道网格之间的相邻关系就可以得到支撑树了。Mathematica 还提供了 MeshCellIndex 函数可以查询网格单元(包括多边形、边线段和点)的索引信息,提供了 MeshCells 函数根据索引返回对应的网格单元,利用这两个函数可以写一个生成相邻信息的函数:

举一个例子来看生成的信息是什么:

上面得到的结果是一个关联 Association,也可以叫哈希表,它由一组键和值的对应关系组成。比如 2->{1,4} 就表示 2 号边是 1 号和 4 号两个单元格的公共边。3*3 的网格刚好有 24 条边,1->{1} 这种说明 1 号边只属于 1 号单元格,这表明 1 号边位于网格边界。

有了这样的相邻信息,只要挑出相邻信息中,有两个元素的值,就可以构造一个图,然后再求得这个图的支撑树。下面的函数里,我们给图的边随机赋值作为长度,得到的总长最小的所谓最小支撑树也就是随机的了:

生成迷宫

我们得到的树的顶点编号刚好是单元格的索引,凭借这个关系及之前生成的相邻信息,可以反向查询出要拆掉的墙的编号,从而得到组成迷宫的边的编号:

函数 genRemainingEdges 有三个参数,除了 neighborInfo 相邻信息,tree 支撑树之外,还有一个 extra 表示可以拆掉的最外围的墙。所以我们再写一个函数求得边缘两条边的编号,默认是左上和右下的两条边:

确定了要拆掉的最外围的两条边,也就确定了迷宫的起点和终点的单元格编号,可以直接用函数 FindPath 找到图上连通两个顶点的路径,于是可以写一个迷宫的求解函数。

把之前的几个函数,如生成相邻信息,得到支撑树,求边缘等结合起来,就可以得到最终的根据网格区域生成迷宫及解答的函数:

这个函数返回两个值,一个是组成迷宫的图案,一个是解答。它们都是图形单元,可以单独画出也可以组合在一起,这里为了方便再写一个把迷宫和解答画在一起,其中解答用粗红线表示的函数:

例如:

生成不同样式的迷宫

之前定义的迷宫生成函数不仅仅是针对矩形网格的,从支撑树到求解,对一般的网格区域都有效,于是只要变化网格区域,我们就可以生成各种迷宫。

变化轮廓

Mathematica 提供一个生成网格区域的函数,DiscretizeRegion,有了它我们可以结合各种生成区域(Region)的函数来得到各种迷宫。比如可以生成一个圆盘或圆环的网格,然后就可以得到相应形状的迷宫:

另外有一个 ImageMesh 函数可以把图像转化为区域,用它我们可以把文字也变成迷宫,需要注意的是生成的网格必须是连通的,也就是说,像"江"这样有不相连的部首的文字不适合生成迷宫:

上面构造文字迷宫的原理是把文字转换为图像,然后用 ImageMesh 得到区域。所以,只要是连通的剪影,都可以用来做迷宫,比如猫和兔子:

变化网格疏密

从上面的例子可以看到,DiscretizeRegion 函数生成的都是三角形的网格,且大小比较均匀一致。参考 Wolfram 博客上的这篇文章 Computational Stippling: Can Machines Do as Well as Humans? 我们可以根据图像内容生成疏密不同的网格。用这样的网格生成的迷宫可以看作是一幅图像的迷宫。首先需要根据那篇博客定义一些函数:

最后综合的函数 genImageRegion 有三个参数,分别是图像,初始点间距的大小和迭代次数。间距越小取点越多,网格也就更精细。点越多,迭代次数越多,生成网格花的时间越长。我们下面以爱因斯坦的头像为例,来看这个函数生成的网格及相应的迷宫。

这是爱因斯坦头像生成的迷宫,注意因为图片大小的限制和线条的粗细,有些小的缝隙因为线条本身的粗细被堵上了,只要将图片放得足够大而保持线条粗细不变,它们之间的空隙还是可以看出来的。我们构造迷宫和解的逻辑保证了这个方法的正确性。

三维迷宫

上面所有的迷宫都是二维的,还可以生成三维的实体迷宫。仍然是利用 Mathematica 的网格区域相关的函数,很简短的代码就能实现,以矩形迷宫为例:

总结

这篇文章里,我们从"拆墙式"的迷宫构造原理出发,利用 Mathematica 丰富的内建函数,实现了基于图论的迷宫构造程序并用它为工具,探索了迷宫各种各样的可能性,从最简单的矩形迷宫,到一般的轮廓迷宫,乃至人像迷宫和三维迷宫。代码的简洁和迷宫的复杂相映成趣,展现了数学之美,算法之美。

原文发布于微信公众号 - WOLFRAM(WolframChina)

原文发表时间:2017-10-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏SeanCheney的专栏

《利用Python进行数据分析·第2版》第13章 Python建模库介绍13.1 pandas与模型代码的接口13.2 用Patsy创建模型描述13.3 statsmodels介绍13.4 sciki

本书中,我已经介绍了Python数据分析的编程基础。因为数据分析师和科学家总是在数据规整和准备上花费大量时间,这本书的重点在于掌握这些功能。 开发模型选用什么库...

1.1K60
来自专栏xingoo, 一个梦想做发明家的程序员

Spark MLlib 之 大规模数据集的相似度计算原理探索

在spark中RowMatrix提供了一种并行计算相似度的思路,下面就来看看其中的奥妙吧!

48700
来自专栏人工智能LeadAI

TF使用例子-LSTM实现序列标注

本文主要改写了一下"Sequence Tagging with Tensorflow"(https://link.jianshu.com?t=https://g...

76980
来自专栏WOLFRAM

用 Mathematica 玩转环面

29050
来自专栏杨熹的专栏

RNN与机器翻译

---- CS224d-Day 9: GRUs and LSTMs -- for machine translation 视频链接 课件链接 ---- 本...

36850
来自专栏从流域到海域

从零开始在Python中实现决策树算法

原文地址:https://machinelearningmastery.com/implement-decision-tree-algorithm-scratc...

58760
来自专栏小鹏的专栏

tf25: 使用深度学习做阅读理解+完形填空

记的在学生时代,英语考试有这么一种类型的题,叫:阅读理解。首先让你读一段洋文材料,然后回答一些基于这个洋文材料提的问题。 我先给你出一道阅读理解 Big ...

64550
来自专栏绿巨人专栏

机器学习中的基本数学知识

82070
来自专栏Pytorch实践

Pointer Network

Pointer Network是seq2seq模型的一种变型。seq2seq模型是一种编码-解码框架的端到端生成模型,已经在机器翻译、对话生成、语法...

45540
来自专栏从流域到海域

How To Implement The Decision Tree Algorithm From Scratch In Python (从零开始在Python中实现决策树算法)

How To Implement The Decision Tree Algorithm From Scratch In Python 原文作者:Jason B...

35490

扫码关注云+社区

领取腾讯云代金券