[SOLVED] C++ 3D Maze Traversal!

mitchell7man · 11-05-2013, 01:43 AM

Hi everyone, I'm taking a c++ class, and am working on a project that creates a 3d maze and then works on solving it.
So I made a 3d vector maze of a custom data structure called cube

Code:

#include "cube.h"
Cube :: Cube(void)
{
    cube_value = 0;
    visited = false;
    gone_right = 0;
    gone_left = 0;
    gone_up = 0;
    gone_down = 0;
    gone_forward = 0;
    gone_backward = 0;
    
}
Cube :: ~Cube(void){}

I've successfully implemented random population of the 3d maze, i'm on the last part of the project which is to solve the maze, the idea is to traverse the maze and leave the coordinates of the path on the stack. I use a different function to organize these into a nice array of points. Anyway my code for solving is this:

Code:

bool PathFinder :: findPath(int x, int y, int z)
{
	find_x = x;
	find_y = y;
	find_z = z;
	string insert_x, insert_y, insert_z;
	ostringstream stream_x, stream_y , stream_z;
	stream_x << find_x;
	stream_y << find_y;
	stream_z << find_z;
	insert_x = stream_x.str();
	insert_y = stream_y.str();
	insert_z = stream_z.str();
	cout << "working on" << insert_x << " " << insert_y << " " << insert_z << endl;
	if(find_x < 0 || find_y < 0 || find_z < 0 || find_x > 4 || find_y > 4 || find_z > 4)
	{
		cout << "out of bounds" << endl;
		return false;
	}
	if(Maze[find_x][find_y][find_z].cube_value != 1 && Maze[find_x][find_y][find_z].visited != true)
	{
		// then it is a wall
		cout << "is a wall" << endl;
		Maze[find_x][find_y][find_z].visited = true;
		return false;
	}
	if(find_x == 4 && find_y == 4 && find_z == 4 && (Maze[find_x][find_y][find_z].cube_value == 1))
	{
		cout << "is finish" << endl;
		return true;
	}
	else
	{

		string to_push = "(" + insert_x + ", " + insert_y + ", " + insert_z + ")";
		cout << "pushing" << to_push << endl;
		pathstack.push(to_push);
		Maze[find_x][find_y][find_z].visited = true;
		bool is_deadend = true;
		if(findPath(find_x+1,find_y,find_z) && Maze[find_x-1][find_y][find_z].visited != true && Maze[find_x][find_y][find_z].gone_right == false)
		{
			Maze[find_x][find_y][find_z].gone_right = true;
			bool is_deadend = false;
			return true;
		}
		if(findPath(find_x-1,find_y,find_z) && Maze[find_x+1][find_y][find_z].visited != true && Maze[find_x][find_y][find_z].gone_left == false)
		{
			Maze[find_x][find_y][find_z].gone_left = true;
			bool is_deadend = false;
			return true;
		}
		if(findPath(find_x,find_y+1,find_z) && Maze[find_x][find_y-1][find_z].visited != true && Maze[find_x][find_y][find_z].gone_up == false)
		{
			Maze[find_x][find_y][find_z].gone_up = true;
			bool is_deadend = false;
			return true;
		}
		if(findPath(find_x,find_y-1,find_z) && Maze[find_x][find_y+1][find_z].visited != true && Maze[find_x][find_y][find_z].gone_down == false)
		{
			Maze[find_x][find_y][find_z].gone_down = true;
			bool is_deadend = false;
			return true;
		}
		if(findPath(find_x,find_y,find_z+1) && Maze[find_x][find_y][find_z-1].visited != true && Maze[find_x][find_y][find_z].gone_forward == false)
		{
			Maze[find_x][find_y][find_z].gone_forward = true;
			bool is_deadend = false;
			return true;
		}
		if(findPath(find_x,find_y,find_z-1) && Maze[find_x][find_y][find_z+1].visited != true && Maze[find_x][find_y][find_z].gone_backward == false)
		{
			Maze[find_x][find_y][find_z].gone_backward = true;
			bool is_deadend = false;
			return true;
		}
		if(is_deadend)
		{
			cout << " dead end " << pathstack.top() << endl;
			Maze[find_x][find_y][find_z].visited = true;
			pathstack.pop();
			return false;
		}




	}

When I run the code i get stuck going back and forth after I hit a certain wall, the code returns then when it tries again it gets stuck. The general idea I have is to check right as far as i can, then return and check the other options, if those are exhausted I'll move back one and try all options (depth search).

Code:

working on0 0 0
pushing(0, 0, 0)
working on1 0 0
pushing(1, 0, 0)
working on2 0 0
is a wall
working on2 1 0
is a wall
working on2 1 1
is a wall
working on2 0 1
pushing(2, 0, 1)
working on3 0 1
pushing(3, 0, 1)
working on4 0 1
pushing(4, 0, 1)
working on5 0 1
out of bounds
working on5 1 1
out of bounds
working on5 1 2
out of bounds
working on5 0 2
out of bounds
working on5 0 1
out of bounds
working on4 0 1

then it just keeps looping :/

The 3d vector it is working on is:

Code:

I'm thinking I'm probably over-complicating this, but any input on either a more simple algorithm, or pointers on where I've gone wrong, or why this is happening would be greatly appreciated.

I hope you all have a wonderful day!
-MJ

millgates · 11-05-2013, 04:28 AM

Hi, your code is hard to follow.
This seems strange to me:

Code:

working on0 0 0
pushing(0, 0, 0)
working on1 0 0
pushing(1, 0, 0)
working on2 0 0
is a wall
working on2 1 0
is a wall
working on2 1 1
is a wall
working on2 0 1
pushing(2, 0, 1)

How come you get from (1, 0, 0) to (2, 0, 1)?

I have a few suggestions, though:

Code:

find_x = x;
find_y = y;
find_z = z;

I would definitely use an array/vector (a class with an overloaded + operator would be nice, too) for coordinates. Also, i would make an enum for directions

Code:

enum direction {
    right    = 0,
    forward  = 1,
    up       = 2,
    left     = 3,
    backward = 4,
    down     = 5,
};

also, this way, the direction oposite to dir will be (dir + 3) % 6.

Then I would define steps in these directions, so that step[right] is {1, 0, 0} and so on.
That would allow me to get rid of those 6 ugly if() statements in your code and replace it with a single loop over all directions.

Then the logic would be simple: for each room in the maze, remember whether or not you already visited it and where you came from (direction). loop over all adjacent rooms until you find one you haven't visited yet and move there. If all adjacent rooms have been visited already, go back to the previous room you came from. Repeat until you get either to the finish, or to the starting room and there are no unvisited adjacent rooms, in which case there is no solution.

suicidaleggroll · 11-05-2013, 01:17 PM

Recursive functions can solve mazes pretty cleanly. It won't necessarily give you the ideal solution, but it will give you a solution. The logic goes something like:

Code:

function recfunc(x,y,z)

if (haveIBeenHere(x,y,z)) return(0)
if (didIHitAWall(x,y,z)) return(0)
if (amIAtTheEnd(x,y,z)) return(1)

haveIBeenHere(x,y,z)=1

for(ii=-1;ii<=1;ii+=2){
   for(jj=-1;jj<=1;jj+=2){
      for(kk=-1;kk<=1;kk+=2){
          if (recfunc(x+ii,y+jj,z+kk)) then return(1)
      }
   }
}

return(0)

or if you only want to move in the cardinal directions:

Code:

function recfunc(x,y,z)

if (haveIBeenHere(x,y,z)) return(0)
if (didIHitAWall(x,y,z)) return(0)
if (amIAtTheEnd(x,y,z)) return(1)

haveIBeenHere(x,y,z)=1

for(ii=-1;ii<=1;ii+=2){
   if (recfunc(x,   y,   z+kk)) then return(1)
   if (recfunc(x,   y+jj,z))    then return(1)
   if (recfunc(x+ii,y,   z))    then return(1)
}

return(0)

The function will recursively call itself and walk through the maze, ignoring cells it's checked before, and walking backwards through function calls when it hits a dead end or the end of the maze. You would just want to set up an array to record the x,y,z locations when recfunc returns a 1, which will be the path backwards through the maze when you're finally back at the original function call.

mitchell7man · 11-06-2013, 10:49 PM

Thanks for both of you input, I think I have a working solver, yet I'm getting a segmentation fault when I do find the end of the maze.
My code at present:

Code:

bool PathFinder :: findPath(int x, int y, int z)
{
	cout << "*****findpath called"<< endl;
	find_x = x;
	find_y = y;
	find_z = z;
	string insert_x, insert_y, insert_z;
	ostringstream stream_x, stream_y , stream_z;
	stream_x << find_x;
	stream_y << find_y;
	stream_z << find_z;
	insert_x = stream_x.str();
	insert_y = stream_y.str();
	insert_z = stream_z.str();
	cout << "working on" << insert_x << " " << insert_y << " " << insert_z << endl;
	cout << "checking if end" << endl;
	if(find_x == 4 && find_y == 4 && find_z == 4 && (Maze[find_x][find_y][find_z].cube_value == 1))
	{
		Maze[find_x][find_y][find_z].visited = true;
		cout << "is finish" << endl;
		return true;
	}
	cout << "checking to see if its in bounds" << endl;
	if(find_x < 0 || find_y < 0 || find_z < 0 || find_x > 4 || find_y > 4 || find_z > 4)
	{
		cout << "out of bounds" << endl;
		return false;
	}
	cout << "checking for wall" << endl;
	if(Maze[find_x][find_y][find_z].cube_value != 1 && Maze[find_x][find_y][find_z].visited != true)
	{
		// then it is a wall
		cout << "is a wall" << endl;
		Maze[find_x][find_y][find_z].visited = true;
		return false;
	}
	cout << "checking if visited" << endl;
	if(Maze[find_x][find_y][find_z].visited == true)
	{
		// then it I have been here
		cout << "I have been here" << endl;
		Maze[find_x][find_y][find_z].visited = true;
		return false;
	}
	else
	{
		cout << "operarting on valid cube" << endl;

		string to_push = "(" + insert_x + ", " + insert_y + ", " + insert_z + ")";
		cout << "          pushing" << to_push << endl;
		pathstack.push(to_push);
		Maze[find_x][find_y][find_z].visited = true;



			if(findPath(find_x+1,find_y,find_z) && Maze[find_x+1][find_y][find_z].visited != true)
			{
				return true;
			}else
			if(findPath(find_x-1,find_y,find_z) && Maze[find_x-1][find_y][find_z].visited != true)
			{
				return true;
			}else
			if(findPath(find_x,find_y + 1,find_z) && Maze[find_x][find_y+1][find_z].visited != true)
			{
					return true;
			}else
			if(findPath(find_x,find_y-1,find_z) && Maze[find_x][find_y-1][find_z].visited != true)
			{
				return true;
			}else
			if(findPath(find_x,find_y,find_z + 1) && Maze[find_x][find_y][find_z + 1].visited != true)
			{
					return true;
			}else
			if(findPath(find_x,find_y,find_z-1) && Maze[find_x][find_y][find_z-1].visited != true)
			{
				return true;
			}else
			{
				cout << "removing ------------->" << pathstack.top() << endl;
				pathstack.pop();
				return false;
			}
	}

note I have cout all over for debugging, I put one before I call basically any variable, and when I run the code, I do get a valid path (i've walked through an entire maze) but I get this at the end in the terminal:

Quote:

pushing(1, 4, 4)
*****findpath called
working on2 4 4
checking if end
checking to see if its in bounds
checking for wall
checking if visited
operarting on valid cube
pushing(2, 4, 4)
*****findpath called
working on3 4 4
checking if end
checking to see if its in bounds
checking for wall
checking if visited
operarting on valid cube
pushing(3, 4, 4)
*****findpath called
working on4 4 4
checking if end
is finish
Run_Test_Driver.sh: line 14: 21690 Segmentation fault (core dumped) ./$EXE
Press any key to exit...

As you can see in my code, the last thing it does is return true; I really cant figure out why I'm getting seg-fault. Does anyone have an Idea where this is coming from?

Thank you for your input, it has been very helpful!
-MJ

pan64 · 11-07-2013, 01:52 AM

valgrind will tell you (hopefully)

suicidaleggroll · 11-07-2013, 09:09 AM

What's with all of the checks if you've visited the cell? You only need one right at the start of the function, toss all the others. It looks like you're driving yourself into a corner here. What happens when it hits the finish?

Code:

Maze[find_x][find_y][find_z].visited = true;
cout << "is finish" << endl;
return true

Then it backs out to whoever called it, which is inside an if statement:

Code:

if(findPath(find_x+1,find_y,find_z) && Maze[find_x+1][find_y][find_z].visited != true)
{
   return true;
}else

The findPath will be true, but so will the Maze.visited since you just set it in findPath. Since you're checking if Maze.visited != true, that if statement will always fail. In fact, every time findPath gets called, the associated index in Maze gets set to true, so that if statement will always fail. You should revisit your logic.

You're also pushing your indices in the wrong spot. Who cares if you're visiting a cell, you only want to know if the cell you're in is on the right track to solving the maze. You need to push the indices as your recursion unwinds with "return true", and the result will be a stack of indices in reverse order to solve the maze (starting with the end, and going back to the start). Otherwise your stack is going to be FULL of dead end paths with incoherent jumps back to previous cells, etc. Please re-read post #3, it was all described there. And maybe remove the stack push and pop until you know the underlying logic is working correctly.

mitchell7man · 11-14-2013, 12:07 AM

Thank you so much, I realized that I wasn't checking all up down left right forward and back, so I added the missing components as well as fixed the issue with the if statements and it works pretty well. Cheers.