Thread by @lorenschmidt

organic level generation experiment thread! i have had this rolling around in my head forever, and i thought i'd finally take a stab at it.

the basic idea is to build spaces out of a set of amoebas which can crawl around, connect, etc. while maintaining topological sameness.

there will be a set of functions for modifying topological islands in various ways. this function retracts peninsulas (cells with only one neighbor in the island).

note that this retract function can never fragment an island, because any cell necessary for continuity will have at least two neighbors.

here is a simple function (with no fitness tests) for expanding a topological island.

if you combine this with the dead end retraction function above, you can expand + retract an island's borders.

this has an interesting property. the retract and expand functions have asymmetrical behavior, so over time certain features crystallize.

this is actually not dissimilar from how snowflakes form. the shape of snowflakes is governed by alternating grow + melt phases.

now let's add some other topological islands for this one to interact with. with our current rules, expanding doesn't take into account other islands. if you let this red island go, it'd spill into the yellow and orange regions and overlap with them.

so let's make it so our island can't overlap with, or touch, other islands.

we'll get all islands other than our current island, and assemble a list of their border cells. then when we expand our island, we can use that as a constraint.

"1" here will act as a barrier to red.

this is p. slow right now because i'm recrunching a ton of stuff every frame (and redrawing every step) but experiment first, optimize later.

here the red island is expanding outward while avoiding overlaps with other islands.

this is what happens if you expand all the regions outward in parallel. you get interesting organic blobs which fill all available space, with shapes dictated by how their neighbors are expanding.

(there's a weird bug which causing a cell to stay disconnected- not sure what that is but i'm sure i can fix it later if and when it is necessary)

16 regions

and here's what happens if you alternate expansion phases with the dead end removal function we wrote above. if you compare this with the previous map, you can see that the borders are much smoother, having far fewer zig-zags and 1 cell peninsulas, as you'd expect.

this map is qualitatively different, but it is also a solution to the same problem.

next let's add functionality for connections between topological islands.

if we were to keep the generation as-is, a single connection would be a 1 x 1 door between rooms.

(later, however, connections will get more complicated and islands will map less cleanly to rooms.)

working on a function for collapsing the corners of regions. that took a little doing, but it looks like the corner test is solid and doesn't throw false positives.

the usual complications. i'm writing a single pass, local solver which finds corners and dead ends which are safe to remove without splitting an island into multiple parts.

it's mostly working, but i have one special case where it's overzealous (corners with exactly 1 diagonal)

here's what it does right now. the occasional fragmentary bits left behind after contraction are caused by the bug mentioned above.

i have a couple of ideas for solutions but they're a little ungainly. i'm trying to come up with a solution i like.

oh my gosh oh my gosh, i think the new shrinkage function is working.

ok check this out, this should result in zero topological breakages.

because this respects topology, it refuses to break loops. some islands can shrink down all the way to a single cell. but others reach stable configurations propped up by stable configurations it cannot reduce.

a set of islands are expanded + contracted in parallel.

the eventual goal is to have a variety of different functions like these, which can modify islands for different effects without altering connections. adding pillars, removing pillars, repositioning islands.

now let's add functionality for finding shared border cells and adding connections between topological islands (grey "C" cells).

the next step will be to make all the island functionality respect multi-island topology.

shrinking areas down to topologically identical but reduced forms

these are all the same map, with rooms reshaped in place without altering the overall topology of the map.

this is starting to gesture at why this is an intriguing avenue of research. with more shaping functions, it would be possible to perform all sorts of alterations.

here's another way to modify a region. this has a more rectangular, architectural style. it will balloon out concave corners, naturally stopping once they become convex.