欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

使用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
    % 判断当前点上下左右四个方向能不能走通
    %1234
    % 并把分歧存入队列
    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');

输出结果:
使用matlab生成迷宫

相关标签: matlab 算法