Search code examples
algorithmgraph-theorytheorygeographyflood-fill

Partial Flood Fill

I'm writing a voronoi-based world generator in which I distinguish between geographic features like mountains, lakes, forests, and oceans.

Each feature is given an id so it can be identified and referenced. I use a flood fill algorithm to determine what features cells belong to.

I've realized a couple similar cases where I'd like to split a feature into multiple smaller ones. The most straightforward example is that of two big forests connected by a narrow strip of forest. Realistically, it should be treated as two forests, separated from each other around the narrow strip but my fill algorithm just plows right through and labels everything as part of one large forest.

I'd like to eventually label them "West 100 Acre Wood" and "East 100 Acre Wood", giving them the knowledge that they're deriving from the same continuous body of forest. I've looked up partial flood fill logic but my search has gotten stuck due to my lack of subject terminology.

If you'd like to see the code I'm working with: https://github.com/olinkirkland/map

Solution

  • After you find a connected region, you can trace around the interior using the right-hand rule (https://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_follower).

    To find single-pixel paths that would make good splitting points, then, you can look for pixels in this interior path that are visited twice (once in each direction). If the path length is long enough on both sides of the split, then you can split the region into two at that pixel and maybe try again with the smaller regions.

    If you want to find split points that are more than one pixel wide, or ensure that the forests on either side are "beefy" enough, I would suggest a pixel-based approach that combines this with the other methods:

    1. BFS to remove pixels that are less than w away from the boundary.

    2. Find each remaining connected region. Each will be the "center" of a forest.

    3. Check each center to make sure it has pixels far enough from the edge to be the center of a forest.

    4. Add the removed pixels back, connecting them to the closest center.