Algorithm for traversing a conditional maze Imagine a maze where there are rooms and doors. You can only go one way through a door. Some doors are locked. Certain rooms contain keys to certain doors. In effect, each time you find a key, the maze changes.
In the image below, the open doors are shown as outlines, the locked doors are shown filled in grey. The arrows show the directions you can go. Keys are shown as sectors (like the movement of a door opening). The pale blue door from room D to room C does not exist.

Room B contains the key for room D, room D contains the key to room E, and room E contains the key to room F. It is possible to reach room D by following the path A>B>C>A>D. You can therefore get the key to room E.
However, if the blue door does not exist, you now have no way to get back to room A to open the door to room E. Because you cannot reach room E, you cannot get the key to open the door to room F, so you cannot reach room F either.
In this case, it is clear that you can never reach rooms E and F, unless a new door is created.
My problem is: imagine any maze, of any level of complexity. Is there an algorithm that will show whether it is possible to reach every room?
Assuming an external view of the maze, it is easy to find whether:


*

*There is an open door to any given room

*There is a key, somewhere, for any given door


The main problems are:


*

*Can you get to the key for every door?

*When you have the key for a given door, can you get to that door?

*If a room cannot be reached, what is the smallest change that could be made to resolve this?

 A: With finite doors and keys, it is possible to enumerate all paths.
Traverse the graph breadth first tracking which nodes have been visited. Upon entering a room with a key, compute the transitive closure of that node with the new door unlocked. Add each member of the transitive closure as an edge to the current node (following this edge should add the necessary in-transit rooms to the visited list), and visit only the nodes on this list that have not been visited previously. The algorithm will always halt.
Using the set of all sets of visited nodes you can answer the following:


*

*Can you get to the key for every door? Is there a set in the collected data that contains all the nodes that contain keys?

*When you have the key for a given door, can you get to that door? Is there a set in the collected data that contains both the node with that key and the node from the door that key unlocks?

*If a room cannot be reached, what is the smallest change that could be made to resolve this? You could add an edge from the start to this room, and technically we are done. 


If you really mean to determine the smallest change that allows the entire maze to be traversed, you could try every possible addition of one edge, then every possible addition of two edges, then every possible addition of three edges, etc, until you have a complete graph. Somewhere along the way the maze will have every node visitable.
