Search code examples
arraysalgorithmpath-finding

Algorithm for tile connection in a two-dimensional array


I have a simple Tile-Class, which has the property IsBlack. I'm working with a two-dimensional array (Tile[,]).

I'd like to check whether all white fields (those where IsBlack=false) are connected. Following examples would return true:

enter image description here enter image description here

Whereas following would return false:

enter image description here

I have a number of ideas, though I think they are rather inefficient:

  • Run a path-finding algorithm from between every single tile (very inefficient)
  • Find "rectangles" of black tiles. (For example, the first image has 1 rectangle, the "border") There must be only 1. (not sure if this approach is valid)

Solution

    1. Search in raster order for a white field
    2. Run a floodfill algorithm from that point and mark which tiles you have visited
    3. Continue searching to see if there are any more white fields that are not marked as visited

    If steps 3 finds an unvisited white, then return false, otherwise return true.