My project requires I use the right-hand method of solving a maze. I have to use a stack to keep track of and eventually print out the path to the exit. I know the way I am trying to keep track of each point is wrong because using mazeArray[xCoord][yCoord] is only going to give me the values at that position in the 2d array. So I feel like I need to use a struct that contains a x position and y position, and maybe instead of using another ADT I could use a bool within each struct to mark if the position was visited or not. I guess I am having a brain fart on how to implement said struct within my project. Any help would be greatly appreciated. Below is all code I have written.

#ifndef MAZE_H
#define MAZE_H

#include <iostream>
#include <fstream>
#include <stack>
#include <queue>
using namespace std;

enum dir {E,S,W,N};
#define MAZE_SIZE 12

class Maze
{

private:
	int xCoord;
	int yCoord;
	int direction;
	bool visited;
	bool exitFound;
	char mazeArray[MAZE_SIZE][MAZE_SIZE];
	char currentPos;
	stack<char> path;
	stack<char> visited;
	queue<char> choices;
	
public:
	Maze();
	void solveMaze();
	void turnRight();
	void turnLeft();
	void explore();
	void printMaze();
	void printPath();
	};

#endif 
#include "maze.h"


Maze::Maze()
{
	exitFound = false;
	direction = E;
	//read file variable
	ifstream loadFile;

	//Open maze txt file
	loadFile.open("maze.txt");	

	//check to see if the file was opened
	if(loadFile.is_open()){

		//A loop that created the maze
		for (int x = 0; x < 12; x++){
			for(int y = 0; y < 12; y++){
				if ((y == 0 || y == 11)||(x == 0 || x == 11))
					mazeArray[x][y] = '1';
				//replace 0 with integers from txt
				else
					loadFile >> mazeArray[x][y];		
			}
		}
		//closing the text file
		loadFile.close(); 
	}
	else{
		cout << "File not found\n";
            }
	cout << "Please select your starting location\n"
		<< "x-coordinate: ";
	cin >> xCoord;
	cout << "y-coordinate: ";
	cin >> yCoord;
	currentPos = mazeArray[xCoord][yCoord];
	path.push(currentPos);
	visited.push(currentPos);
}


void Maze::explore()
{

	if(direction == E){
		//Examining North
		if(mazeArray[xCoord][yCoord-1] = '0')
			path.push(mazeArray[xCoord][yCoord-1]);
		//Examining East
		if(mazeArray[xCoord+1][yCoord] = '0')
			path.push(mazeArray[xCoord+1][yCoord]);
		//Examining South
		if(mazeArray[xCoord][yCoord+1] = '0')
			path.push(mazeArray[xCoord][yCoord+1]);	
	}

	else if(direction == S){
		//Examining East
		if(mazeArray[xCoord+1][yCoord] = '0')
			path.push(mazeArray[xCoord+1][yCoord]);
		//Examining South
		if(mazeArray[xCoord][yCoord+1] = '0')
			path.push(mazeArray[xCoord][yCoord+1]);
		//Examining West	
		if(mazeArray[xCoord-1][yCoord] = '0')
			path.push(mazeArray[xCoord-1][yCoord]);
		//if right hand rule carries you forward
		//yCoord = (yCoord + 1);
	}	

	else if(direction == W){
		//Examining South
		if(mazeArray[xCoord][yCoord+1] = '0')
			path.pursh(mazeArray[xCoord][yCoord+1]);
		//Examining West	
		if(mazeArray[xCoord-1][yCoord] = '0')
			path.push(mazeArray[xCoord-1][yCoord]);
		//Examining North
		if(mazeArray[xCoord][yCoord-1] = '0')
			path.push(mazeArray[xCoord][yCoord-1]);
	}

	else if(direction == N){
		//Examining West	
		if(mazeArray[xCoord-1][yCoord] = '0')
			path.push(mazeArray[xCoord-1][yCoord]);
		//Examining North
		if(mazeArray[xCoord][yCoord-1] = '0')
			path.push(mazeArray[xCoord][yCoord-1]);
		//Examining East
		if(mazeArray[xCoord+1][yCoord] = '0')
			path.push(mazeArray[xCoord+1][yCoord]);
		//Traveling East
		if (mazeArray[xCoord+1][yCoord]='0'){
			xCoord+=1;
			currentPos = mazeArray[xCoord][yCoord];
			visited.push(currentPos);
			direction=E;
			explore();
		}
		//Continuing North
		else if(mazeArray[xCoord][yCoord-1]=='0'){
			yCoord-=1;
			currentPos=mazeArray[xCoord][yCoord];
			visited.push(currentPos);
			direction=N;
			explore();
		}
		//Travelling West
		else if(mazeArray[xCoord-1][yCoord]=='0'){
			xCoord-=1;
			currentPos = mazeArray[xCoord][yCoord];
			visited.push(currentPos);
			direction==W;
			explore();
		}
		//If have to go back the way came
		//This definately does not work
		else{
			//loop through visited stack until empty
			for(visited.top(); visited.empty(); visited.pop())
				path.pop();
		}
	}
}


void Maze::printMaze()
{
	for (int j = 0; j < 12; j++) {
		for (int i = 0; i < 12; i++) {
			cout << mazeArray[i][j];	
		}
		cout << endl;
	}	
}

void Maze::printPath()
{

}

If you want to keep track of the visited coordinates, you will need to keep a 2D array of a map for flagging. Mark each position once you have visited that spot. Please bear in mind that you may still need to revisit a coordinate in order to find the way out. Since this is a maze, by disallowing a spot to be revisited may cause your bot to get stuck. Good luck!

Yes, I definatly need the capability to revisit spots inorder to back track. I am confused by what you mean keeping a 2d array to flag visited. I have a 2d array for the maze itself. Do you mean I need to keep another one for something else? Let me give my basic pseudocode and see if that helps to explain what I am trying to achieve.

EDIT: I do not want the code done for me or anything. Some guidance on the types of ADT's to use and some pointers on things you see I am doing wrong is what I am requesting. Thanks to all that can help.

Create a border of walls around maze
create maze from textfile
get start position from user
check if the position is on the exit or trapped
push start position to stack
while not on exit and not trapped
mark as visited
check surrounds for floor//floor meaning able to travel that path
push surrounds with floor
if floor to right
turn to face that direction
move there
else if no floor to immediate right turn counterclockwise and check to your right again
else only floor is way I came
pop stack until i reach an unvisited//not sure of the ADT to keep visited in, this is the //backtracking portion
loop back to checking surrounds of non visited

Edited 7 Years Ago by Afupi: n/a

A stack sounds like a good idea and your explanation is rational. To make it a little easier to understand start with a simpler maze.

Consider a simple maze that has just 3 cells in the shape of an L with the start at the top of the L and the exit at the other end of the L with a single cell in between. The start has just a single opening, the bottom. The middle box has two openings, the top and the right hand wall. The exit has 1 opening, the left hand wall. To run the maze you do something like this:

push start cell on stack
mark start as visited
check right---wall
check top---wall
check left----wall
check bottom---open to middle cell
if middle cell is not the exit
push middle cell on stack
mark middle cell as visited
check right---open to exit
push exit cell on stack
stop.
The stack now contains a path from start to exit

Now add a fourth cell to the above L, completing a 2x2 maze. The fourth cell, in the upper right hand corner, is open on left but nowhere else. The sequence could go like this:

push start on stack
mark start as visited
check start right---open to fourth cell
  if fourth cell has been visited 
    don't go there now
  else if fourth cell is exit
    push fourth cell on stack
    stop
  else
    mark fourth cell as visited
    check right---wall
    check top---wall
    check left---open, 
      if the next cell on left is visited already
        don't go there now
    check bottom---wall
    all options for fourth cell have failed so pop fourth cell from stack and  continue checking next cell back--which is start
   check start right---open
     if visited already
      don't go there now
   check start top---wall
   check start left---wall
   check start bottom---open to middle cell
etc.

Now you can probably extend the analagy to your more generalized scenario.

Thank you for the assistance. I am going to give this a try and will repost.

This article has been dead for over six months. Start a new discussion instead.