Recursive function Help
2 views (last 30 days)
Show older comments
I have code here with a maze that uses a recursive function to solve the maze and then prints out all the coordinates from start to exit.
% clear workspace
clearvars;
clear global MAZE ROWLIMIT COLLIMIT ROWEND COLEND
% maze, its size, and endpoint must be global
global MAZE ROWLIMIT COLLIMIT ROWEND COLEND
% maze
MAZE(1,:) = '############';
MAZE(2,:) = '# # #';
MAZE(3,:) = ' # # #### #';
MAZE(4,:) = '### # # #';
MAZE(5,:) = '# ### # ';
MAZE(6,:) = '#### # # # #';
MAZE(7,:) = '# # # # # #';
MAZE(8,:) = '## # # # # #';
MAZE(9,:) = '# # #';
MAZE(10,:) = '###### ### #';
MAZE(11,:) = '# # #';
MAZE(12,:) = '############';
% constants & initial values
ROWLIMIT = 12;
COLLIMIT = 12;
rowbegin = 3;
colbegin = 1;
ROWEND = 5;
COLEND = 12;
% solve the maze -- (0,0) is a dummy "previous" value
isPathToExit(0, 0, rowbegin, colbegin);
This is the code I written so far for the recursive function 'isPathToExit':
function success = isPathToExit(previous_row, previous_col, current_row, current_col)
% Finds a path from entrance to exit through the maze
% base case
global MAZE ROWLIMIT COLLIMIT ROWEND COLEND
if current_row == ROWEND && current_col == COLEND
disp(sprintf('(%i, %i)', current_row, current_col));
success = true;
return;
else
success = false;
end
% recursion
if current_row+1 ~= previous_row && MAZE(current_row+1, current_col) ~= '#' && current_row+1 ~= ROWLIMIT && current_row ~= 0
success = isPathToExit(current_row, current_col, current_row+1, current_col);
if success
disp(sprintf('(%i, %i)', current_row+1, current_col));
return;
end
end
if current_row-1 ~= previous_row && MAZE(current_row-1, current_col) ~= '#' && current_row-1 ~= ROWLIMIT && current_row ~= 0
success = isPathToExit(current_row, current_col, current_row-1, current_col);
if success
disp(sprintf('(%i, %i)', current_row-1, current_col));
return;
end
end
if current_col+1 ~= previous_col && MAZE(current_row, current_col+1) ~= '#' && current_col+1 ~= COLLIMIT && current_col ~= 0
success = isPathToExit(current_row, current_col, current_row, current_col+1);
if success
disp(sprintf('(%i, %i)', current_row, current_col+1));
return;
end
end
if current_col-1 ~= previous_col && MAZE(current_row, current_col-1) ~= '#' && current_col-1 ~= COLLIMIT && current_col ~= 0
success = isPathToExit(current_row, current_col, current_row, current_col+1);
if success
disp(sprintf('(%i, %i)', current_row, current_col-1));
return;
end
end
When I run it, it displays the points up to a wall of the maze and stops. I need it display the points from start to exit.
0 Comments
Accepted Answer
Alex
on 17 Nov 2011
A few comments: 1. using global variables, then settings and clearing them is a bad habit to get into.
2. disp(Maze(i,j)); will not show the coordinates, it'll only show the element of the Maze that is the current position, which all of those should be " " white space.
If you want the indicies, use:
disp(sprintf('The current maze index is %i and %i, current_row, current_col));
3. Your if statements are very hard to read. Also, you're putting the recursive statements within the if statement itself, I would recommend separating those. This makes debugging easier. Additionally, you don't need to have all those conditions based on row_limit, col_limit, and such. Since the entire maze is surounded by '#', all you need to do is check in the 3 remaining directions for a solution
ex:
function success = Recursive_Fcn(prev_row, prev_col, next_row, next_col)
if (at maze exit)
sucess = true
return
else
sucess = false;
end
if(prev pt was not from up && up point is clear && ~sucess )
sucess = recursive statement(up direction)
if(success)
print pt
end
end
if(prev pt was not from down && down point is clear && ~sucess )
sucess = recursive statement(down direction)
if(success)
print pt
end
end
if(prev pt was not from lwft && left point is clear && ~sucess )
sucess = recursive statement(left direction)
if(success)
print pt
end
end
if(prev pt not from right && right pt is clear && ~success)
success = recursive statement(right direction)
if(success)
print pt
end
end
return
I made these changes to your code and got it to work.
31 Comments
More Answers (0)
See Also
Categories
Find more on Labyrinth problems in Help Center and File Exchange
Products
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!