Algorithm to check if all maze walls are connected

Question

I am building a maze game and am searching for an algorithm that returns true if it finds a wall or segment of walls in a maze that are not connected to the rest of the walls in the maze (ie an island of walls). The maze solving algorithm that I am using to test if the mazes being generated by users are solvable is the "right hand rule" (my algorithm is similar to the ones discussed here and here), but it has a potential to fail if one or more walls are not connected to every other wall.

My maze is being stored in a 2D array of 1 and 0 integers representing the the present/not-present state of each wall.

Does anyone know of the least expensive way to calculate whether or not a maze (saved in the format mentioned above) has any walls that are totally disconnected from the rest of the walls?

Code, pseudo code, or a plain english conditional outline would be much appreciated. I plan on translating it to javascript if anyone is looking for a language for examples.

Thanks!

Answer 1

Flood-fill all the connected walls from some starting wall. You can do this either by setting the walls to some other value (e.g. 2) or having another 2D array just for this.

Run through the maze again. If you find any wall that hasn't been filled in the above step, we know it's not connected to the rest.

But it might also make sense (perhaps more sense) to make this part of your solving algorithm by just marking the cells you've already visited as visited and not revisiting already visited cells (again using another value or another array, as above). If you do this, it doesn't really matter whether or not the walls aren't connected.

Answer 2

One way to do it is to pick a random wall and add it to an empty list. Then:

while the list isn't empty:
    take an item from the list
    mark the item as visited
    put all of its unvisited neighbors on the list

When the list is empty, either every wall will have been visited, or you have at least two distinct "islands" of walls.