javascript - Eliminate isolated cave in procedural cave generation

I've got an algorithm that generates a cave procedurally, the map is modeled in the data as a 2d array of 0s (empty space) and 1s (wall). The algorithm works just fine, but I've got quite some isolated small caves on the scene, which I would like to avoid.

That's how the map looks that gets generated. Is there some efficient algorithm to remove the black holes in the white wall sections? I was thinking of something like:

For every closed cave, check if there is a bigger cave and if so, close it.

But that seems insanely inefficient since I'd have to loop over the map a lot in order to do this for all small caves.

Answer

1. 
   

   Edge-dilate and then edge-constrict the pixels - box or radial filter - basically increase the black areas by 1-2 pixels, then reduce by 1-2 pixels again. This will "smooth" the array out, removing small caves. The problem is this will also affect fine detail in your larger areas (unwanted?).

   
   


2. 
   

   Classify connected regions as nodes in a graph, as a graph is truest representation of what you've generated (that is, it models the flow your entities are able to move within). How:

   
   
   
   
   • Run through the entire 2D array, and add every white / open cell to an open list.
   
   
   • Step through each open cell in the open list.
   
   
   • Walk all neighbours and neighbours-of-neighbours etc. of the current cell, till you've found all open cells connected to this one (use flood fill for this); each time you find one, remove it from the open list, and add it to the list for this locally-adjacent group / node.
   
   
   
   • Now step to next (remaining, unaccounted for) open cell in the open list and do the same.
   
   
   
   

At the end you will have a sequence of nodes representing groups of connected, open cells. You can now just look at the number of cells constituting that group and remove it if its too small, or you can look it in a more geometric fashion (such as width / height of bounds) and reduce / eliminate where appropriate. This is a bit more complex, but it gives more control by only affecting those spaces you wish to affect, unlike dilate-constrict.