Tile-real-ization optimization idea

[Isaac Dupree]

I thought of a way we might be able to optimize worldblock (tileblock?)
creation without constraining/complicating a worldgen much.

Imagine the tiles of the initial world as an infinite graph, each tile
connected by adjacency with all 26 neighbors.

Choose a finite set of nodes that, if removed, would disconnect the
graph. It then has a finite interior and an infinite exterior. If the
set of removed nodes are all air, then (for most worlds, most of the
time) every node in the "interior" is also air.

Call exceptions to this rule "castles in the air". Each "castle in the
air" is a maximal connected subgraph of non-air tiles that is finite.

If we know there are no "castles in the air", then when we need to
real-ize a large cube/sphere-ish region of tiles all at once[1], we can
first check only the edge tiles of that region; if all are air, then we
know the whole region is air at O(n^2) rather than O(n^3), n being radius.

But if we allow certain types of rock or wisp[2] that can create stable
castles in the air, perhaps some worldgen functions will find it easy to
inform us about their castles-in-the-air. A worldgen, when asked about
a region, would have to state whether it might contain any castles in
the air. I wonder how many worldgens would have difficulty doing a good
job of that. Probably some, and certainly not others! Worlds where
it's too difficult can at worst always say a region might contain
castles in the air. Worlds with normal physics will probably always say
that a region contains no castles in the air.

This observation about "castles in the air" probably works analogously
for "castles in the water". Optimizing for water would be useful once
we have giant swimming pools (also known as oceans).

I'm not sure whether O(n^2) is good enough, nor whether the constant
factors and heuristics make it worth it to do at all. But maybe! (It's
clearly possible to do better in some cases, because [I think] a lot of
worlds have a maximum elevation and can say in O(1) that any region
above that is all air.) Whether adjacency has to be "all 26 neighbors"
depends on whether a tile can be supported on the diagonals without (an)
orthogonal rock(s) in between that creates an orthogonal path between
them. Note to self: If, when we create a worldblock, we cache whether
each of its boundaries was initially all-air, and cache this recursively
up the worldblock trie, and only real-ize areas adjacent to ones we
already know... well that does not help the O() complexity (some sides
will usually be as-of-yet-unknown) but it might help practically.

[1] TODO: but in our current plans, we'll rarely know all-at-once that
we'll need a large region bigger than worldblock side. Clever
heuristics {about when to real-ize and/or forget worldblocks that are
near other worldblocks we need} might be necessary and sufficient.

[2] wisps: I'm thinking the region around Zelazny's Courts of Chaos, if
I recall it rightly, with zillions of wispy walking-paths winding
through empty three-dimensional space. Those probably drifted around
over time, but we could have stationary wisps.