Random maze solving algorithm with matrix
47 次查看(过去 30 天)
显示 更早的评论
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 个评论
回答(3 个)
Shiva Kalyan Diwakaruni
2021-1-12
Hi ,
you can refer the following link
which consists of maze_solution which works for perfect maze.
hope it helps,
thanks
0 个评论
George Abrahams
2023-12-18
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', [] );
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/1571707/image.png)
% 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 )
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/1571712/image.png)
0 个评论
Image Analyst
2023-12-18
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:
0 个评论
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!