Having trouble making my maze solve itself

[icomma]

Hey everyone,

All right, for this assignment for class we had to write something that would randomly generate a maze, draw it in a form, solve itself using recursion, and then draw the correct path. After many, many frustrating hours the end is finally in sight, but I've hit a wall that I can't figure out. As it stands, the maze does generate and draw. Now I'm getting it to solve itself. The idea I'm working at is that it will recursively check every possible exit from the current "cell" until it either hits a dead end, or hits the end of the maze. If it hits the end, it will return true back up through the function, making a note in an array that x,y room is correct (correctPath bool**). Afterward, it will draw whatever lines correspond to the correctPath array.

This is the solveMaze function, where the problem happens:

bool maze::solveMaze(int x, int y) {
	//Base case. If it hits the end of the maze, returns true
	if(x == 9 && y == 9) {
		isSolved = true;
		return true;
	}
	else {
		//This section determines of whether or not there is a possible place to move, with special
		//cases for instances where the array would be taken out of bounds
		bool somewhereToGo = false;
		if(x-1 < 0 && y-1 < 0) {
			if((top[x][y+1] == false && beenThere[x][y+1] == false) || (left[x+1][y] == false && beenThere[x+1][y] == false)) {
				somewhereToGo = true;
			}
		}
		else if(x-1 < 0 && y+1 > 10) {
			somewhereToGo = false;
		}
		else if(x-1 < 0) {
			if((top[x][y+1] == false && beenThere[x][y+1] == false) || (left[x+1][y] == false && beenThere[x+1][y] == false) ||
				(top[x][y] == false && beenThere[x][y-1] == false)) {
					somewhereToGo = true;
			}
		}
		else if(x+1 > 10) {
			somewhereToGo = false;
		}
		else if((top[x][y] == false && beenThere[x][y-1] == false) || (top[x][y+1] == false && beenThere[x][y+1] == false) ||
				(left[x][y] == false && beenThere[x-1][y] == false) || (left[x+1][y] == false && beenThere[x+1][y] == false)) {
					somewhereToGo = true;
		}

		//If no possible moves, returns false on the current cell of the maze...
		if(somewhereToGo == false) {
			return false;
		}
		
		//...but if there is somewhere, then...
		else if(somewhereToGo) {
			if(beenThere[x+1][y] == false && left[x+1][y] == false) {
				if(solveMaze(x+1, y)) {
					correctPath[x][y] = true;
					return true;
				}
				beenThere[x+1][y] = true;
			}
			if(beenThere[x][y+1] == false && top[x][y+1] == false) {
				if(solveMaze(x, y+1)) {
					correctPath[x][y] = true;
					return true;
				}
				beenThere[x][y+1] = true;
			}
			if(beenThere[x][y-1] == false && top[x][y] == false) {
				if(solveMaze(x, y-1)) {
					correctPath[x][y] = true;
					return true;
				}
				beenThere[x][y-1] = true;
			}
			if(x-1 >= 0) {
				if(beenThere[x-1][y] == false && left[x][y] == false) {
					if(solveMaze(x-1, y)) {
						correctPath[x][y] = true;
						return true;
					}
					beenThere[x-1][y] = true;
				}
			}
		}
	}
}

The error comes at line 3: a stack overflow error that occurs while the program is running. When it says top[x][y] it is checking to see if there is a wall at that cell, and left[x][y] is for the left of that cell. Is this something wrong with a piece of my code in particular, or am I just approaching this with an entirely wrong idea? I've changed it so that it just has to reach 0,0 to solve the maze right off the bat, and that works fine, so it seems that the maze just never reaches the end.

Thanks a ton in advance.

[tfityo]

Can you estimate how many times solveMaze() is called?
Usually stack overflow means that too many recursive calls (each call pushes several bytes to stack).

Have you tested the function on small mazes?

[icomma]

My maze is already pretty small at 10x10, but I was going to take your advice and shrink it to test...unfortunately with the way it's coded at the moment, that would take a lot of altering. Although you did get me thinking, so I started the solver one move away from the end (which is 9, 9)--both at 8,9 and 9,8. Both of these worked fine, but any further away and the program froze until the break, at which point I got the "An unhandled exception of type 'System.StackOverflowException' occurred" again.

Potentially, solveMaze() could be called several hundred times, depending on how the maze is generated. Should I start looking for a way to only call it a small amount of times at a time?

[tfityo]

You can include the following code for testing purposes:

int NumberCall = 0;

bool maze::solveMaze(int x, int y) {
        cerr << NumberCall++;
	//Base case. If it hits the end of the maze, returns true
	if(x == 9 && y == 9) {
        //... rest of the code 

[icomma]

Turns out it called around uh... 5000 times before it broke.

But oh well. I fixed it, and am pretty much jumping with joy at this point. Turns out the problem was that I didn't say the room had been visited until AFTER the recursive call, and since it went to any room it hadn't visited yet, it just kept going back and forth. Thanks for your help tfityo, deeply appreciate it.