使用matlab生成迷宫
程序员文章站
2022-05-22 14:13:57
...
使用matlab生成迷宫,利用深度优先搜索凿穿墙壁遍历迷宫中的可通行点并保证路线不重合。
如何解迷宫见: 使用matlab应用动态规划算法走迷宫.
clc
clear
% 生成迷宫矩阵puzz并初始化
% puzz中的元素:0代表墙,2代表没经过的空地,1代表走过的空地
puzz = 2 * ones(101, 101);
index1 = 1: 2: size(puzz, 1);
index2 = 1: 2: size(puzz, 2);
puzz(index1, :) = 0;
puzz(:, index2) = 0;
puzz(1, :) = 0;
puzz(end, :) = 0;
puzz(:, 1) = 0;
puzz(:, end) = 0;
start = [2, 2];
puzz(start(1), start(2)) = 1;
p_old = start;
queue = [];
% 凿墙建迷宫
while 1
% 判断当前点上下左右四个方向能不能走通
% 上1下2左3右4
% 并把分歧存入队列
legal_direction = [0 0 0 0];
temp = [p_old(1) - 2, p_old(2)];
if temp(1) >= 1 && temp(1) <= size(puzz, 1) && temp(2) >= 1 && temp(2) <= size(puzz, 2)
if puzz(temp(1), temp(2)) == 2
queue = [queue; p_old(1), p_old(2), 1];
legal_direction(1) = 1;
else
queue(ismember(queue, [p_old(1), p_old(2), 1], 'rows'), :) = [];
end
end
temp = [p_old(1) + 2, p_old(2)];
if temp(1) >= 1 && temp(1) <= size(puzz, 1) && temp(2) >= 1 && temp(2) <= size(puzz, 2)
if puzz(temp(1), temp(2)) == 2
queue = [queue; p_old(1), p_old(2), 2];
legal_direction(2) = 1;
else
queue(ismember(queue, [p_old(1), p_old(2), 2], 'rows'), :) = [];
end
end
temp = [p_old(1), p_old(2) - 2];
if temp(1) >= 1 && temp(1) <= size(puzz, 1) && temp(2) >= 1 && temp(2) <= size(puzz, 2)
if puzz(temp(1), temp(2)) == 2
queue = [queue; p_old(1), p_old(2), 3];
legal_direction(3) = 1;
else
queue(ismember(queue, [p_old(1), p_old(2), 3], 'rows'), :) = [];
end
end
temp = [p_old(1), p_old(2) + 2];
if temp(1) >= 1 && temp(1) <= size(puzz, 1) && temp(2) >= 1 && temp(2) <= size(puzz, 2)
if puzz(temp(1), temp(2)) == 2
queue = [queue; p_old(1), p_old(2), 4];
legal_direction(4) = 1;
else
queue(ismember(queue, [p_old(1), p_old(2), 4], 'rows'), :) = [];
end
end
if sum(legal_direction) > 0
% 深度优先,不停凿墙向前进并保证路线不重合
while 1
% 随机选择一个方向,如果方向可行就往那个方向上走一步(两格)
choose_direction = ceil(rand(1)*4);
switch choose_direction
case 1
p_new = [p_old(1) - 2, p_old(2)];
case 2
p_new = [p_old(1) + 2, p_old(2)];
case 3
p_new = [p_old(1), p_old(2) - 2];
case 4
p_new = [p_old(1), p_old(2) + 2];
end
if p_new(1) >= 1 && p_new(1) <= size(puzz, 1) && p_new(2) >= 1 && p_new(2) <= size(puzz, 2)
if puzz(p_new(1), p_new(2)) == 2
puzz((p_new(1)+p_old(1))/2, (p_new(2)+p_old(2))/2) = 1;
puzz(p_new(1), p_new(2)) = 1;
queue(ismember(queue, [p_old(1), p_old(2), choose_direction], 'rows'), :) = [];
p_old = p_new;
break;
end
end
end
else
% 无路可走就退到上一个分歧点
p_old(1) = queue(1, 1);
p_old(2) = queue(1, 2);
end
if sum(sum(puzz == 2)) == 0
break;
end
end
% 输出迷宫
puzz(2, 1) = 1;
puzz(end-1, end) = 1;
imshow(imresize(puzz, 4, 'nearest'));
save('puzzle.mat', 'puzz');
输出结果: