given a 2-D maze stored in a 2-D array

eg:

SWWWW
. . . . .
W.W.W
. . . . F

S is starting point
F is exit
. is the path
W is the wall.

After the player enters the maze, s/he tries to find a path to reach the exit. Assume that the player can only move towards 4 directions: right, down, left and up, and can only move 1 room each time. The heuristic adopted by the player could be like this:
-If the current room is the exit, s/he successfully finished the route.
- Otherwise, s/he's still on the trip. S/he can try to move right, down, left or up to see whether there is a way to reach the exit. If s/he encounters a wall or a boundary of the matrix in the chosen direction, it means there are no ways in this direction and s/he should try another.

If there are more than 1 routes, print the routes separately

Sample results for the above maze:

./maze 4 6 (<===4,6 are the size of this maze)

0, 0
1, 0
1, 1
1, 2
1, 3
2, 3
3, 3
3, 4

0, 0
1, 0
1, 1
2, 1
3, 1
3, 2
3, 3
3, 4

my function is here but there seems to be some error..

bool result = false; <==global variable

bool path(char maze[][MAXCOL], int r, int c, int x, int y, int end_x, int end_y){
// base case
if (x == end_x && y == end_y){
cout << x << ", " << y << endl;
return true;
}

// recursive case
// cout << x << ", " << y << endl;
if (maze[x-1][y] != 'W' && (x - 1) >= 0 && maze[x-1][y] != 'm'){
maze[x][y] = 'm';
if (result = path(maze, r, c, x-1, y, end_x, end_y))
cout << x << ", " << y << endl;
}
if (maze[x+1][y] != 'W' && (x + 1) <= (r - 1) && maze[x+1][y] != 'm'){
maze[x][y] = 'm';
if (result = path(maze, r, c, x+1, y, end_x, end_y))
cout << x << ", " << y << endl;
}
if (maze[x][y-1] != 'W' && (y - 1) >= 0 && maze[x][y-1] != 'm') {
maze[x][y] = 'm';
if (result = path(maze, r, c, x, y-1, end_x, end_y))
cout << x << ", " << y << endl;
}
if (maze[x][y+1] != 'W' && (y + 1) <= (c - 1) && maze[x][y+1] != 'm'){
maze[x][y] = 'm';
if (result = path(maze, r, c, x, y+1, end_x, end_y))
cout << x << ", " << y << endl;
}
if (maze[x-1][y] == 'W' && (x - 1) <= 0)
return false;
if (maze[x+1][y] == 'W' && (x + 1) >= (r-1))
return false;
if (maze[x][y-1] == 'W' && (y-1) <= 0)
return false;
if (maze[x][y+1] == 'W' && (y+1) >= (c-1))
return false;
}

## All 3 Replies

The result is quite strange as I got
3, 1
1, 3
1, 3
2, 3
3, 3
3, 4
3, 3
3, 2
3, 1
2, 1
1, 1
1, 1
0, 0

anyone can give me some ideas about the base case and recursive case?

*note, there is no separation between "." ad "W" of the maze. I separate the symbol just for making it easier to read

Just a question, but does it have to be recursive? I had to write something similar to this, and what I did was use a while that kept going until they hit the end of the maze. It is on this site somewhere if you feel like searching for it...

Anyway, here's the pseudo code of how I would handle it.

``````function (/*position in maze*/,
/*whatever else...*/)
if (/* at end */)
{ /* do whatever you need to do when they hit the end */ }
else
{ // determine where they can move (U, D, R, L, & back possibly)
// list where they can move
// ask where they'd like to move and then move there if it was valid
// call recursive function again with new info
}``````

If that's not clear, feel free to ask.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.