I have an assingment in which i have to right an algorithim to get through a maze. I dont know where to really start with it. I know in the instructions it said to write it as though we used our right hand as a guide. in other words we walk through the maze with our right hand on the wall. if there is no wall we turn where the wall turns.in the end we will have traveled the whole maze but eventually get out. any help would be greatly appreciated.
thanks!!:)

i need help writing an algorithim to get through a maze. i have a rough idea on where to start but am not
entirely sure on the concept. i do know we have to write it as though we are using our right hand as a guide
hand. in other words we put our right hand on the wall. as we walk we use our right hand as a guide hand. if
we feel no wall we turn folling our right hand along the wall. we eventuall will get out of the maze. it is a slow
process but that is the way the assingment is. any help would be greatly appreciated. thanks!! =)

just do what your teacher said then man ;). Assuming your maze is an integer array of zeros and ones then just have your program keep moving "forward" in a sense that forward is constantly changing, and assuming zero is walkable and one is a wall, check whether or not the block to the right of you is a one. If the block isn't a one, change forward to that direction and your app will move in that direction now, because it is forward ;).

ie: (very tiny map for example hehe)

int map[5] = {
    {1,1,1,1,1},
    {1,0,0,0,2},
    {1,0,1,1,1},
    {1,0,0,0,1},
    {1,1,1,1,1},
};

//...
std::string direction;
int x = 3; //x is 'y' because the array coordinates are backwards ;)
int y = 3 //as y is 'x'

//...

if (direction == "left")
{
    if (map[y - 1][x] == 0)
        direction = "up";
}

//... 

    return 0;
}

that only provides for left but i think you can figure the rest out right? pm me if you still don't get it. And are you sure your teacher doesn't want you to use the pathfinding algorithm?

Edited 3 Years Ago by Dani: Formatting fixed

i have something like this so far. our group came up with this but im not sure if its whats supposed to be. thanks

void mazeWalk(char** &maze, int xCoord, int yCoord, int direction)
{
    
    printMaze(maze);
    maze[xCoord][yCoord]='x';
    if(yCoord==11)
    {
        cout<<"Maze has been successfully solved!  :)";
        return;
    }
    if(yCoord==0)
    {
        maze[xCoord][yCoord]='x';
        cout<<"Begin MAZE!!!";
        //return;
    }

    int count=0;
    for(int move=direction; count <4;(move++)%4, count ++)
    { 
            
            if( direction==RIGHT)
            {
                if(move==RIGHT)
                {
                    if (maze[xCoord][yCoord+1]== '.' ||maze[xCoord][yCoord+1]== 'x')
                        mazeWalk(maze,xCoord, yCoord+1,RIGHT);
                }
                else if (move==DOWN)
                {
                    if(maze[xCoord-1][yCoord]== '.' ||maze[xCoord-1][yCoord]== 'x')
                    mazeWalk(maze, xCoord-1,yCoord, RIGHT);
                }
                else if (move==LEFT)
                {
                    if (yCoord!=1)
                
                    if(maze[xCoord][yCoord-1]== '.' ||maze[xCoord][yCoord-1]== 'x')
                    mazeWalk(maze, xCoord,yCoord-1, RIGHT);
                }
                else if (move==UP)
                {
                    if(maze[xCoord+1][yCoord]== '.' ||maze[xCoord+1][yCoord]== 'x')
            
                    mazeWalk(maze, xCoord+1,yCoord, RIGHT);
                }
            }




            else if( direction==DOWN)
            {
                if(move==RIGHT)
                {
                    if (maze[xCoord][yCoord+1]== '.' ||maze[xCoord][yCoord+1]== 'x')
                        mazeWalk(maze,xCoord, yCoord+1,RIGHT);
                }
                else if (move==DOWN)
                {
                    if(maze[xCoord-1][yCoord]== '.' ||maze[xCoord-1][yCoord]== 'x')
                    mazeWalk(maze, xCoord-1,yCoord, RIGHT);
                }
                else if (move==LEFT)
                {
                    if (yCoord!=1)
                
                    if(maze[xCoord][yCoord-1]== '.' ||maze[xCoord][yCoord-1]== 'x')
                    mazeWalk(maze, xCoord,yCoord-1, RIGHT);
                }
                else if (move==UP)
                {
                    if(maze[xCoord+1][yCoord]== '.' ||maze[xCoord+1][yCoord]== 'x')
            
                    mazeWalk(maze, xCoord+1,yCoord, RIGHT);
                }
            }

            else if( direction==LEFT)
            {
                if(move==RIGHT)
                {
                    if (maze[xCoord][yCoord+1]== '.' ||maze[xCoord][yCoord+1]== 'x')
                        mazeWalk(maze,xCoord, yCoord+1,RIGHT);
                }
                else if (move==DOWN)
                {
                    if(maze[xCoord-1][yCoord]== '.' ||maze[xCoord-1][yCoord]== 'x')
                    mazeWalk(maze, xCoord-1,yCoord, RIGHT);
                }
                else if (move==LEFT)
                {
                    if (yCoord!=1)
                
                    if(maze[xCoord][yCoord-1]== '.' ||maze[xCoord][yCoord-1]== 'x')
                    mazeWalk(maze, xCoord,yCoord-1, RIGHT);
                }
                else if (move==UP)
                {
                    if(maze[xCoord+1][yCoord]== '.' ||maze[xCoord+1][yCoord]== 'x')
            
                    mazeWalk(maze, xCoord+1,yCoord, RIGHT);
                }
            }

             else if( direction==UP)
            {
                if(move==RIGHT)
                {
                    if (maze[xCoord][yCoord+1]== '.' ||maze[xCoord][yCoord+1]== 'x')
                        mazeWalk(maze,xCoord, yCoord+1,RIGHT);
                }
                else if (move==DOWN)
                {
                    if(maze[xCoord-1][yCoord]== '.' ||maze[xCoord-1][yCoord]== 'x')
                    mazeWalk(maze, xCoord-1,yCoord, RIGHT);
                }
                else if (move==LEFT)
                {
                    if (yCoord!=1)
                
                    if(maze[xCoord][yCoord-1]== '.' ||maze[xCoord][yCoord-1]== 'x')
                    mazeWalk(maze, xCoord,yCoord-1, RIGHT);
                }
                else if (move==UP)
                {
                    if(maze[xCoord+1][yCoord]== '.' ||maze[xCoord+1][yCoord]== 'x')
            
                    mazeWalk(maze, xCoord+1,yCoord, RIGHT);
                }
            }

        }
}

Correction!
This is the code we got. Were confident it works but can anyone help us as to why it does not begin. we were just supposed to write the algorithim to get through the maze but the rest was given to us by the teacer. why does it not work? we do not understand what it means by "the solution will be printed in the output file" how do we set that up? sorry if the answer is simple. were just stressed and cant seem to get it at the moment. any help would begreatly appreciatied. thanks

#include <iostream>
#include <string>
#include <fstream>

#define DOWN 0 
#define RIGHT 1 
#define UP 2 
#define LEFT 3 

using namespace std;

void initMaze(char** &);
void mazeWalk(char** &, int, int, int);
void printMaze (char** &);
int Rows, Columns;
int XSTART, YSTART;
ifstream		indata;
ofstream                outdata;

int main (int argc, char* argv[])
{
	if ( argc != 3 )
        {
                cerr << "The program should take two arguments, \nthe names of the input and output files!" <<endl;
                cerr << "The input file is a plain text file with a maze; the solution will be printed in the output file" <<endl;
                return 0;
        }

	indata.open(argv[1]);
	outdata.open(argv[2]);

	char **maze;
	initMaze(maze);
	mazeWalk(maze, XSTART, YSTART, RIGHT);
	printMaze(maze);
	for (int i=0; i<Rows; i++)
		delete maze[i];
	delete maze;
	indata.close();
	outdata.close();
	return 0;
}

void initMaze(char** &maze)
{
	Rows = 12;
	Columns = 12;
	maze = new char*[Rows];
	for (int i=0; i<Rows; i++)
		maze[i] = new char[Columns];
	for (int i=0; i<Rows; i++)
		for (int j=0; j<Columns; j++)
			indata >> maze[i][j];
	indata >> XSTART >> YSTART;
	return;
}

void mazeWalk(char** &maze, int xCoord, int yCoord, int direction)
{
    
    printMaze(maze);
    maze[xCoord][yCoord]='x';
    if(yCoord==11)
    {
        cout<<"Maze has been successfully solved!!";
        return;
    }
    if(yCoord==0)
    {
        maze[xCoord][yCoord]='x';
        cout<<"Begin MAZE!!!";
        //return;
    }

    int count=0;
    for(int move=direction; count <4;(move++)%4, count ++)
    { 
            
            if( direction==RIGHT)
            {
                if(move==RIGHT)
                {
                    if (maze[xCoord][yCoord+1]== '.' ||maze[xCoord][yCoord+1]== 'x')
                        mazeWalk(maze,xCoord, yCoord+1,RIGHT);
                }
                else if (move==DOWN)
                {
                    if(maze[xCoord-1][yCoord]== '.' ||maze[xCoord-1][yCoord]== 'x')
                    mazeWalk(maze, xCoord-1,yCoord, RIGHT);
                }
                else if (move==LEFT)
                {
                    if (yCoord!=1)
                
                    if(maze[xCoord][yCoord-1]== '.' ||maze[xCoord][yCoord-1]== 'x')
                    mazeWalk(maze, xCoord,yCoord-1, RIGHT);
                }
                else if (move==UP)
                {
                    if(maze[xCoord+1][yCoord]== '.' ||maze[xCoord+1][yCoord]== 'x')
            
                    mazeWalk(maze, xCoord+1,yCoord, RIGHT);
                }
            }




            else if( direction==DOWN)
            {
                if(move==RIGHT)
                {
                    if (maze[xCoord][yCoord+1]== '.' ||maze[xCoord][yCoord+1]== 'x')
                        mazeWalk(maze,xCoord, yCoord+1,RIGHT);
                }
                else if (move==DOWN)
                {
                    if(maze[xCoord-1][yCoord]== '.' ||maze[xCoord-1][yCoord]== 'x')
                    mazeWalk(maze, xCoord-1,yCoord, RIGHT);
                }
                else if (move==LEFT)
                {
                    if (yCoord!=1)
                
                    if(maze[xCoord][yCoord-1]== '.' ||maze[xCoord][yCoord-1]== 'x')
                    mazeWalk(maze, xCoord,yCoord-1, RIGHT);
                }
                else if (move==UP)
                {
                    if(maze[xCoord+1][yCoord]== '.' ||maze[xCoord+1][yCoord]== 'x')
            
                    mazeWalk(maze, xCoord+1,yCoord, RIGHT);
                }
            }

            else if( direction==LEFT)
            {
                if(move==RIGHT)
                {
                    if (maze[xCoord][yCoord+1]== '.' ||maze[xCoord][yCoord+1]== 'x')
                        mazeWalk(maze,xCoord, yCoord+1,RIGHT);
                }
                else if (move==DOWN)
                {
                    if(maze[xCoord-1][yCoord]== '.' ||maze[xCoord-1][yCoord]== 'x')
                    mazeWalk(maze, xCoord-1,yCoord, RIGHT);
                }
                else if (move==LEFT)
                {
                    if (yCoord!=1)
                
                    if(maze[xCoord][yCoord-1]== '.' ||maze[xCoord][yCoord-1]== 'x')
                    mazeWalk(maze, xCoord,yCoord-1, RIGHT);
                }
                else if (move==UP)
                {
                    if(maze[xCoord+1][yCoord]== '.' ||maze[xCoord+1][yCoord]== 'x')
            
                    mazeWalk(maze, xCoord+1,yCoord, RIGHT);
                }
            }

             else if( direction==UP)
            {
                if(move==RIGHT)
                {
                    if (maze[xCoord][yCoord+1]== '.' ||maze[xCoord][yCoord+1]== 'x')
                        mazeWalk(maze,xCoord, yCoord+1,RIGHT);
                }
                else if (move==DOWN)
                {
                    if(maze[xCoord-1][yCoord]== '.' ||maze[xCoord-1][yCoord]== 'x')
                    mazeWalk(maze, xCoord-1,yCoord, RIGHT);
                }
                else if (move==LEFT)
                {
                    if (yCoord!=1)
                
                    if(maze[xCoord][yCoord-1]== '.' ||maze[xCoord][yCoord-1]== 'x')
                    mazeWalk(maze, xCoord,yCoord-1, RIGHT);
                }
                else if (move==UP)
                {
                    if(maze[xCoord+1][yCoord]== '.' ||maze[xCoord+1][yCoord]== 'x')
            
                    mazeWalk(maze, xCoord+1,yCoord, RIGHT);
                }
            }

        }
}


	//WRITE THE DEFINITION OF YOUR FUNCTION HERE





void printMaze (char** &maze)
{
	outdata << "---" <<endl;
	for (int i=0; i<Rows; i++)
	{
		for ( int j=0; j<Columns; j++)
			outdata << maze[i][j];
		outdata << endl;
	}
	outdata << "---" <<endl;
	return;
}
This article has been dead for over six months. Start a new discussion instead.