## Nyaato

Hello guys, I'm new here, and this is my first post in this forums. Please bear with me if I can't explain what I'm in need of well.

Basically, this is part of my assignment, and I'm supposed to find a path from one end to the other in a maze.

The maze is pre-defined in a text file, and I've got to load it up onto the program. After loading the maze, I'll need to use a function to find the correct pathing and print out the pathing on the maze itself.

I'm a beginner in C++, so I'm kind of stuck at a particular problem.

The problem I'm facing is that, the way I use to search for the path is wrong. I've got no idea how to search for the correct path using a correct method.

A copy of the maze is attached in the file below, because posting here would be rather weird, as the whole maze is gonna look out of shape.

So far, this is my code:

``````#include <iostream>
#include <fstream>
#include <string>
using namespace std;

char gameArray[8][16];
int startX = 0;
int startY = 0;
bool positionCheck = false;

// Reminder:
// i = y-axis direction
// j = x-axis direction

void findPath(void)
{
for (int i = 0; i<8; i++)
{
for (int j = 0; j <16; j++)
{
if (gameArray[i][j] == 'M')
{
if (positionCheck == false)
{
startX = j;
startY = i;
positionCheck = true;
cout << "Mouse is at: " << i << " " << j << endl;
}
}
}
}
// moving in north
if (gameArray[startY-1][startX] == ' ' ) // checking -1 of the y axis for a space. Can be increased to check more spaces at the front.
{
cout << "Replacing path!" << endl;
gameArray[startY-1][startX] = '+'; // if the space is available, change the space to a + sign.
startY--;
findPath(); // recurs to that it'll recheck
}
// moving in south
else if (gameArray[startY+1][startX] == ' ') // same as north
{
cout << "Replacing path!" << endl;
gameArray[startY+1][startX] = '+';
startY++;
findPath();
}
// moving in west
else if (gameArray[startY][startX-1] == ' ')
{
cout << "Replacing path!" << endl;
gameArray[startY][startX-1] = '+';
startX--;
findPath();
}
else if (gameArray[startY][startX+1] == ' ')
{
cout << "Replacing path!" << endl;
gameArray[startY][startX+1] = '+';
startX++;
findPath();
}
}

char inputStandard(void)
{
ifstream myfile ("standard.txt");

if (myfile.is_open())
{
for (int i = 0; i<8; i++)
{
for (int j = 0; j < 16; j++)
{
myfile.get(gameArray[i][j]);
}
}
myfile.close();
}
return 0;
}

char inputCustom(void)
{
ifstream myfile ("custom.txt");

if (myfile.is_open())
{
for (int i = 0; i<8; i++)
{
for (int j = 0; j < 16; j++)
{
myfile.get(gameArray[i][j]);
}
}
myfile.close();
}
return 0;
}

void main(void)
{
string status_mode = "NONE";
int choice;
for (int start_loop = 1; start_loop>0; start_loop++)
{
if (status_mode != "NONE")
{
for (int indexrow=0; indexrow<8; indexrow++)
{
for (int indexcol=0; indexcol<16;indexcol++)
{
cout <<  gameArray[indexrow][indexcol];
}
}
cout << endl;
}
cout << "Active Maze: " << status_mode << endl;
cout << "1. Select Standard Maze" << endl;
cout << "2. Select Custom Maze" << endl;
cout << "3. Find Path" << endl;
cout << "4. Print Path" << endl;
cout << "5. End " << endl;

cin >> choice;

if (choice == 1)
{
status_mode = "STANDARD";
inputStandard();
cout << "Standard Mode Selected!" << endl << endl;
}
if (choice == 2)
{
status_mode = "CUSTOM";
inputCustom();
cout << "Custom Mode Selected!" << endl << endl;
}
if (choice == 3)
{
findPath();
}
if (choice == 4)
{
cout << "DISABLED. " << endl << endl;
}
if (choice == 5)
{
cout << "EXITING!" << endl;
break;
}
if (!cin)
{
cout << "ERROR IN INPUT!" << endl;
}
}
}``````

How the final product I'm required to do this somewhat like this...

[IMG]http://notcliche.com/example.PNG[/IMG]

Any help with regards to a pathing method would be greatly appreciated, and thanks in advance!

## VernonDozier 2,218

This is actually harder because the maze itself has a lot of extra white space so there is not a unique solution. It will be easier in some ways to program for a maze where all the paths are only one character wide. Best foolproof algorithm is to always keep a wall on your right. When you bump into an obstacle, always turn right, which keeps the wall on your right. You should change the value of the grid where you can walk to a different value to mark what spots you have already travelled. When you are forced to backtrack, mark that direction as a direction that you know is a wrong turn. When given an option, always go somewhere you haven't yet gone. This method will work here too even though the maze has extra white space. Draw it on paper first before tackling the programming part. You need to really understand the algorithm before implementing it.

## Lerner 582

First, it's int main() not void main(). Your compiler may let you use void, but it's not a wise idea to do so, and it's even one keystroke less to type int rather than void.

Second main() usually has two arguments. You can type them in, or leave the parenthesis blank, but I'm not sure using void as a parameter is going to work.

Third, do you know about structs and stacks? They are used in some of the implementations for solving mazes as they can be helpful in setting up the protocols vernon dozier talks about, like keeping tack of whether you've been to a given square or cell of the maze or not and backtracking when the path you have been following becomes blocked.

## Nyaato

Alright, noted and changed my void main() to int main(). Thanks for the advice!

I've use structs before, but not stacks. Haven't learned of that as of yet.

I'm still trying to figure out how to backtrack, as of what VernonDozier had suggested, but I'm not getting far at the moment...

If it's not too much, could I get an example of how it's like? Thanks again!

## VernonDozier 2,218

Alright, noted and changed my void main() to int main(). Thanks for the advice!

I've use structs before, but not stacks. Haven't learned of that as of yet.

I'm still trying to figure out how to backtrack, as of what VernonDozier had suggested, but I'm not getting far at the moment...

If it's not too much, could I get an example of how it's like? Thanks again!

Here is a maze.

``````*******
***
*     *
* *****
*     *
*******

Here is the correct path.

*******
oo***oo
*ooooo*
* *****
*     *
*******

Here is the attempt where you keep the wall to your right.

*******
oo***
*o    *
*o*****
*oooo@*
*******

Oops, I hit a wall with a dead end.  I have nowhere else to go, so I backtrack (i.e. go where I went before).  I know that any spot where I've gone before and where I have no blank spaces and no option to switch directions is a dead end.  Mark that dead end with an x so I don't go over it again.

*******
oo***
*o    *
*o*****
*ooo@x*
*******

*******
oo***
*o    *
*o*****
*oo@xx*
*******

and so on till I get to a spot where I have a new option.

*******
oo***
*@    *
*x*****
*xxxxx*
*******

I'm back where I was before.  Go right again.

*******
oo***
*o@   *
*x*****
*xxxxx*
*******

Keep going.

*******
oo***oo
*ooooo*
*x*****
*xxxxx*
*******``````

Solved! Blank space is where I haven't been. o is where I've been that may possibly be the route, x is where I've been that is definitely not the route, @ is where I am now. When you reach a dead end, turn around and leave x's in your trail until you have an option to go right again. Never go down a path with an x.

This is a trivial example, but hopefully it'll help. Again, draw it out on paper first till you get a better understanding. Don't skip any steps till you really understand it.

## Nyaato

Okay, so far so good. I understood what you've suggested to me. However, I'm still in a pinch.

I got this whole chunk of code done up, and the backtracking works to a certain extend. I know something is wrong with my backtracking, but I've got no idea how to fix it.

``````void findPath(void)
{
for (int i = 0; i<8; i++)
{
for (int j = 0; j <16; j++)
{
if (gameArray[i][j] == 'M')
{
if (positionCheck == false)
{
startX = j;
startY = i;
positionCheck = true;
cout << "Mouse is at: " << i << " " << j << endl;
}
}
}
}
// moving in north
if (gameArray[startY-1][startX] == ' ')
{
cout << "Replacing path!" << endl;
gameArray[startY-1][startX] = '+';
startY--;
findPath();
}
// moving in east
else if (gameArray[startY][startX+1] == ' ')
{
cout << "Replacing path!" << endl;
gameArray[startY][startX+1] = '+';
startX++;
findPath();
}
// backtracking
else if (gameArray[startY][startX] == '+')
{
cout << "Backtracking" << endl;
gameArray[startY][startX] = 'X';
if (moveEast == false)
{
startX--;
}
else if (moveNorth == false)
{
startY++;
}
findPath();
}
// checking for max north
else if (gameArray[startY-1][startX] == '*' && moveNorth == true)
{
moveNorth = false;
cout << "Max for north reached!" << endl;
gameArray[startY][startX] = 'X';
startY++;
findPath();
}
// checking for max east
else if (gameArray[startY][startX+1] == '*' && moveEast == true)
{
moveEast = false;
cout << "Max for east reached!" << endl;
gameArray[startY][startX] = 'X';
startX--;
findPath();
}
}``````

The code above is the whole findPath function. There is something wrong with the backtracking area, but I've got no idea how to fix it.

A screenshot of the problem is displayed in the attachment. Please advise!

## VernonDozier 2,218

I don't even see a solution to that maze unless you are allowed to move diagonally. I strongly suggest you not allow that if you don't need to as it complicated things significantly from a programming standpoint. Develop a more compact maze. You shouldn't have any paths that are wider than your character. As mentioned, the "keep the wall to the right" method will also solve these "wide path" problems too, but you'll do better to design a maze like I did, where there is a solution without going diagonally and where all the paths are just one unit wide.

We have no way to run your code. In something like this, the problem could easily be anywhere. We don't know what the variables have been initialized to before this function is called. Just looking at what you have, though, I seriously doubt you want the nested for-loop. You probably want a while loop. You need some way to see whether the maze is solved, at which point exit the while loop. You have no idea how many steps it is going to take, so a for-loop doesn't seem like the right approach. You need to post the entire program for anyone to be able to run it. If it is the same program as what you originally posted, you need to say so. We can't assume that.

## Nyaato

As much as I would like to change the maze, it's not really possible for me to do that, as the maze stated in standard.txt is what I need solve.

I'll paste the whole code here again. I've fixed some of the error I've found, and it should, more or less work properly now, however, there are still some errors around.

I'll work on changing the for loop into while loop, as you've suggested, and it seems quite true, since I've got no idea how many steps I would need to finish the whole maze.

Anyway... here's the whole code. I know it's kind of messy... but bear with me. Thanks again.

``````#include <iostream>
#include <fstream>
#include <string>
using namespace std;

char gameArray[8][16];
int startX = 0;
int startY = 0;
bool moveNorth = true; // checks if it is able to move north
bool moveEast = true; // checks if it's able to move east
bool positionCheck = false; // used to check if Mouse's (M) position is located

void findPath(void)
{
for (int i = 0; i<8; i++)
{
for (int j = 0; j <16; j++)
{
if (gameArray[i][j] == 'M')
{
if (positionCheck == false)
{
startX = j;
startY = i;
positionCheck = true;
cout << "Mouse is at: " << i << " " << j << endl;
}
}
}
}
// moving in north
if (gameArray[startY-1][startX] == ' ')
{
moveEast = false;
cout << "Replacing path!" << endl;
gameArray[startY-1][startX] = '+';
startY--;
findPath();
}
// moves in the east direction
if (gameArray[startY][startX+1] == ' ')
{
moveNorth = false;
cout << "Replacing path!" << endl;
gameArray[startY][startX+1] = '+';
startX++;
findPath();
}
// moves in the west direction
if (gameArray[startY][startX-1] == ' ')
{
moveEast = false;
moveNorth = false;
cout << "Replacing path!" << endl;
gameArray[startY][startX-1] = '+';
startX--;
findPath();
}
// backtracking
else if (gameArray[startY][startX] == '+')
{
if (moveNorth == false)
{
// backtracking in north direction
cout << "Back tracking!" << endl;
gameArray[startY][startX] = 'X';
startX--;
}
else if (moveEast == false)
{
// backtracking in east direction
cout << "Back tracking!" << endl;
gameArray[startY][startX] = 'X';
startY++;
}
}
// check if north reaches a dead end
else if (gameArray[startY-1][startX] == '*' && moveNorth == true)
{
cout << "Max for north reached!" << endl;
gameArray[startY][startX] = 'X';
startY++;
findPath();
}
// checks if east reaches a dead end
else if (gameArray[startY][startX] == '+' && moveEast == true)
{
cout << "Backtracking" << endl;
gameArray[startY][startX] = 'X';
startY++;
findPath();
}

}

char inputStandard(void)
{
ifstream myfile ("standard.txt");

if (myfile.is_open())
{
for (int i = 0; i<8; i++)
{
for (int j = 0; j < 16; j++)
{
myfile.get(gameArray[i][j]);
}
}
myfile.close();
}
return 0;
}

char inputCustom(void)
{
ifstream myfile ("custom.txt");

if (myfile.is_open())
{
for (int i = 0; i<8; i++)
{
for (int j = 0; j < 16; j++)
{
myfile.get(gameArray[i][j]);
}
}
myfile.close();
}
return 0;
}

void main(void)
{
string status_mode = "NONE";
int choice;
for (int start_loop = 1; start_loop>0; start_loop++)
{
if (status_mode != "NONE")
{
for (int indexrow=0; indexrow<8; indexrow++)
{
for (int indexcol=0; indexcol<16;indexcol++)
{
cout <<  gameArray[indexrow][indexcol];
}
}
cout << endl;
}
cout << "Active Maze: " << status_mode << endl;
cout << "1. Select Standard Maze" << endl;
cout << "2. Select Custom Maze" << endl;
cout << "3. Find Path" << endl;
cout << "4. Print Path" << endl;
cout << "5. End " << endl;

cin >> choice;

if (choice == 1)
{
status_mode = "STANDARD";
inputStandard();
cout << "Standard Mode Selected!" << endl << endl;
}
if (choice == 2)
{
status_mode = "CUSTOM";
inputCustom();
cout << "Custom Mode Selected!" << endl << endl;
}
if (choice == 3)
{
cout << "DISABLED." << endl << endl;
findPath();
}
if (choice == 4)
{
cout << "DISABLED. " << endl << endl;
}
if (choice == 5)
{
cout << "EXITING!" << endl;
break;
}
if (!cin)
{
cout << "ERROR IN INPUT!" << endl;
}
}
}``````

## VernonDozier 2,218

You need to provide the original input file too. It is unfortunate that you are stuck with that maze because you now have to design code that can move and check in eight directions rather than four. Also, how do you know where to start and stop? There are no holes in the side of the maze and nothing in your code that reads from the input file that tells you where to start, plus how do you know when you are done? Is there an 'S' and 'F' in the input file or something? You can't start at (0,0) because that's a wall/asterisk.

``````void main(void)
{
string status_mode = "NONE";
int choice;
for (int start_loop = 1; start_loop>0; start_loop++)
{
if (status_mode != "NONE")
{
for (int indexrow=0; indexrow<8; indexrow++)
{
for (int indexcol=0; indexcol<16;indexcol++)
{
cout <<  gameArray[indexrow][indexcol];
}
}
cout << endl;
}
cout << "Active Maze: " << status_mode << endl;
cout << "1. Select Standard Maze" << endl;
cout << "2. Select Custom Maze" << endl;
cout << "3. Find Path" << endl;
cout << "4. Print Path" << endl;
cout << "5. End " << endl;

cin >> choice;

if (choice == 1)
{
status_mode = "STANDARD";
inputStandard();
cout << "Standard Mode Selected!" << endl << endl;
}
if (choice == 2)
{
status_mode = "CUSTOM";
inputCustom();
cout << "Custom Mode Selected!" << endl << endl;
}
if (choice == 3)
{
cout << "DISABLED." << endl << endl;
findPath();
}
if (choice == 4)
{
cout << "DISABLED. " << endl << endl;
}
if (choice == 5)
{
cout << "EXITING!" << endl;
break;
}
if (!cin)
{
cout << "ERROR IN INPUT!" << endl;
}
}
}``````

It is `int main ()` , not `void main ()` , even if your compiler lets you get away with it. You have what appears to be an infinite loop. See red code above. If that is intentional, you should probably change it to a `while (true)` loop so it's more obvious that it is intentional.

## VernonDozier 2,218

I just took another look at the original standard.txt. It's attached earlier in the thread. No diagonal moves are required. I'm not sure what you did on your post, but it looks like you did a diagonal move or something. There is a 'C' and an 'M' in there too. You need to say what those represent.

## Nyaato

Ah yes. I'm sorry for leaving out these information.

Basically, this is a "game" of the mouse and cheese. The mouse is represented with M, which is the starting point of the maze itself. C is the cheese, which is the ending point of the maze.

Thus, the objective of the whole program is to reach from M to C!

The highlighted text from main function:

``````for (int start_loop = 1; start_loop>0; start_loop++)
{
if (status_mode != "NONE")
{
for (int indexrow=0; indexrow<8; indexrow++)
{
for (int indexcol=0; indexcol<16;indexcol++)
{
cout <<  gameArray[indexrow][indexcol];
}
}
cout << endl;
}``````

The red highlighted text is the "infinite loop", which will keep prompting the user for an action after a particular action has been performed. I'm really sorry if I've confused you...

The for loop in the main function is just to show the maze, it has no relation in the pathfinding/insert the maze into array.

Once again, I'm sorry if I didn't provide sufficient information.

Here's the results I've gotten so far...

[IMG]http://i37.tinypic.com/2rpblzm.jpg[/IMG]

## VernonDozier 2,218

For debugging purposes, you need to display each iteration of your maze solving function to see what's happening. Take your display code and make a function out of it.

``````void Display ()
{
for (int indexrow=0; indexrow<8; indexrow++)
{
for (int indexcol=0; indexcol<16;indexcol++)
{
cout <<  gameArray[indexrow][indexcol];
}
}
cout << endl;
}``````

At the top of the findPath () function, add these two lines:

``````Display ();
cin.get ();``````

`cin.get ()` pauses. Press the enter key to see the next iteration. It will give you a much better feel for what is going on step by step. These two lines are debugging code, so you need to remember to eventually take them out.

## Lerner 582

Backtracking can be made more efficient if you can keep track of where you've been. As I said in my earlier post a stack is commonly used but you could use an array or list almost as readily. Since you are already using an array for the maze I assume you are reasonably familiar with their use. So, I'd declare a one dimensional array of type struct called path or solution or whatever with the same number of total objects as in the maze. I'd als declare an int to keep track of how many cells of the maze you actually have in the path. As you go to each new cell of the maze add it to the end of the array. When you can't go any further with a given cell then you can effectively remove that cell from the path by decreasing the value of the variable keeping track of the number of cells actually in the path at the same time you place the '+' in the cell of the maze that is the dead end. Then it's a simple task print out the path when you find a solution to the maze.

You will probably need to do bounds check sooner or later, too. That means if the Mouse is in the top row it can't go up (South?) any further, if it's in the far right row it go right (East) any further, etc.

Next moves can be checked in same order every time----North, East, South, West, etc. Valid next moves for the Mouse would be elements of the maze that have values C or space. First valid move found in that sequence put 0 in current cell, move m (the actual mouse, which is separate from M which is the starting position of the Mouse) in the next valid move cell and repeat. If the move puts the Mouse out of bounds and if the next element of the maze is *, +, 0, or M then that move is invalid. If no valid move is found after looking in all four directions, then put a + in the current cell and decrease the length of the current path by one and put m in that cell and retry. If the length of the path ever gets to minus one (or zero or other value meaning it is empty) then there is no solution.

The process stops when there is a solution or the path is empty.

If there is a solution then print it out.