Seethis 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. Thepercolations 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 whatpercolation 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, butI 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 theconnectivity, to figure out whether the maps are traversable, but I haven’t pursued this. Also seeDirk Brockmann’s explorable explanation about percolation[3] andthis example of using the idea to make cave maps[4] [2021].