Need help in finding correct method for my program!
 

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...

http://notcliche.com/example.PNG

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

Re: Need help in finding correct method for my program!
 

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.

Re: Need help in finding correct method for my program!
 

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.

Re: Need help in finding correct method for my program!
 

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!

Re: Need help in finding correct method for my program!
 

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.

Re: Need help in finding correct method for my program!
 

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!

Re: Need help in finding correct method for my program!
 

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.

Re: Need help in finding correct method for my program!
 

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;

                }

        }

}

Re: Need help in finding correct method for my program!
 

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.

Re: Need help in finding correct method for my program!
 

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.