Random maze solving algorithm with matrix

69 Ansichten (letzte 30 Tage)
Silviu Coman
Silviu Coman am 8 Jan. 2021
Beantwortet: Image Analyst am 18 Dez. 2023
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');

Antworten (3)

Shiva Kalyan Diwakaruni
Shiva Kalyan Diwakaruni am 12 Jan. 2021
Hi ,
you can refer the following link
which consists of maze_solution which works for perfect maze.
hope it helps,
thanks

George Abrahams
George Abrahams am 18 Dez. 2023
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 )

Image Analyst
Image Analyst am 18 Dez. 2023
For a variety of maze-solving algorithms, including one by me and another by Steve Eddins (the leader of image processing team), see:
Also see Steve's blog series on shortest paths:

Kategorien

Mehr zu Graph and Network Algorithms finden Sie in Help Center und File Exchange

Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by