Stack for backtracking maze

Question

For the algorithm DFS for maze-generation:

1) Is the stack value supposed to change once I push the stack in whenever there is a path to go?

For example as below 5x5 Maze:

0, 0, 0, 0, 0

0, 1, 0, 0, S

0, 1, 1, 1, 1

0, D, 0, 0, 0 

0, 0, 0, 0, 0

Let's say from source I move down one step (CurrentCell)

The stack will push in coordinates (5,2) (Current Source Location)

Then when I reaches (5,3), the currentCell will become the Source. (5,3)

Am i correct?

So when the source moves to the next left path, the stack will push in the current coordinate, which is (5,3) so on and so for until it reaches a dead end instead of the destination.

So as per above example:

The stack will first push in value of

Stack(0) (5,2) Stack(1) (5,3)

. . . .

The question is, how am i supposed to push in the x and y? Because the current problem is, even if I push in the x and y, the x and y stays at the original value instead of constantly updating. That's the reason why my backtrack is not working, I guess.

Code:

(random == 3) //To check for bottom neighbor
                        {
                            if (y+ 2 < column) //In case the column overshots
                            {

                                {
                                    maze[x][y+ 1].setValue(1); //New Path Set as 1
                                    myStack.push(maze[x][y]);
                                    y= y+ 1;
                                    }
                               }
                           }

TechNewb TechNewb · Accepted Answer · 2015-03-15T03:14:47

turns out I am correct.

                maze[x][y] = myStack.top();
                myStack.pop();
                cout << "Array X is : " << maze[x][y].getX();
                cout << "Array Y is : " << maze[x][y].getY();

All i need is to pop and check whether is the route I took backtracks back. Thanks all for the help!

Stack for backtracking maze

1 Answers