See this article[1] about percolation over triangulations. Construct a graph by picking random points and then running the Delaunay Triangulation. Assign a random color to each point. The percolations keep only the edges connecting points to their own color. Here’s the result:
Take each point from the above graph and draw a cell around it:
Do you see a path from the top of the map to the bottom of the map? Is it in the black region or the white region? Does this always happen? That’s what percolation theory[2] is about. This connectivity could be useful for cave maps or maybe also for forest wilderness maps.
More options:
Jitter:
regions, cell shapes.
But wait, there’s more! The threshold doesn’t have to be constant! For a procedurally generated map, it could be useful to force an area to be open so that you can place a set piece / prefab room there:
It could also be useful to vary the density. Here’s a gradient:
Here’s a variable density using Simplex/Perlin noise:
And here’s also Simplex/Perlin noise but tweaked to make the middle values more common, since they produce the most interesting patterns:
I was originally inspired by the article about percolation, but I ended up not using the percolation. I realized that I was just filling cells based on a threshold. I think the percolation aspect might be useful for studying the connectivity, to figure out whether the maps are traversable, but I haven’t pursued this. Also see Dirk Brockmann’s explorable explanation about percolation[3] and this example of using the idea to make cave maps[4] [2021].