Random maze solving algorithm with matrix

Question

Silviu Coman 2021-1-8

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/711803-random-maze-solving-algorithm-with-matrix

回答： Image Analyst 2023-12-18

Hello, I am trying to make an alghorithm that solves mazez. I found a few solutions online but they seem very complicated and i tried to make it using a binary matrix. However i am stuck since i am unable to properly plot the shortest path between the top left corner and lower right one. I am new to matlab so i have just been winging it. I made a random maze in the form of a 10x10 matrix in order to test the code and i have considered 1 the path that you can take and 0 the walls. I am not sure how to make the plot only from side to side and up in down so when i try to plot it doesn't take into account the walls. The next problem after that is how to find the shortest route, but i think that is done by adding the segments of the possible paths and seeing which one is the shortest. I am open to any suggestions and thanks in advance!

A=[1,1,0,0,0,0,1,0,0,0;0,1,0,1,0,1,1,1,0,0;0,1,1,1,1,1,0,1,0,0;0,0,1,0,0,1,0,0,1,0;1,1,1,1,1,1,0,0,1,0;0,1,0,0,1,0,0,1,1,0;0,1,0,0,1,1,1,1,0,0;0,1,1,0,0,1,0,0,0,0;0,0,1,1,0,1,0,1,0,0;0,0,0,0,0,1,1,1,1,1];
[x,y] = ind2sub(size(A),find(A==1));
disp([x y]);
colormap([0 0 0; 1 1 1 ]);
image(A .* 255);
hold on;
plot(y,x,'ro');  

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Shiva Kalyan Diwakaruni 2021-1-12

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/711803-random-maze-solving-algorithm-with-matrix#answer_596003

Hi ,

you can refer the following link

https://www.mathworks.com/matlabcentral/fileexchange/27175-maze_solution

which consists of maze_solution which works for perfect maze.

hope it helps,

thanks

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

Answer 2

George Abrahams 2023-12-18

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/711803-random-maze-solving-algorithm-with-matrix#answer_1373562

在 MATLAB Online 中打开

Hi Silviu. One solution is to use my bwgraph function on File Exchange to contruct a graph from the matrix, and then the built-in function shortestpath to find the shortest path between two given nodes.

A = [1,1,0,0,0,0,1,0,0,0;0,1,0,1,0,1,1,1,0,0;0,1,1,1,1,1,0,1,0,0;0,0,1,0,0,1,0,0,1,0;1,1,1,1,1,1,0,0,1,0;0,1,0,0,1,0,0,1,1,0;0,1,0,0,1,1,1,1,0,0;0,1,1,0,0,1,0,0,0,0;0,0,1,1,0,1,0,1,0,0;0,0,0,0,0,1,1,1,1,1];
% Construct the graph of connected non-zero pixels, with a connectivity 
% of 4, i.e., only pixels sharing an edge (not a corner) are connected.
G = bwgraph( A, Connectivity=4 );
% Plot the image and graph.
colormap( 'gray' )
image( A .* 255 )
hold on
sz = size( A );
[ x, y ] = meshgrid( 1 : sz(2), 1 : sz(1) );
h = plot( G, 'XData', x(:), 'YData', y(:), 'NodeLabel', [] );

% Find the shortest path between the nodes [1 1] and [10 10].
source = sub2ind( sz, 1, 1 );
target = sub2ind( sz, 10, 10 );
P = shortestpath( G, source, target );
% Highlight the shortest path on the plot.
set( h, 'NodeColor', 'k' )
highlight( h, P, 'EdgeColor', 'r', 'NodeColor', 'r', ...
    'MarkerSize', 5, 'LineWidth', 1.5 )