I'm working on a maze generation algorithm. My algorithm selects from predefined tiles and creates a maze. Here is an example produced by my code. '**' is a wall and '__' is empty floor space.
** ** ** ** ** ** ** ** ** ** **
** __ __ __ ** ** __ ** ** ** **
** ** __ __ __ __ __ ** ** ** **
** ** __ __ __ __ __ ** ** ** **
** __ __ __ ** __ ** ** ** ** **
** __ __ __ ** __ ** ** ** ** **
** __ __ ** ** __ ** ** ** ** **
** __ __ __ ** ** ** __ __ __ **
** __ ** __ ** ** ** __ __ ** **
** __ __ __ ** ** ** __ ** ** **
** ** ** ** ** ** ** ** ** ** **
I need to create a function that will test to see if all floor space is connected. i.e. make sure that all '__' spaces can be reached from every other '__' space. That would mean the above maze is illegal but the below is acceptable.
** ** ** ** ** ** ** ** ** ** **
** ** __ ** __ __ __ __ __ __ **
** __ __ __ __ __ __ __ __ __ **
** ** __ ** __ __ ** ** __ ** **
** __ __ __ ** ** ** __ __ __ **
** __ __ ** ** ** ** __ __ __ **
** __ __ __ ** ** ** __ __ __ **
** ** ** __ ** ** ** ** ** ** **
** __ __ __ __ __ __ ** ** ** **
** __ __ __ ** ** ** ** ** ** **
** ** ** ** ** ** ** ** ** ** **
I'm not sure how to best approach this problem. I think I should use a BFS search, but I'm not 100% sure. All suggestions welcome, thanks in advance!