Random maze solving algorithm with matrix

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');  

Answer 1

[Shiva Kalyan Diwakaruni]

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

Answer 2

[George Abrahams]

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 )

Answer 3

[Image Analyst]

For a variety of maze-solving algorithms, including one by me and another by Steve Eddins (the leader of image processing team), see:

https://www.mathworks.com/search.html?c%5B%5D=entire_site&q=maze&fq%5B%5D=subcollection:community/blogs&page=1

Also see Steve's blog series on shortest paths:

Exploring shortest paths – bwdistgeodesic