当前位置: 首页 > ds >正文

递归的逻辑(5)——米诺斯的迷宫

  米诺斯迷宫的传说来源于克里特神话,在希腊神话中也有大量的描述,号称世界四大迷宫之一。

  米诺斯是宙斯和欧罗巴的儿子,因智慧和公正而闻名,死后成为了冥国的判官。由于米诺斯得罪了海神波塞冬,波塞冬便以神力使米诺斯的妻子帕西法厄爱上了一头公牛,生下了一个牛首人身的怪物米诺陶洛斯。这个半人半牛的怪物不吃其他食物,只吃人肉,因此米诺斯把他关进一座迷宫中,令它无法危害人间。

  后来雅典人杀死了米诺斯的一个儿子,为了复仇,米诺斯恳求宙斯的帮助。宙斯给雅典带来了瘟疫,为了阻止瘟疫的流行,雅典从必须每年选送七对童男童女去供奉怪物米诺陶洛斯。

  当雅典第三次纳贡时,王子忒修斯自愿充当祭品,以便伺机杀掉怪物,为民除害。当勇敢的王子离开王宫时,他对自己的父亲说,如果他胜利了,船返航时便会挂上白帆,反之则还是黑帆。忒修斯到了米诺斯王宫,公主艾丽阿德涅对他一见钟情,并送他一团线球和一柄魔剑,叫他将线头系在入口处,放线进入迷宫。忒修斯在迷宫深处找到了米诺陶洛斯,经过一场殊死搏斗,终于将其杀死。

  忒修斯带着深爱他的艾丽阿德涅公主返回雅典,却在途中把她抛在一座孤岛上。由于他这一背信弃义的行为,他遭到了惩罚——胜利的喜悦冲昏了他的头脑,他居然忘记更换船上的黑帆!结果,站在海边遥望他归来的父亲看到那黑帆之后,认为儿子死掉了,便悲痛地投海而死。

  似乎我很小的时候就听过这个故事,随着时间的流逝,故事的梗概早已忘却,但那个神奇的迷宫却至今都记忆犹新。虽然不清楚当时的迷宫是怎样设计的,但是我们可以通过递归的方法让米诺斯的迷宫重现人间。

 1 # 迷宫矩阵2 maze = [3     [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],4     [0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1],5     [1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1],6     [1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1],7     [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1],8     [1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1],9     [1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1],
10     [1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1],
11     [1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1],
12     [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1],
13     [1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1],
14     [1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1],
15     [1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1],
16     [1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1],
17     [1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0],
18     [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
19 ]
20 def paint(maze):
21     ''' 打印迷宫 '''
22     for a in maze:
23         for i in a:
24             print('%4d' % i, end='')
25         print()
26
27 if __name__ == '__main__':
28     paint(maze)

  在矩阵中,用0表示通道,1表示墙壁,忒修斯王子可以在0之间任意穿行,矩阵迷宫的打印结果:

迷宫的数据结构

  虽然可以用0和1绘制出一个迷宫,但仍然属于手动编辑,我们的目标是寄希望于计算机,自动生成并绘制一个大型的迷宫:

  迷宫中有很多墙壁,再用0和1组成的简单矩阵就不合适了。如果将迷宫矩阵的每一个位置看作一个方块,则方块的上、下、左、右都可能有墙壁存在,这就需要对每个位置记录四面墙壁的信息:

  实际上没那么复杂,只要记录上墙和右墙就可以了,至于下墙和左墙,完全可以由相邻方块的上墙和右墙代替:

  当然,最后还要在四周套上一层边框:

  在生成迷宫时,每一个方块都需要记录三种信息:是否已经被设置、是否有右墙、是否有上墙。一个较为“面向对象”的方法是将方块信息设计成一个类结构,用三个布尔型属性来记录信息,但是这样做性价比并不高,一种更简单且高效的方式是用一个3位的二进制数来表示:

  矩阵中所有元素的初始值都设置为011,也就是方块未设置、有右墙和上墙;如果已经设置了某个方块,那么第3位被置为1,如此一来,每个方块可能会有5种状态:

  使用下面的代码设置一个8×8迷宫矩阵的初始状态:

 1 # 迷宫矩阵2 class MinosMaze:3     maze = []            # 迷宫矩阵4     n = 0                # 矩阵维度5     init_status = 0b011  # 初始状态,有上墙和右墙6     def __init__(self, n: int):7         ''' 初始化一个 n 维的迷宫 '''8         self.n = n9         # 初始化迷宫矩阵,所有方块未设置、有右墙、有上墙
10         self.maze = [([self.init_status] * n) for i in  range(n)]
11
12     def patin_maze(self):
13         for a in self.maze:
14             for i in a:
15                 print('%4d' % i, end='')
16             print()
17
18 if __name__ == '__main__':
19     m = MinosMaze(8)
20     m.patin_maze()

  我们使用拆墙法自动生成迷宫,这需要遍历迷宫矩阵中的每一个方格,设置是否拆除右墙或上墙。用递归的方法随机遍历上下左右四个方向,直到所有方向全部遍历完为止:

  四个的拆墙过程如下:

  1. 向上遍历,需要拆除当前方格的上墙;

  2. 向下遍历,需要拆除下侧方格的上墙;

  3. 向左遍历,需要拆除左侧方格的右墙;

  4. 向右遍历,需要拆除当前单元格的右墙。

1 class MinosMaze:
2     ……
3     def remove_wall(self, i, j, side):
4         ''' 拆掉maze[i][j] 的上墙或右墙 '''
5         if side == 'U':
6             self.maze[i][j] &= 0b110  # 拆掉上墙
7         elif side == 'R':
8             self.maze[i][j] &= 0b101  # 拆掉右墙

自动生成迷宫

  通过递归的方式遍历方格,迷宫矩阵的方格会逐一被设置:

 1 import random23 class MinosMaze:4     ...5     def create(self):6         ''' 自动创建迷宫 '''7         def auto_create(i, j):8             self.maze[i][j] |= 0b100    # maze[i][j] 已经被设置过9             # 当self.maze[i][j]的上下左右四个方向都是初始状态时,开始拆墙操作
10             while (i - 1 >= 0 and self.maze[i - 1][j] == self.init_status) \
11                     or (i + 1 < self.n and self.maze[i + 1][j] == self.init_status) \
12                     or (j - 1 >= 0 and self.maze[i][j - 1] == self.init_status) \
13                     or (j + 1 < self.n and self.maze[i][j + 1] == self.init_status):
14                 side = random.choice(['U', 'D', 'L', 'R'])   # 随机方向
15                 # 能够向↑走
16                 if side == 'U' and i - 1 >= 0 and self.maze[i - 1][j] == self.init_status:
17                     self.remove_wall(i, j, 'U')     # 拆除当前方格的上墙
18                     auto_create(i - 1, j)           # 向↑走
19                 # 能够向↓走
20                 elif side == 'D' and i + 1 < self.n and self.maze[i + 1][j] == self.init_status:
21                     self.remove_wall(i + 1, j, 'U') # 拆除下侧方格的上墙
22                     auto_create(i + 1, j)           # 向↓走
23                 # 能够向←走
24                 elif side == 'L' and j - 1 >= 0 and self.maze[i][j - 1] == self.init_status:
25                     self.remove_wall(i, j - 1, 'R') # 拆除左侧方格的右墙
26                     auto_create(i, j - 1)           # 向←走
27                 # 能够向→走
28                 elif side == 'R' and j + 1 < self.n and self.maze[i][j + 1] == self.init_status:
29                     self.remove_wall(i, j, 'R')     # 拆除当前单元格的右墙
30                     auto_create(i, j + 1)           # 向→走
31         auto_create(0, 0)   # 从入口位置开始遍历
32
33     def patin_maze(self):
34         ''' 打印迷宫数组 '''
35         for a in self.maze:
36             for i in a:
37                 print('%4d' % i, end='')
38             print()
39
40 if __name__ == '__main__':
41     m = MinosMaze(8)
42     m.create()
43     m.patin_maze()

  程序构造了一个8×8的迷宫,一种可能的结果是:

  矩阵元素的打印的结果是十进制整数,它和二进制的对应关系:

画出迷宫

  绘制迷宫的方法很简单,只需在坐标轴中画出每个方格的墙壁就好了:

 1 import random2 import matplotlib.pyplot as plt34 class MinosMaze:5     ……6     def paint(self):7         # 绘制迷宫内部8         for i in range(self.n):9             for j in range(self.n):
10                 # 有右墙
11                 if self.maze[i][j] & 0b010 == 0b010:
12                     # 右墙的坐标
13                     r_x, r_y = [j + 1, j + 1], [self.n - i, self.n - i - 1]
14                     plt.plot(r_x, r_y, color='black')
15                 # 有上墙
16                 if self.maze[i][j] & 0b001 == 0b001:
17                     # 上墙的坐标
18                     u_x, u_y = [j, j + 1], [self.n - i, self.n - i]
19                     plt.plot(u_x, u_y, color='black')
20
21         plt.axis('equal')
22         ax = plt.gca()
23         ax.spines['top'].set_visible(False)
24         ax.spines['right'].set_visible(False)
25         plt.show()

  看起来不那么像迷宫,这是由于没有添加边框,因此还需要在paint()方法中加上最后的完善工作:

 1 def paint(self):2     ……3     plt.plot([0, self.n], [self.n, self.n], color='black')   # 上边框4     plt.plot([0, self.n], [0, 0], color='black')             # 下边框5     plt.plot([0, 0], [0, self.n], color='black')             # 左边框6     plt.plot([self.n, self.n], [0, self.n], color='black')  # 右边框78     # 设置入口和出口9     entrance, exit = ([0, 0], [self.n, self.n - 1]), ([self.n, self.n], [0, 1])
10     plt.plot(entrance[0], entrance[1], color='white')
11     plt.plot(exit[0], exit[1], color='white')
12
13     plt.axis('equal')
14     ax = plt.gca()
15     ax.spines['top'].set_visible(False)
16     ax.spines['right'].set_visible(False)
17     plt.show()

  出口的位置在迷宫的右下角,由于创建迷宫时遍历了所有方格,因此出口方格一定是从它上侧或左侧的方格遍历而来的,这意味着它一定没有上墙或左墙,拆掉它的右边框一定能够成为出口。现在可以终于可以绘制出一个完整的迷宫了:

  米诺斯的迷宫复杂的多,也许一个32×32的设计图可以困住怪兽:

  


   作者:我是8位的

  出处:http://www.cnblogs.com/bigmonkey

  本文以学习、研究和分享为主,如需转载,请联系本人,标明作者和出处,非商业用途! 

  扫描二维码关注公众号“我是8位的”

http://www.xdnf.cn/news/11188.html

相关文章:

  • 面试题笔试-带答案-1
  • 熟练掌握MATLAB编程语言,具有一定的编程经验;
  • 手把手教你!STM32单片机入门指南:从初级到中级工程师的学习路线
  • 基于的楼盘销售系统(源码+开题)
  • Visio2007注册码(产品密匙)
  • WebService的安全设置
  • js未结束的字符串常量错误解决方法
  • QQ农场外挂源代码
  • HTML通用代码
  • Web 趋势榜: 上周不可错过的最热门的 10 大 Web 项目 - 又增加了那么多的好项目啊 - 210611...
  • Adobe Illustrator CS5 序列号及安装方法
  • 关于雅虎邮箱的Foxmail,outlook设置。
  • 81个技巧——让你玩转Win8!
  • linux lspci信息 详解_Linux引导之EFI SHELL详解
  • PowerDesigner入门使用方法
  • 关于Tor比较全面的讲解
  • 好的飞鸽传书2007未必是“语言律师”
  • Intel, AMD及VIA CPU的微架构(13)
  • 基于深度学习的低光照图像增强
  • Python爬虫入门【3】:美空网数据爬取
  • 最近游戏更新 未整理 无图片
  • 详细配置和安装KaLi系统教程
  • kindle刷多看系统_Kindle PW2 强制降级 救砖 从官方最新版本降级5.4.3.2 TTL 拆机 刷入多看
  • 诺基亚E63凤凰刷机实战
  • 什么样的黑客能用python盗QQ号
  • 电商技术揭秘八:搜索引擎中的SEO内部链接建设与外部推广策略
  • 来自IT公司速查手册的各大IT公司薪资和待遇内幕
  • 干货|555定时器原理+3钟工作状态讲解,原理框图分析,通俗易懂
  • CMOS checksum error-Defaults loaded 故障解决办法
  • Microsoft Enterprise Library: Cache 模块