情報工学実験B（人工知能実験）の迷路作成用スクリプト

maze_convert.m

function maze_st = maze_convert(maze)
% MAZE_CONVERT  Convert from a map to Adjacency matrix
%   maze_st = MAZE_CONVERT(maze)
% ARGS
%   maze                  Maze matrix
% RETURN
%   maze_st.A             Adjacency Matrix
%   maze_st.initial_node  Initial node
%   maze_st.target_node   Target node
%   maze_st.xy            xy for gplot
%   maze_st.size          Size of Maze [x,y]
%
% SEE ALSO
%   MAZE_EXAMPLES
%
%   Rev.8 by Sunao Hara, at 2020.11.5
%

%% Create initial_nodes
maze_st.initial_node = find(maze==-1);

%% Create target_nodes
maze_st.target_node  = find(maze==-2);

%% Create adjacency matrix
maze_size = size(maze);  % [y, x]

A = zeros(maze_size(2)*maze_size(1));

for src_y = 1:maze_size(1)
    for src_x = 1:maze_size(2)
        % Ignore 'YOR ARE IN ROCK!'
        if maze(src_y, src_x) == 0; continue; end
        
        % Check a connectivity to the East
        dst_x = src_x + 1;  dst_y = src_y;
        if (dst_x <= maze_size(2)) && (maze(dst_y, dst_x) ~= 0)
            src_id = (src_x-1)*maze_size(1)+src_y;
            dst_id = (dst_x-1)*maze_size(1)+dst_y;
            A(src_id, dst_id) = max(1, maze(dst_y, dst_x));
            A(dst_id, src_id) = max(1, maze(src_y, src_x));
        end
        
        % Check a connectivity to the South
        dst_x = src_x;  dst_y = src_y + 1;
        if (dst_y <= maze_size(1)) && (maze(dst_y, dst_x) ~= 0)
            src_id = (src_x-1)*maze_size(1)+src_y;
            dst_id = (dst_x-1)*maze_size(1)+dst_y;
            A(src_id, dst_id) = max(1, maze(dst_y, dst_x));
            A(dst_id, src_id) = max(1, maze(src_y, src_x));
        end
    end
end

% Keep as an adjacency matrix
maze_st.A    = A;

%% Create Maze size
maze_st.size = maze_size(2:-1:1);

%% Plot the created maze
maze_st.xy = maze_draw(maze_st);

end

function xy = maze_draw(maze_st)
    % MAZE_DRAW  Draw Adjacency Matrix as a MapView

    newplot;

    A = maze_st.A;
    maze_size = maze_st.size;
    initial_node = maze_st.initial_node;
    target_node  = maze_st.target_node;

    [x1, y1] = meshgrid(1:maze_size(1), maze_size(2):-1:1);
    xy = [x1(:) y1(:)];

    %% Plot the Graph
    % Nodes
    [X,Y] = gplot(A, xy);
    plot(X, Y, 'o', 'MarkerSize', 15, 'MarkerFaceColor', 'b', 'MarkerEdgeColor', 'b');
    daspect([1 1 1]); % Keep aspect ratio (data unit)
    
    % Edges
    hold on;
    for n = 1:length(xy)
        m = find(A(n, :) ~= 0);
        for m_ = m
            % Ignore self loop
            if n == m_; continue; end
            
            ln_x = [xy(n, 1) xy(m_, 1)];
            ln_y = [xy(n, 2) xy(m_, 2)];
            mk = '';
            cl = 'b';

            if n < m_ && ln_x(1) ~= ln_x(2)      % Left to right
                ln_y = ln_y + 0.05;
                mk = '>'; %cl = 'b';
            elseif n > m_ && ln_x(1) ~= ln_x(2)  % Right to left
                ln_y = ln_y - 0.05;
                mk = '<'; %cl = 'g';
            elseif n < m_ && ln_y(1) ~= ln_y(2)  % Up to down
                ln_x = ln_x + 0.05;
                mk = 'v'; %cl = 'b';
            elseif n > m_ && ln_y(1) ~= ln_y(2)  % Down to up
                ln_x = ln_x - 0.05;
                mk = '^'; %cl = 'g';
            end
            
            % Draw line and direction marker
            line(ln_x, ln_y, 'LineWidth', 1.5, 'Color', cl);
            scatter(0.34*ln_x(1) + 0.66*ln_x(2), ...
                    0.34*ln_y(1) + 0.66*ln_y(2), ...
                    80, cl, mk, 'filled');  % for Octave 2020.11.5
        end
    end
    hold off;

    %% Highlight 'Initial node' and 'Target node'
    % ☆ 'p', 〇 'o'
    hold on;
    scatter(xy(initial_node,1), xy(initial_node,2), 300, 'w', 'o', 'filled');  % for Octave 2020.11.5
    scatter(xy(initial_node,1), xy(initial_node,2), 700, 'r', 'p', 'filled');  % for Octave 2020.11.5
    scatter(xy(target_node,1), xy(target_node,2), 300, 'r', 'o', 'filled');  % for Octave 2020.11.5
    scatter(xy(target_node,1), xy(target_node,2), 480, 'r', 'o', 'LineWidth', 2);  % for Octave 2020.11.5
    hold off;

    %% Node numbers
    %text(xy(:,1)+0.1, xy(:,2)-0.2, num2cell(1:length(xy)), 'Color', 'k', 'FontSize', 14);
    text(xy(:,1), xy(:,2), num2cell(1:length(xy)), 'Color', 'w', 'FontSize', 11, ...
        'HorizontalAlignment', 'center', 'FontWeight', 'bold');

    %% Edge weights
    for n = 1:length(xy)
        m = find(A(n, :) ~= 0);
        for m_ = m
            % Ignore self loop
            if n == m_; continue; end

            ln_x = [xy(n, 1) xy(m_, 1)];
            ln_y = [xy(n, 2) xy(m_, 2)];

            tx = 0.4*ln_x(1) + 0.6*ln_x(2);
            ty = 0.4*ln_y(1) + 0.6*ln_y(2);

            cl = 'b';
            if n < m_ && ln_x(1) ~= ln_x(2)      % Left to right
                ty = ty + 0.25; %cl = 'b';
            elseif n > m_ && ln_x(1) ~= ln_x(2)  % Right to left
                ty = ty - 0.25; %cl = 'g';
            elseif n < m_ && ln_y(1) ~= ln_y(2)  % Up to down
                tx = tx + 0.25; %cl = 'b';
            elseif n > m_ && ln_y(1) ~= ln_y(2)  % Down to up
                tx = tx - 0.25; %cl = 'g';
            end

            text(tx, ty, num2str(A(n,m_)), 'HorizontalAlignment', 'center', ...
                 'Color', cl, 'FontSize', 12, 'FontAngle', 'italic');
        end
    end

    %% Purge some chart objects
    xlim([min(xy(:,1))-0.6, max(xy(:,1))+0.6])
    ylim([min(xy(:,2))-0.6, max(xy(:,2))+0.6])
    xticks([]); yticks([]);
end

maze_example.m

% 迷路の作り方
% 壁を0として，通れる道は1以上にする．
% スタートは-1でゴールは-2とする．

% 迷路の例1
maze1 = ...
    [-1 0  1 1 1 1 1;
      1 0  0 0 0 0 1;
      1 1  1 1 1 1 1;
      1 0  0 0 0 0 1;
      1 0 -2 1 1 0 1;
      1 0  0 0 1 0 1;
      1 1  1 1 1 1 1];

% 迷路の例2
maze2 = ...
    [-1 0  1 1 1 1 1 0 1;
      1 0  0 0 0 0 1 0 1;
      1 1  1 1 1 1 1 0 1;
      1 0  0 0 0 0 1 0 1;
      1 0 -2 1 1 0 1 1 1;
      1 0  0 0 1 0 0 0 1;
      1 1  1 1 1 1 1 1 1;
      0 0  1 0 1 0 1 0 0;
      1 1  1 0 1 0 1 1 1];

% 迷路の例3
maze3 = ...
    [-1 0  1 1 1 1 1 0 1;
      1 0  0 0 0 0 1 0 1;
      1 1  1 1 1 1 1 0 1;
      1 0  0 0 0 0 1 0 1;
      2 0 -2 1 2 0 1 1 1;
      3 0  0 0 3 0 0 0 1;
      4 5  6 7 1 1 1 1 1;
      0 0  1 0 1 0 1 0 0;
      1 1  1 0 1 0 1 1 1];