Stacks, Queues, and a Maze??

[orangejuice2005]

We were given a task, to familiarize ourselves with stacks and queues, to write a program to solve a maze problem. We are given text files with pre-defined values letting us know the size of the maze, the mouse's position, the cheese's position as well as the value each cell carries.

I attached some extra info for a more clear understanding of this assignment.

What am trying to do....where i got some questions is.....ok so the input file is read and each cell contains an interger value that gets translated into its binary notation where starting from the left, each bit represents N E S W (North, east, south and west). How do i have it recognize where there are 1's and 0's ( 1 signifies a pathway within the room, 0...a c omplete wall) within the binary number. She provided us with the below header file....my questions is the "&" symbol does what? doorEncoding(which is the value of the cell) & 0x08...what does that mean? am thinking it compares the number's 1 positions after the symbol to the cell value?

Maze.h

typedef struct 
{ 
    unsigned short int doorEncoding; // Range 0..15. 
         north = doorEncoding & 0x08   // 8 = 1000 ( north position has 1)
         east  = doorEncoding & 0x04  // 4 = 0100 ( east position has 1)
         south = doorEncoding & 0x02
         west  = doorEncoding & 0x01
           
    bool      visited; 
    int         parentRow; 
    int         parentCol; 
    char      direction; // From parent. 


} MazeCell;

Maze.cpp

// Read and initialize all the cells. 
	int x = 0; 
	while(txtfile >> x)  
	{	
		for (int i = 0; i < rows; i++)
		{
			for (int j = 0; j < cols; j++)
			{
				maze[i][j].doorEncoding = x;
			}
		}
	}

Thank you, and am srry for the troubles once again.

[mitrmkar]

Very shortly about the & operator, it is the bitwise and operator.
See e.g. here http://www.learncpp.com/cpp-tutorial/38-bitwise-operators/ for details.

[orangejuice2005]

Hey thank you for the link, it really explained a lot.

[orangejuice2005]

Am having troubles coming up with an implementation that would solve a maze. Am trying to picture how am going to have it the mouse examine the room to see which doors are available and determine the neighboring cells and determine if its been visited before and it it hasn't move to that direction then place the cell into the stack. This is obviously going to be done by a loop but i don't know how to go about starting it. What i got so far:

cpp

void MazeCell::doorEncoding(unsigned short int x)
{
      /* Cells are maped by chars.
      1st bit maps West door
      2nd bit maps south  door
      3rd bit maps east door
      4th bit maps North  door*/
	
	//The 4 directions (North, South, East and West)
	enum {west, south, east, north};

	//find the state of a door (state of door will be given by "x & 0x08")
	 int north = x & 0x08;
	 int east = x & 0x04;
	 int south = x & 0x02;
	 int west = x & 0x01;
}

void Maze::Solve() //need help
{ 
	CellPosition c; 
	stack<CellPosition> cpos; 
	c.row = mouseRow; 
	c.col = mouseCol; 
	cpos.push(c); 

	maze[mouseRow][mouseCol].parentRow = -1;
	maze[mouseRow][mouseCol].parentCol = -1;
	
	bool visited = false;
	while(!cpos.empty())
	{
		while(maze[mouseRow][mouseCol] != maze[cheeseRow][cheeseCol])
		{
			if()


			visited = true;
		}
	}
	cout << "Maze has no solution" << endl;
}

I would have the mouse move through each cell and with each iteration of the loop, take the cell and mark it as visited and push it into a stack. If it is the cheese cell, then stop the loop stops. If not, we continue picking a side with a doorway to the next cell position and continue doing this till it finds the cheese.

visited -- 1 ==> the cell has been visited. 0 => not visited.
parent -- parent (i.e. previous cell) if the cell has been visited.
For the first cell (mouse's initial position) there is no parent.
Hence the -1 values
direction -- The direction (i.e. the letter) from parent to this cell.

Attaching what i have so far if any1 wants to see the grand scheme of things.

[kjc367]

One method to solve a maze is to consider the walls more as a door that is open (available) or closed (already tried). Boundaries are marks closed as are the solid walls.

the sequence would be:
1) Enter cell
2) If this cell contains cheese, stop -- maze solved
3) If you've been here before (i.e. visited), pop off the stack (i.e. return to the previous cell and repeat step 5)
4) Mark as visited
5) If the door to the North, East, West, or South is open, mark it as closed (i.e. now a wall) and move to that new cell. (i.e. push cell and move to next cell)
6) All paths checked, no solution

Using just a byte and using the upper nibble to mark used/closed doors:

existing
bit 0: Door to West
bit 1: Door to South
bit 2: Door to East
bit 3: Door to North

new
bit 4: Door to West Used
bit 5: Door to South Used
bit 6: Door to East Used
bit 7: Door to North Used

Using this approach, you can see that if any of the upper nibble is set, then this cell has been visited. To use a door, you check that it is present (bits 0-3) and unused (bits 4-7). If you're working on minimal space used, then you could even "mark" the cheese with a special code such as 0x00 (no doors, none used).

This also works well for a recursive calling. You could argue that the recursive is using a stack, it just happens to be the system stack.

[Lerner]

Here's a slightly different algorirhm.

Given:

1) a fixed maze with:
  a) defined room for mouse to start and 
  b) defined room for placement of cheese 
and
2) each room has:
  a) a flag for being visited, and
  b) 4 sides which may either be a wall or a door, and
  c) a variable to keep track of next side to look at 
     (side numbers range from 1-4, with side number set to 1 on construction),

then one approach using iterative style might be something like this:

//special case
 designate that mouse starting room has been visited 
 push mouse starting room on stack

//general case
while stack not empty and maze not solved
  current room will be top of stack
  //check for solution
  if current room same as cheese room
     maze solved
  else if current room side number is 5 //means no more neighbors to look in
    pop current room from stack  //go back to a prior room  
  else //look for new room
     while(current room side number is less than 5 and need new room) 
       if this side is a door
         new room is selected based on what side this is
         current room side number is incremented by 1
         if new room not visited 
            need new room is false 
            new room marked as visited
            push new room on stack      
       else
         current room side number is incremented by 1

Warning: it's been a while since I've done maze solving programs so logic not infallible.

[orangejuice2005]

Thank you kjc367 and Lerner, the responses i've gotton from both of you as made the process of coming with a solution method clear but am having a hard time translating that to code....i've tried something but i don't think its right.

void Maze::Solve() //need help
{ 
	The 4 sides (North, South, East and West)
	 enum {w, s, e, n};

	CellPosition c; 
	stack<CellPosition> cpos; 
	maze[mouseRow][mouseCol].visited = true;
	maze[mouseRow][mouseCol].parentRow = -1;
	maze[mouseRow][mouseCol].parentCol = -1;
	c.row = mouseRow; 
	c.col = mouseCol; 
	cpos.push(c); 

	
	bool visited = false;
	while(!cpos.empty())
	{
	//check for solution
	while(maze[mouseRow][mouseCol] != maze[cheeseRow][cheeseCol])
	{
	if(maze[mouseRow][mouseCol] == maze[cheeseRow][cheeseCol])
	{
	   c.row = mouseRow;
	   c.col = mouseCol;
	   cpos.push(c);
	   visited = true;
	   cout<< "Maze has been solved!!" << endl;
	   break;
	}
	else if (north == 8)  // does this say north = binary value(1000)?
	{
	  maze[mouseRow][mouseCol] = maze[i][j-1];
	  maze[mouseRow][mouseCol].direction = n;
	  maze[i][j-1].parentRow = maze[i];
	  maze[i][j-1].parentCol = maze[j+1];
	  c.row = mouseRow;
	  c.col = mouseCol;
	  cpos.push(c);
	if(north != 8 && east == 6)
	{
		maze[mouseRow][mouseCol] = maze[i+1][j];
		maze[mouseRow][mouseCol].direction = e;
		maze[i+1][j].parentRow = maze[i-1];
		maze[i+1][j].parentCol = maze[j];
		c.row = mouseRow;
		c.col = mouseCol;
		cpos.push(c);
	}
	if(north != 8 && east != 4 && south == 2)
	{
		maze[mouseRow][mouseCol] = maze[i][j+1];
		maze[mouseRow][mouseCol].direction = s;
		maze[i][j+1].parentRow = maze[i];
		maze[i][j+1].parentCol = maze[j-1];
		c.row = mouseRow;
		c.col = mouseCol;
		cpos.push(c);
	}
	if(north != 8 && east != 4 && south != 2 && west == 1)
	{
		maze[mouseRow][mouseCol] = maze[i-1][j];
		maze[mouseRow][mouseCol].direction = w;
		maze[i-1][j].parentRow = maze[i+1];
		maze[i-1][j].parentCol = maze[j];
		c.row = mouseRow;
		c.col = mouseCol;
		cpos.push(c);
	}
	}
	maze[mouseRow][mouseCol].visited = true;
		
  if (north !=8 && east !=4 && south !=2 && west !=1)
   {
     // go back to parent cell and choose other available direction
     maze[mouseRow][mouseCol]=
   }
}
}
	cout << "Maze has no solution" << endl;
}

[Lerner]

I find it useful to separate the bitwise manipulations from
the algorithym as much as I can since bitwise manipulation
always confuses me.

I see no need for "parent" information, as the stack and
the visited variable will keep track of where you've been.

Likewise, direction is an unnecessary confounding variable,
in my opinion.

This is a first draft and not a compiled, tried and true version
of how I would implement the pseudocode from my first post.
There is undoubtedly one or more syntactic or logic error that
you will find, but it gives you an idea of how to go from
pseudocode to code.

class Cell
{
  public:
   int rowNumber;
   int colNumber;
   bool doors[4]; //true == door, false == wall
   bool visited;  //set to false in constructor
   int sideNumber; //range 0-3, set to zero in constructor
   bool operator == //useful, but not necessary
   etc
};

void Maze::initialize()
{
  read data from file to establish:
  1) mouse starting position
  2) cheese location
  3) Cells in the maze
  4) values for sides of all Cells in maze      
}

void Maze::Solve() 
{		 
  Cell * newRoom; 
  stack<Cell> path;
 
  bool solutionNeeded = true;
  bool needNewRoom;
 
  maze[mouseStartRow][mouseStartCol].visited = true;
  path.push(maze[mouseStartRow][mouseStartCol]);
 
  while(!path.empty() && solutionNeeded)
  {
    //mouse is path.top();
  
    if(path.top() == cheeseLocation)
      solutionNeeded = false;
    else if(path.top().sideNumber == 4) //dead end
      path.pop(); //go back to prior room.
    else
    {
      needNewRoom = true;
      while(path.top().sideNumber < 4 && needNewRoom)
      {
        if(path.top().doors[path.top().sideNumber]) //if this side is a door
        {
          switch(path.top().sideNumber)
          {
            case 0: //west side of current cell is a door, so move 1 col to left
              newRoom = &maze[path.top().rowNumber][path.top().colNumber - 1];
              break;
            //etc
          }
          path.top().sideNumber++;
          if(!newRoom->visited)
          {
            needNewRoom = false;
            newRoom->visited = true;
            path.push(*newRoom);
          }
        }
        else
          path.top().sideNumber++;
      }
    }
  }
  if(solutionNeeded)
    cout << "no solution" << endl;
}