Python趣味题:Prim算法生成完美迷宫

作者 : 开心源码 本文共1581个字,预计阅读时间需要4分钟 发布时间: 2022-05-12 共219人阅读

image

本文详情利用 Prim(普里姆)算法 构建完美迷宫,迷宫的生成过程采用动态展现,可以更清楚的观察迷宫是怎样建立的。所谓 完美迷宫 ,就是没有回路,没有不可达区域的迷宫,并且迷宫中任意两个网格间都有唯一的路径。

利用Prim算法构建迷宫,主要有两种方式:遍历墙和遍历网格。下面分别形容:

Prim遍历墙

要建立行数为A,列数为B的迷宫,则迷宫中一共有AB个网格,网格的编号从0至AB-1。每个网格均有4面墙,因而数据结构可以采用字典的形式。例如,对于编号为n的网格而言,4面墙对应的能设置为:

{(n,'u'):0, (n,'d'):0, (n,'r'):0, (n,'l'):0}

其中键由被这面墙分割的一个网格的编号和方向组成。后面的值代表这面墙的状态标识。例如,本文中0表示保留这面墙,1表示移除这面墙。

下面给出 Prim遍历墙 的算法:

一开始,所有网格的所有墙都保留;

随机选择一个网格,将这个网格加入到遍历过的网格列表里;而后将这个网格的四面墙,增加到候选墙的列表中;

当候选的墙的列表不为空时,进行下面的循环:

(1) 在候选墙的列表中随机选择一面墙。根据这面墙的标识(网格编号和方向)可以得到被这面墙分割的2个网格,例如C1和D2;

(2) 下面对这2个网格进行判断:假如这2个网格仅有1个网格(假设D2)在遍历过的网格列表里,那就移除这面墙(字典中的值变为1),同时在候选墙列表中也移除。同时把另一个网格(也就是C1)增加到遍历过的网格列表中,同时把这个网格(C1)的附近的墙增加到候选墙的列表中,注意只增加字典中的值为0的墙,也就是没有解决过的墙。

(3) 假如这2个网格都在遍历过的网格列表里,说明这面墙需要保留。直接在候选墙的列表中删除就可。由于这面墙尽管字典的值为0,但是分割的2个网格都已经遍历过,所以不可能在被选进候选墙中。

迷宫展现

imageimageimage

Prime遍历网格

对于遍历网格构建的迷宫,尽管也可以采用字典的数据结构,但是不利于绘制迷宫。因而采用二维数组的形式来形容迷宫,而后利用Python的绘图包Matplotlib中的imshow函数来直接绘制。上述操作会把墙也看作网格,也就是每个代表着路的网格会被代表着墙的网格所包围。因而要建立行数A,列数B的迷宫,最终的迷宫的网格数会变为(2A+1)*(2B+1)。对于一个二维数组而言,就是(2A+1)行,(2B+1)列。

绘图是根据二维数组中的数字大小来设定颜色的,因而代表着路和墙的数字是不同的,本例中1代表墙,0代表路。

下面给出 Prim遍历网格 的算法:

首先把所有的网格都视为墙;也就是二维数组所有元素设为1;

在本来是路的位置中随机选择一个网格,也就是在形容迷宫的二维数组中,选择行、列索引都是奇数的。例如[3,3],[5,9]之类的。将这个网格变为路,也就是二维数组对应的数字变为0。而后将这个网格附近的本来是路的网格增加到候选网格列表中去。所谓附近就是之间隔一堵墙的网格。也就是网格的行或者者列索引差2。

当候选网格列表不为空时,进行下面的循环:

(1). 在候选列表中随机选择一个网格,而后对这个网格附近的网格情况进行判断。

(2). 假如附近的网格中有网格已经遍历过(也就是二维数组中对应的值为0),并且与这个网格之间的墙也变为路了,意思就是这个墙对应的数字为0,那就直接把这个网格对应的数字变为0就可。而后在把这个网格附近的,但是没有遍历过的加入到候选网格中。

(3). 假如附近的网格尽管有遍历过的,但是与它之间的墙还是墙,那就把这个墙和这个网格对应的数字均变为0。而后在把这个网格附近的,但是没有遍历过的加入到候选网格中。

迷宫展现

imageimageimage

小编最近整理了一套Python学习教程,有需要的小伙伴,记得来小编的交流群:556370268,就可免费领取一套Python学习教程哦

image

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » Python趣味题:Prim算法生成完美迷宫

发表回复