所谓环形迷宫,是指下图这样的一幅迷宫,用一笔就可以绘制完成:
1
初步画法
它的走法是从中心走到最外面或者反过来,从最外面走到中心。这样的迷宫特点很鲜明,它拓扑上与一个圆同构,或者叫同伦。然后的问题是开口,我们自然希望开口具备某种特征。我选择的特征是:若最内层的圆半径为 1,那么所有开口之间的距离也是 1。带缺口的圆的绘制其实是圆弧,自然的一个问题是问缺口的圆弧弧度是多少,使得圆弧两端之间的距离是 1。假设半径为 n,那么若弧度为 x,则这个特征可以表示为如下方程
解这个方程可得到 x:
当然在构建迷宫的时候,需要打通的是内外两层圆。为了让这两层圆的缺口能对上,我们需要的只是一个角度,然后加减内外层对应的弧度 x/2。因为这个 x/2 和层数 n 相关,所以我们最好把它定义成一个函数:
然后可以定义有一个缺口的圆的函数,参数为半径和开口中心的角度(这个开口中心的角度可以称为主角度),这个函数用于绘制最内层和最外层的圆:
在定义中间层的圆之前,由于 Mathematica 中圆弧函数 Circle 定义很奇怪,为了能正确绘制需要的圆弧,首先需要定义一些辅助函数,首先是把角度归到 [0,2π) 范围内的函数:
然后是逆时针绘制从 a 到 b 的圆弧的函数,不论 a 和 b 大小关系如何,始终绘制从 a 出发,沿圆逆时针行进到 b 的圆弧:
这样就可以从容绘制迷宫中间那些圆弧了,这些圆弧都承担着内层外缘和外层内缘的作用,所以每个都是开了两个口子的圆,也就是两段圆弧:
光有圆弧定义也是不够的,两层圆弧之间的开口要封起来,形成一个"通道",于是就有通道的定义,参数 n 表示从 n 到 n+1 层圆之间的通道:
这样结合 COneGapCircle 函数,可以得到一个最简单的一笔画迷宫如下:
接下来就是定义完整的圆形一笔画迷宫了,可以看到,这个迷宫完全可由各层的角度决定,所以参数就很简单了,从内到外的若干角度组成的列表,然后就可以有一个直观的定义了:
然后给定一些角度,就可以得到迷宫。下面这个的初始状态是一眼可以看出来的迷宫:
02
随机角度选择
第一个观察是这个角度列表长度必须是奇数,不然中心拓扑上就是圆的内部,怎么走也是走不到外面的。
第二个观察则是经过一些简单的试验,可以看到这个角度列表要是设定得不好,那么最终的迷宫会很容易走出来。要生成一个随机的迷宫,我们还得设置一些条件,让它不那么随机。
假设从内到外这个角度列表是 Subscript[a, 1] 到 Subscript[a, n]。那么显然 Subscript[a, i]和 Subscript[a, i+2]在圆上的差异要尽可能的大,如果在圆上同一个位置,那么就是属于一眼看出来的那种了。
不说结合第一个观察,从内到外偶数位置的缺口怎么走也走不到的,即便相邻的偶数接口在圆的同一个位置,也无关紧要。所以这一条原则又可以修正为相邻奇数位置的角度不能一样,而是要尽可能的差异化。
第三个观察是考察相邻的两个角度的,最显然的它们的范围不能有重合,重合的话,这个迷宫的拓扑就变了,不再是简单闭曲线了,这个很不好,内外不分。即便不重合,靠得太近也不好,靠太近了玩家走到那一关直接就能知道往哪个方向走,因为另一个方向得死路一眼就看出来了。
根据上面的观察我们可以定义一个随机生成角度列表的函数,当然在此之前我们需要定义一些辅助函数。首先是判定某个角度是否在一段角度范围内的判定函数,这个判定函数的两个参数必须是逆时针的一段范围,且起点小终点大:
然后是判定第 n 层的缺口主角度 gn 是否和 n 层的另一缺口主角度 g 有重叠的函数。要注意第 n 层的主角度一个是第 n 个角度,更有一个第 n - 1 层的主角度:
再下面是判定两个主角度差异是不是太小的函数:
有了这些判定函数,就可以定义最终的生成函数了:
实验结果看来也不错:
Graphics[CCircleEulerMaze[CGenRandomAngles[19, 3π/2]], ImageSize -> 700]
03
求解路径
光有角度生成迷宫,也不见得尽善尽美,因为这个层数一多,看着人眼睛就晕了,要是能顺便求解就更好了。通过观察可以发现,其实对于一个角度序列,就是要连通奇数位置的(假定起始位置是1)角度。而从哪个方向走取决于偶数位置的角度,要偶数位置的角度没有挡在奇数位置之间。
解路径有两种,一种是圆之间的圆弧,以重视从圆弧出口出来的直线段。后者很好办:
然后就是根据三个弧度来生成解圆弧的函数了:
最后我们把线段和圆弧交替穿插起来,就拼成了完整的解路径。交替穿插是为了能够给后面解路径的动画生成提供方便。
从最后效果看,也蛮不错的: