Python3 趣味系列题7 ------ Prim

作者: AiFany | 来源:发表于2019-03-08 18:06 被阅读20次

maze.jpg

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

利用Prim算法构建迷宫，主要有两种方式：遍历墙和遍历网格。下面分别描述：

Prim遍历墙

要建立行数为A，列数为B的迷宫，则迷宫中一共有A*B个网格，网格的编号从0至A*B-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个网格都已经遍历过，所以不可能在被选进候选墙中。
迷宫展示

image

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。然后在把这个网格周围的，但是没有遍历过的加入到候选网格中。
迷宫展示