(本节适合已经阅读了前一节或已有matlab面向对象基础的读者阅读,如果恰巧对图论问题感兴趣那就更好)
$ 1.1 算法介绍
这里我们使用普利姆算法来生成迷宫,该算法思路如下:
·前提: 将迷宫视作是由一个个格子组成,格子之间可能有墙壁也可能没有,可解迷宫的基本条件就是存在至少一条从起始格子到终止格子的连通路,考虑到迷宫的复杂性,我们期望能使玩家被所有格子干扰(即所有格子都可以到达),因此我们要生成一个连通图.
·开始生成: 先随机选择一个格子,将它纳入可到达列表中,并随机打通它和周围四个(我们假定迷宫是二维的,而且格子都是传统的正方形)格子之间的一堵墙,把那个和它相连的格子纳入可到达列表中.
·循环过程: 从可到达列表中随机选取一个格子,随机打通它和周围某一不可到达格子之间的墙壁,把那个格子也纳入可到达列表中.如果选出来的格子四周的格子都可以到达,那么拉黑这个格子,不再使其进入下一次选取范围(但仍然处在可到达列表中).
·循环终止: 所有格子都可以到达即终止此循环,或者规定除了起点和终点以外的格子都可在迷宫内到达即终止循环,而后打通起点和终点格子的墙壁(和迷宫外的墙壁以及和临近格子的墙壁).
$ 1.2 设计思路
1.2.1 输入输出
首先应该明确输入输出: 输入应该给出迷宫的格子数(长
×
宽),输出为一个格子对象的二维矩阵,这个矩阵可以由前一节提到的类矩阵的生成方法来生成,之后按我们之前所说的算法打通.
1.2.2 类的设计
开始考虑类的设计问题,首先要明确的是对象的属性都应该包括哪些. ·首先是四周墙壁是否都存在(与上左下右的格子是否直接相连),这个属性可以是一个四维向量,也可以是四个分立的布尔值(?),但要注意,如果需要考虑迷宫边界的格子(它们可能缺少几个邻近的格子),这些属性最好还有第三种取值. ·其次是该格子是否可以到达,是否已经被拉黑(虽然可到达,但不再被选中),这是关系到格子在上述循环中是否可以被选中的属性(虽然某种意义上来看,可到达属性可以由墙壁存在性来计算,但这会增加计算负担).
其次是考虑方法函数. ·首先是构造函数,应该明确格子所在位置,如果在边缘,初始化的时候与附近格子直接相连的属性应该有特殊取值,因此接受的参数应该包括整个迷宫的大小和格子所在的位置. ·其次是更新格子的信息,一旦格子被选中,就要考虑是否更新它临近格子信息的问题了,这需要在函数定义的时候传入多个实例,传出多个实例,本例中,包括该格子本身,应该是五个参数.
1.2.3 主体流程
(这个顺序是我个人的习惯,oop总是先考虑类的设计,后看流程,但不管怎样总是要先大致看一下我要用什么干什么,即输入输出) 生成格子矩阵
→
随机选点开始
→
循环循环再循环
→
结束,画个图出来.
$ 1.3 程序代码
1.3.1 类的定义
classdef mazeCell
properties
left;
right;
top;
bottom;
isAccessible;
isOC;
end
methods
function currentCell=mazeCell(coordX,coordY,sizeX,sizeY)
if coordX==
1
currentCell.left=
2;
else
currentCell.left=
0;
end
if coordX==sizeX
currentCell.right=
2;
else
currentCell.right=
0;
end
if coordY==
1
currentCell.top=
2;
else
currentCell.top=
0;
end
if coordY==sizeY
currentCell.bottom=
2;
else
currentCell.bottom=
0;
end
if sizeX==sizeY&&sizeX==
1
currentCell.isAccessible=
1;
else
currentCell.isAccessible=
0;
end
currentCell.isOC=
0;
end
function [leftCell,rightCell,topCell,bottomCell,currentCell]=refreshCell(leftCell,rightCell,topCell,bottomCell,currentCell)
isL=(
leftCell.isAccessible==
1)||(
currentCell.left==
2);
isR=(
rightCell.isAccessible==
1)||(
currentCell.right==
2);
isT=(
topCell.isAccessible==
1)||(
currentCell.top==
2);
isB=(
bottomCell.isAccessible==
1)||(
currentCell.bottom==
2);
if (isL&&isR&&isT&&isB)
currentCell.isOC=
1;
return;
else
randSeq=
rand(
1,
4);
[~,selector]=max(randSeq);
switch selector
case 1
if(~isL)
leftCell.right=
1;
currentCell.left=
1;
leftCell.isAccessible=
1;
end
case 2
if(~isR)
rightCell.left=
1;
currentCell.right=
1;
rightCell.isAccessible=
1;
end
case 3
if(~isT)
topCell.bottom=
1;
currentCell.top=
1;
topCell.isAccessible=
1;
end
case 4
if(~isB)
bottomCell.top=
1;
currentCell.bottom=
1;
bottomCell.isAccessible=
1;
end
end
end
end
end
end
1.3.2 主体循环
function [ Maze ] = mazeGeneration( sizeX,sizeY )
for j=
1:sizeY
topLattice(
j)=mazeCell(
1,
j,
2,sizeY);
bottomLattice(
j)=mazeCell(
2,
j,
2,sizeY);
end
for j=
1:sizeY
a(
j)=mazeCell(
2,
j,
3,sizeY);
end
Maze(
1,:)=topLattice;
for i=
2:sizeX-
1
Maze(
i,:)=a;
end
Maze(sizeX,:)=bottomLattice;
Maze(
floor((sizeX-
2)*
rand(
1)+
2),
floor((sizeY-
2)*
rand(
1)+
2)).isAccessible=
1;
checker=sizeX*sizeY-
1;
while checker
counter=
0;
A=
[Maze.isAccessible];checker=sum(A==
0);
B=
[Maze.isOC];OCchecker=sum(B);
selector=
floor((sizeX*sizeY-checker-OCchecker)*
rand(
1)+
1);
checker=checker-
2;
while selector>
0
if(~Maze(
floor(counter/sizeY+
1),
mod(counter,sizeY)+
1).isAccessible||Maze(
floor(counter/sizeY+
1),
mod(counter,sizeY)+
1).isOC)
counter=counter+
1;
else
counter=counter+
1;
selector=selector-
1;
end
end
counter=counter-
1;
i=
floor(counter/sizeY+
1);
j=
mod(counter,sizeY)+
1;
if(
i==
1)
if(
j==
1)
[~,Maze(1,2),~,Maze(2,1),Maze(1,1)]=refreshCell(mazeCell(
1,
1,
1,
1),Maze(
1,
2),mazeCell(
1,
1,
1,
1),Maze(
2,
1),Maze(
1,
1));
else
if(
j==sizeY)
[Maze(1,j-1),~,~,Maze(2,j),Maze(1,j)]=refreshCell(Maze(
1,
j-
1),mazeCell(
1,
1,
1,
1),mazeCell(
1,
1,
1,
1),Maze(
2,
j),Maze(
1,
j));
else
[Maze(1,j-1),Maze(1,j+1),~,Maze(2,j),Maze(1,j)]=refreshCell(Maze(
1,
j-
1),Maze(
1,
j+
1),mazeCell(
1,
1,
1,
1),Maze(
2,
j),Maze(
1,
j));
end
end
else
if(
i==sizeX)
if(
j==
1)
[~,Maze(i,2),Maze(i-1,1),~,Maze(i,1)]=refreshCell(mazeCell(
1,
1,
1,
1),Maze(
i,
2),Maze(
i-
1,
1),mazeCell(
1,
1,
1,
1),Maze(
i,
1));
else
if(
j==sizeY)
[Maze(i,j-1),~,Maze(i-1,j),~,Maze(i,j)]=refreshCell(Maze(
i,
j-
1),mazeCell(
1,
1,
1,
1),Maze(
i-
1,
j),mazeCell(
1,
1,
1,
1),Maze(
i,
j));
else
[Maze(i,j-1),Maze(i,j+1),Maze(i-1,j),~,Maze(i,j)]=refreshCell(Maze(
i,
j-
1),Maze(
i,
j+
1),Maze(
i-
1,
j),mazeCell(
1,
1,
1,
1),Maze(
i,
j));
end
end
else
if(
j==
1)
[~,Maze(i,2),Maze(i-1,1),Maze(i+1,1),Maze(i,1)]=refreshCell(mazeCell(
1,
1,
1,
1),Maze(
i,
2),Maze(
i-
1,
1),Maze(
i+
1,
1),Maze(
i,
1));
else
if(
j==sizeY)
[Maze(i,j-1),~,Maze(i-1,j),Maze(i+1,j),Maze(i,j)]=refreshCell(Maze(
i,
j-
1),mazeCell(
1,
1,
1,
1),Maze(
i-
1,
j),Maze(
i+
1,
j),Maze(
i,
j));
else
[Maze(i,j-1),Maze(i,j+1),Maze(i-1,j),Maze(i+1,j),Maze(i,j)]=refreshCell(Maze(
i,
j-
1),Maze(
i,
j+
1),Maze(
i-
1,
j),Maze(
i+
1,
j),Maze(
i,
j));
end
end
end
end
end
end
1.3.3 绘制函数
function [ fig ] = mazeDraw( Maze )
[sizeX,sizeY]=
size(Maze);
pMat=
ones((sizeX+
2)*
16+(sizeX+
1)*
2,(sizeY+
2)*
16+(sizeY+
1)*
2)*
255;
for i=
1:sizeX
for j=
1:sizeY
if Maze(
i,
j).left~=
1
pMat(
18*
i-
1:
18*
i+
18,
18*
j-
1:
18*
j)=
0;
end
if Maze(
i,
j).right~=
1
pMat(
18*
i-
1:
18*
i+
18,
18*
j+
17:
18*
j+
18)=
0;
end
if Maze(
i,
j).top~=
1
pMat(
18*
i-
1:
18*
i,
18*
j-
1:
18*
j+
18)=
0;
end
if Maze(
i,
j).bottom~=
1
pMat(
18*
i+
17:
18*
i+
18,
18*
j-
1:
18*
j+
18)=
0;
end
end
end
pMat(
19:
34,
1:
36)=
225;pMat(
18*sizeX+
1:
18*sizeX+
16,
18*sizeY-
1:
18*sizeY+
34)=
225;
imshow(pMat);
end
$ 1.4 结果展示
我也不知道为啥生成了这么简单的迷宫,可能是算法本身不会产生多连通情况吧……没怎么绕直接就出来了…… 最后说下,这个东西其实有致命bug,但是仔细分析代码不难找到,留作作业吧.
下节预告:什么??你还指望有下节??? 看我有机考完还剩下几条命再说吧……
