3
\$\begingroup\$

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.

Map

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.

\$\endgroup\$
  • \$\begingroup\$ Are you sure you need to do this? \$\endgroup\$ – Nakilon Nov 25 '17 at 2:16
  • \$\begingroup\$ @AytAyt if you fill gaps with wall they'll be still "unusable". I mean one can use gaps as a decoration -- they may look natural. \$\endgroup\$ – Nakilon Nov 25 '17 at 2:26
  • 1
    \$\begingroup\$ Well, I'd like to since the goal is to generate a random item that has to be collected and I don't want it to spawn in an area that is not accessible. Of course I could check in the generation code if the randomly chosen spot is in the biggest caven, but id rather do it the other way around. \$\endgroup\$ – Claudio Brasser Nov 25 '17 at 14:16
3
\$\begingroup\$
  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.

\$\endgroup\$
  • \$\begingroup\$ Yes that is what I've meant by the solution I suggested abstractly. Create some sort of model for the map (agree that a graph would be a good fit) and define one sub-cave as a group of connected black spots. Then I could just fill in every cave under a certain size threshold. For your first suggestion: I'm running an algorithm that uses the 4-5 technique like this, but mine ends up looking a lot less smooth. Did I get this right that you would do multiple runs with different parameter ? \$\endgroup\$ – Claudio Brasser Nov 25 '17 at 14:11
  • 1
    \$\begingroup\$ @ClaudioBrasser It's fairly standard practice to perform multiple filter passes, yes. It all boils down to the specifics of your algorithm's parameters, yes.Of course multiple runs is typically more costly so we usually aim to get in done in as few runs as possible but this may not be a performance bottleneck for you so don't let that alone stop you from doing it the way the seems best. What problems are you still having? I definitely suggest the graph instead. \$\endgroup\$ – Engineer Nov 26 '17 at 6:17
  • 1
    \$\begingroup\$ I did pretty much what your second proposal suggested. I implemented a flood-fill algorithm that fills every section that is not the biggest cave. It has some computation delay at the moment and I'm going to try to reduce that, but it works :) Thank you! \$\endgroup\$ – Claudio Brasser Nov 26 '17 at 18:15
1
\$\begingroup\$

To get rid of the black spots inside the white portions , you can just flood-fill the large black part, (look for black parts until one is more than say 40% of the cells,) then remove all the other black parts.

If you want to keep sufficiently large caves that are still inside the walls then it is more complicated.

You could flood-fill every cave and remove any of them that are below a certain area/radius. That would be O(n) in caves, plus finding each cave, which I you could do by scanning each cell of the map only once, besides the flood-fill, so O(n) in cells.

If that is still too slow, you could try randomly sampling points, keeping only the large caves you happen to hit, and getting rid of the rest.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.