Using recursion to work through a maze

[TimL]

I just completed a program that uses recursion to get through a maze specified by a two-dimensional 12x12 array. The program works pretty much the way I wanted it to, but I was wondering if there was a way to stop the collapsing of functions once a return; line is reached other than by using a loop for most of the lines in the function.

The problem I ran into was that when reaching a dead end, the program would collapse all the way back to the beginning of the maze and display a message saying it was unsuccessful. By placing all of the code that tests for a valid move inside a loop, and marking where I had already been in the maze, I was able to get the collapsing of recursive functions to stop at the most recently passed junction and continue checking for valid moves from that point. I am not convinced this is the most efficient method for solving a maze problem using recursion, though.

I can provide my code if necessary, but since it is almost 150 lines I wasn't sure if I should just throw it in my post or not.

[Disch]

The whole point of using recursion for this is so you don't have to keep track of where you've been already.

Whenever the recursive function calls itself, it should examine the called function's output and adjust its output accordingly.

The actual logic for the recursive function should actually be pretty simple. Here's an example:

bool FindPath( const Map& mymap, int x, int y )
{
  if( mymap.IsGoal(x,y) )
    return true;  // found exit/goal

  // otherwise try to move in every direction by calling FindPath again
  //  if it returns true, we also return true because we found the path:
  if( CanMoveUp(...) )
  {
    if(FindPath(...))  return true;
  }

  if( CanMoveLeft(...) )
  {
    if(FindPath(...)) return true;
  }

  //....

  // if none of those panned out, then we are not on the right path
  return false;  // so report back failure
}

EDIT: of course this approach will loop infinitely if your maze has a path that loops into itself. The above function would keep going in circles and never escape. If that is a possibility for this maze you will need to keep track of where you've been somehow and stop if you run into a place you've already been on a given path.

[Mathhead200]

This is a perfect problem for recursion. You could code the algorithm using a loop but you would need to store the possible choices at each intersection in a stack (queue, list, ...) and those stacks in a stack as well for each intersection. It would be much sloppier looking. The advantage would be knowing how much memory you are using (stack size) if you wanted an exit clause of some kind.

//Maybe something like this...?

struct Choice {
	...
};

struct Intersection {
	stack<Choice> choices;
};

solveMaze() {
	stack<Intersection> intersections;
	...
	while( path_exists || !intersections.is_empty() ) {
		...
		Intersection current_intersection = intersections.pop();
		if( current_intersection.is_empty )
			continue;
		Choice current_choice = current_intersection.choices.pop();
		...
	}
	...
}

Again, I would go with recursion if it works, and does what you want!

[TimL]

Thanks for the feedback.

@Disch: The logic you show is somewhat similar to what I have. Mine isn't quite as clean, but still similar. When you pass arguments to the next iteration of the recursive function, are you sending it the current location, or the future location after the calculated move is made? Mine does the latter.

@Mathhead200: Unfortunately I am not familiar yet with queues, lists, struct, so I'm not sure I can follow your code too well. It sort of makes sense, but I'm sure I'm missing quite a bit.

[Disch]

Well mine was just pseudo code. It isn't really complete, it's just to show the overall idea.

If you have that same (or a similar) idea and it's not working then you probably just have some debugging to do. Can you post the source?

[TimL]

My code actually does work, but I don't know if it could be made more efficient.

The "facing" variable simply keeps track of which direction the computer is moving through the maze (0 is up, 1 is right, 2 is down, 3 is left), and the computer will always try to go to the right, based on its direction of movement, whenever possible.

In the maze, the hashes are walls and the dots are the valid path.

#include <iostream>

using std::cin;
using std::cout;
using std::endl;

void printMaze(const char maze[][12], int xLoc, int yLoc);
int mazeTraverse(char maze[][12], int xLoc, int yLoc, int facing);

int main()
{
	char maze[ 12 ][ 12 ] =
      { {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},
      {  '#', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.', '#'},
      {  '.', '.', '#', '.', '#', '.', '#', '#', '#', '#', '.', '#'},
      {  '#', '#', '#', '.', '#', '.', '.', '.', '.', '#', '.', '#'},
      {  '#', '.', '.', '.', '.', '#', '#', '#', '.', '#', '.', '.'},
      {  '#', '#', '#', '#', '.', '#', '.', '#', '.', '#', '.', '#'},
      {  '#', '.', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#'},
      {  '#', '#', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#'},
      {  '#', '.', '.', '.', '.', '.', '.', '.', '.', '#', '.', '#'},
      {  '#', '#', '#', '#', '#', '#', '.', '#', '#', '#', '.', '#'},
      {  '#', '.', '.', '.', '.', '.', '.', '#', '.', '.', '.', '#'},
      {  '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'} };
	int success = 0;

	success = mazeTraverse(maze, 2, 0, 1);	// Call function to move through the maze, assign returned value to success.

	if (success == 1)	// If success is equal to 1...
		cout << "Congratulations! The maze has been solved.\n";	// ...output congratulations...
	else	// ...else...
		cout << "Unfortunately the maze has not been solved correctly.\n";	// ...output failed message.

	return 0; // End program.
}

// print the current state of the maze
void printMaze( const char maze[][ 12 ], int xLoc, int yLoc)
{
   // nested for loops to iterate through maze
   for ( int x = 0; x < 12; ++x ) 
   {
      for ( int y = 0; y < 12; ++y )
		  if ((x == xLoc) && (y == yLoc))
			  cout << 'X' << ' ';
		  else
			  cout << maze[ x ][ y ] << ' ';

      cout << '\n';
   } // end for

   cout << "\nHit return to see next move\n";
   cin.get();
} // end function printMaze

// Traverse through the maze one square at a time
int mazeTraverse(char maze[][12], int xLoc, int yLoc, int facing)
{
	int success = 0;

	maze[xLoc][yLoc] = '*';   // Mark current location in the maze.

	printMaze(maze, xLoc, yLoc);	// Call function to display maze with current location marked.
	
	while (success == 0)	// While success is not equal to 0...
	{
		if ((xLoc == 4) && (yLoc == 11))	// If current location is the exit of the maze...
		{
			success = 1;	// ...set success to 1.
		}
		else if (facing == 0)	// Else if facing up...
		{
			if (maze[xLoc][yLoc+1] == '.')	// ...check square to the right for valid move...
			{
				success = mazeTraverse(maze, xLoc, yLoc+1, 1);	// Move to the right.
			}
			else if (maze[xLoc-1][yLoc] == '.')	// ...check square above for valid move...
			{
				success = mazeTraverse(maze, xLoc-1, yLoc, 0);	// Move up.
			}
			else if (maze[xLoc][yLoc-1] == '.')	// ...check square to the left for valid move...
			{
				success = mazeTraverse(maze, xLoc, yLoc-1, 3);	// Move to the left.
			}
			else	// If nowhere to go...
				return 0;	// ...close recursion to the previous junction.
		}
		else if (facing == 1)	// If facing right...
		{
			if (maze[xLoc+1][yLoc] == '.')	// ...check square below for valid move...
			{
				success = mazeTraverse(maze, xLoc+1, yLoc, 2);	// Move down.
			}
			else if (maze[xLoc][yLoc+1] == '.')	// ...check square to the right for valid move...
			{
				success = mazeTraverse(maze, xLoc, yLoc+1, 1);	// Move right.
			}
			else if (maze[xLoc-1][yLoc] == '.')	// ...check square above for valid move...
			{
				success = mazeTraverse(maze, xLoc-1, yLoc, 0);	// Move up.
			}
			else	// If nowhere to go...
				return 0;	// ...close recursion to the previous junction.
		}
		else if (facing == 2)	// If facing down...
		{
			if (maze[xLoc][yLoc-1] == '.')	// ...check square to the left for valid move...
			{
				success = mazeTraverse(maze, xLoc, yLoc-1, 3);	// Move to the left.
			}
			else if (maze[xLoc+1][yLoc] == '.')	// ...check square below for valid move...
			{
				success = mazeTraverse(maze, xLoc+1, yLoc, 2);	// Move down.
			}
			else if (maze[xLoc][yLoc+1] == '.')	// ...check square to the right for valid move...
			{
				success = mazeTraverse(maze, xLoc, yLoc+1, 1);	// Move to the right.
			}
			else	// If nowhere to go...
				return 0;	// ...close recursion to the previous junction.
		}
		else if (facing == 3)	// If facing left...
		{
			if (maze[xLoc-1][yLoc] == '.')	// ...check square above for valid move...
			{
				success = mazeTraverse(maze, xLoc-1, yLoc, 0);	// Move up.
			}
			else if (maze[xLoc][yLoc-1] == '.')	// ...check square to the left for valid move...
			{
				success = mazeTraverse(maze, xLoc, yLoc-1, 3);	// Move to the left.
			}
			else if (maze[xLoc+1][yLoc] == '.')	// ...check square below for valid move...
			{
				success = mazeTraverse(maze, xLoc+1, yLoc, 2);	// Move down.
			}
			else	// If nowhere to go...
				return 0;	// ...close recursion to the previous junction.
		}
	}	// ...end while loop.

	return success;	// Return value of success.
}

[Mathhead200]

TimL wrote:

Unfortunately I am not familiar yet with queues, lists, struct, so I'm not sure I can follow your code too well.

Well in short, a stack is like a deck of cards in that you can put cards on top or take them off the top (and possibly count them.) When you take an element off a stack it is called popping, and when you add an element to a stack it is called pushing. Sometime stacks are referred to as being in FIFO (First In First Out) order.

A queue is like a line of people at the store. You get in line at the back, but the next person to be pulled out of line is at the front (although in Computer Science you think of the person at the cash register as at the end of the queue, i.e. the earliest person who was added. And, you yourself would be at the beginning of the queue.) Queues would be in FILO (First In Last Out) order.

A *stack* is the type of structure that controls recursive function behind the scene. That is, each time a call is made to the containing function, the current function's state is added to a stack to keep track of it.