Tidying Up the Stack-Based Search
Let’s clean up the stack-based search so that we only push valid, unvisited cells onto the stack. Before we push a neighbor, we check that it is inside the maze, is not a wall, and has not already been visited. We also mark each cell as visited as soon as we push it, not when we pop it. If we waited until the pop, two different cells could push the same neighbor before it is popped, and the stack would hold that neighbor twice.
Here is how it goes on the same maze:
0 1 2 3
┌───┬───┬───┬───┐
0 │ S │ │ │ │
├───┼───┼───┼───┤
1 │ │ █ │ █ │ │
├───┼───┼───┼───┤
2 │ █ │ █ │ █ │ E │
└───┴───┴───┴───┘
We begin by pushing the start cell and marking it as visited. The start is the one cell that does not go through the neighbor check, so we check it before pushing it: if the start is a wall, there is no path, and we return false right away.
0 1 2 3 0 1 2 3
┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐
0 │ S │ │ │ │ 0 │ x │ │ │ │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤
1 │ │ █ │ █ │ │ 1 │ │ │ │ │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤
2 │ █ │ █ │ █ │ E │ 2 │ │ │ │ │
└───┴───┴───┴───┘ └───┴───┴───┴───┘
maze visited
┌────────┐
top ──▶ │ (0, 0) │
└────────┘
Now we pop (0, 0) and ask if it is the exit. It is not. So we go through its neighbors and push the valid, unvisited ones.
- Going up, is
(-1, 0)valid and unvisited? No, it is outside the maze. - Going left, is
(0, -1)valid and unvisited? No, it is outside the maze. - Going down, is
(1, 0)valid and unvisited? Yes. Push it onto the stack and mark it as visited. - Going right, is
(0, 1)valid and unvisited? Yes. Push it onto the stack and mark it as visited.
0 1 2 3 0 1 2 3
┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐
0 │[S]│ │ │ │ 0 │ x │ x │ │ │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤
1 │ │ █ │ █ │ │ 1 │ x │ │ │ │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤
2 │ █ │ █ │ █ │ E │ 2 │ │ │ │ │
└───┴───┴───┴───┘ └───┴───┴───┴───┘
maze visited
┌────────┐
top ──▶ │ (0, 1) │
├────────┤
│ (1, 0) │
└────────┘
Next, we pop the top element, (0, 1), and ask if it is the exit. It is not. So we go through its neighbors and push the valid, unvisited ones.
- Going up, is
(-1, 1)valid and unvisited? No, it is outside the maze. - Going left, is
(0, 0)valid and unvisited? No, it is already visited. - Going down, is
(1, 1)valid and unvisited? No, it is a wall. - Going right, is
(0, 2)valid and unvisited? Yes. Push it onto the stack and mark it as visited.
0 1 2 3 0 1 2 3
┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐
0 │ S │[ ]│ │ │ 0 │ x │ x │ x │ │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤
1 │ │ █ │ █ │ │ 1 │ x │ │ │ │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤
2 │ █ │ █ │ █ │ E │ 2 │ │ │ │ │
└───┴───┴───┴───┘ └───┴───┴───┴───┘
maze visited
┌────────┐
top ──▶ │ (0, 2) │
├────────┤
│ (1, 0) │
└────────┘
Notice that the stack now holds only two cells. Each one is an open cell inside the maze, and no cell appears twice. At the same point in the previous section, the stack held seven cells.
This tidied-up version is the form of the stack-based search you will often see in textbooks and online. It is not an exact copy of the recursive search, though. Because we mark a cell as visited when we push it, a cell can be marked long before the search pops it. If another cell later checks it as a neighbor, the search skips it. So on some mazes, this version visits the cells in a different order than the recursive search does. It still finds a path whenever one exists.
Since the visiting order no longer matches the recursion anyway, there is no reason to push the neighbors in reverse. From here on, we push them in the order right, down, left, up, which is how most textbooks write it. The search then pops them in the order up, left, down, right.