Finding a Maze Path using Recursion

[ball3r]

Hi guys,

Firstly, a quick thank you to whoever put this site up, wealth of advice and everyone here sounds helpful.

I'm quite new to C++ and programming in general so go easy on me.

I'm trying to find a way through a maze from a given start point through to the goal. The maze (saved in a text file) is of this form:

10
x x x x x x x x x x
x x x x p x x p g x
x p p p p x p p x x
x x x p p x p p p x
x p p p x x x x p x
x x x p p p p p p x
x p p p x x x x x x
x x x p x x x p p x
x x x p p p p p x x
x x x x x x x x x x

where the 10 specifies the size of the maze(So in this case 10by10)
x - represent a wall
p - represents a path
and
g - represents the goal

Here is my code so far (I know this is not the most efficient or clever way...)

#include <iostream>
#include <fstream>
#include <string>
#define FALSE 0
#define TRUE 1

using namespace std;
/*Tasks
*/
void printMaze(char maze[100][100],int mazeSize)
{
    for(int i = 0; i < mazeSize; i++)//printing the maze
		{
			for(int j = 0; j < mazeSize;j++)
			{
				cout << maze[i][j] << " ";
				if(j==(mazeSize-1)){cout << "\n";}//checks that we have printed 10 lines so far, then prints the next line.
			}
	
		}
}
int findPath(char maze[100][100], int row, int col)
{
//THIS ALL DOESN'T DO MUCH, BUT I NEED SOME HELP HERE PLEASE
	if(maze[row][col]=='g')
	{
		cout << "\n\nGoal reached at coordinates: (" << row << "," << col << ")\n";
		return 0;
	}
    

	/*if( maze[row][col] == 'p') 
	{
		maze[row][col]='f';

		findPath(maze,row, col+1);
		findPath(maze,row, col-1);
		findPath(maze,row-1, col);
		findPath(maze,row+1, col);
	}*/

}

int main(int argc, char *argv[])
{
	ifstream mazeFile; //The file read object 
	string line; 
	char size[5]; //to store the dimension of our array
	char maze[100][100];//to store the maze
	if(argc == 4)
	{
	mazeFile.open(argv[1]);//Open our file from the command line argument

		int c1 = atoi(argv[2]); //First coordinate from the third command line argument
		int c2 = atoi(argv[3]); //Second coordinate from the fourth command line argument

		cout << "Start coordinates are (" << c1 << "," << c2 << ")" << endl ;//Feedback to user displaying 
		//start coordinates
	}
	else
	{
		cout << "Error: Arguments Incorrect\n";
		return 0;
    };

	if (mazeFile.is_open()) //Check if file has opened succesfully
	{
		
		mazeFile >> size;//Gets the first line of the file(dimensions of the maze)
		cout << "Maze dimensions are " << size << " by " << size << endl;
		cout << "\nThe maze:\nx - is wall, p - is path & g - is goal\n\n" ;
		int mazeSize = atoi(size);//convert out maze size from char to int to use it in the display
		
		
		while (!mazeFile.eof())//while not having reached the end of file
		{
			for(int n=0; n<mazeSize; n++)// col. number
			{
					for(int m=0; m<mazeSize; m++)// rows number
				{
					mazeFile >> maze[n][m];//places mazes into the 2d array

				}
			}
			
		}

		mazeFile.close();

	}
	else
	{
		cout << "Unable to open file.\n"; 
		return 0;
	};
		int mazeSize = atoi(size);//convert out maze size from char to int to use it in the display
		
		
		printMaze(maze,mazeSize);//Prints the maze
	
		int c1 = atoi(argv[2]); //First coordinate from the third command line argument
		int c2 = atoi(argv[3]); //Second coordinate from the fourth command line argument

	if(maze[c1][c2] == 'x')
		{
			cout << "\nError: Start coordinate is 'x'\n";
		}
		else
		{
			findPath(maze,c1,c2);
		};
		
}

The program is run with command line arguments, e.g. maze.exe maze.txt 1 1
where maze.exe is the compiled program, maze.txt is where the maze is saved(same directory as maze.exe) 1 and 1 are the start coordinates(must be a p)

I'm basically in need of some help to try and and figure out a way to go through the maze to find g(goal).
By using recursion.

Hope you I was clear, and that you guys can help.

Thank you

[mrnutty]

For your print maze do this instead,

void printMaze(char maze[100][100],int mazeSize)
{
    for(int i = 0; i < mazeSize; i++)//printing the maze
		{
			for(int j = 0; j < mazeSize;j++)			
				cout << maze[i][j] << " ";			
                   cout << endl;
		}
}

As for your problem, where does the player start from ? I don't see
a way to get in the maze from outside, so I figure there is a starting
point.

[tux4life]

By simply using Google I found these nice links:

• http://www.cs.bu.edu/teaching/alg/maze/
• http://www.dreamincode.net/forums/showtopic94248.htm

[CppBuilder2006]

I think there must be a start position too!
if I was to write such a program. i'd begin with a function like this:

bool areAdjacentPartOfPath(POINT p1, POINT p2)
{
       if(CharAt(p1) != p || CharAt(p2) != p)
               return false;
       if(  |p1.x - p2.x| + |p1.y - p2.y| == 1)
              return true;
       return false;
}

this is sth like a psuedo- code! just giving an idea!:)

[WaltP]

As for your problem, where does the player start from ? I don't see
a way to get in the maze from outside, so I figure there is a starting point.

I think there must be a start position too!

Ummm, guys, read the post:

The program is run with command line arguments, e.g. maze.exe maze.txt 1 1
where maze.exe is the compiled program, [doh!!!]
maze.txt is where the maze is saved(same directory as maze.exe)
1 and 1 are the start coordinates(must be a p)