How to guarantee that all open nodes are traversable

Question

In a project, I'm currently using A* for finding paths. I first put down my agent. Then I place all of the blockers on any nodes that are free. The agent needs to be able to get to any open node. However, the following situation can happen:

A = Agent
B = Node that's blocked
X = An open node that's impossible to reach

[A] [ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [ ]
[B] [B] [ ] [ ] [ ]
[X] [B] [ ] [ ] [ ]

Here are the questions that could be answered in order to avoid this situation (answering either one could solve this problem):

1. How can I detect that there is no path to X and then fix it in the best possible way (or at least an acceptable way that won't require calling A* to every node, then randomly picking a different node to put one of the blockers on until finally all of the nodes are traversable)?
2. When placing blockers, how can I ensure that they won't make any open node be impossible to reach?

One way I can think of is to place all the blockers. Then I could check their neighbors to see if any neighbor nodes are open and can be traversed to by calling A* to them. That's at least a little bit better than the way I explained a possible solution in question 1.

Answer 1

There are several ways to generate mazes. The simplest one is a randomized depth-first search(starting from the start cell and visiting unvisited neighbors in random order until the exit is reached. All unvisited cells are considered to be walls). It has all the required properties(the exit is always reachable due to its termination condition, all open cells are reachable from the start cell because it always generates exactly one connected component). You can read more about it(and a few other maze generation algorithms) here: http://en.m.wikipedia.org/wiki/Maze_generation_algorithm.