|
|
|
|
|
|
by sgentle
237 days ago
|
|
|
As far as I can tell, this isn't adding any meaningful topology. The various notions of graph-connectedness basically amount to a standard finite-state CA with a slightly complex update rule. The per-cell update mechanism, using "amazing dragons" as an example: 1. Calculate a metric for every cell based on its neighbours eg: metric = sum(1/degree if degree > 0)
2. Calculate whether each cell is eligible based on its metric eg: eligible = (state > 0) ? (0.9 <= metric <= 2.6) : (1.4 <= metric <= 7.0)
3. Calculate new state based on degree (degree = eligible ? number of eligible neighbours : 0) eg: state = (degree == 1 || degree == 7) ? 0 : degree
Since the "edges" just represent eligibility of neighbours, which depends on their neighbours, you can replace them with a larger neighbourhood (ie 5x5 instead of 3x3). And since state is just degree or 0, you effectively have 1 more state than degrees.Here's an example of that approach: https://www.shadertoy.com/view/wXSyRw I think for this to live up to the name it would need one or both of the following: 1. edges that mask or gate cells in some way (ie a dynamic neighbourhood)
2. rules that turn edges into other edges without going via cell states |
|
|
However, your Shadertoy port doesn't produce equivalent behavior to the original rule—I've tried several corrections in your shader and none match.
While you've demonstrated the theoretical point, this actually highlights why the abstraction matters: implementing these dynamics correctly is non-trivial even when the algorithm seems straightforward. The three-phase execution, metric calculations, and mutual eligibility create subtle interactions that are easy to get wrong.
Why the shader port doesn't work:
I've successfully implemented this same rule in Taichi (also GPU-based), and comparing the two reveals the issue.
The three-phase execution model requires intermediate storage between phases that Shadertoy's ping-pong buffer architecture can't provide.
In my Taichi implementation, each phase has its own buffer:
- Phase 1 reads node_degree (previous state) and writes to node_next_eligible
- Phase 2 reads node_next_eligible and writes to node_next_degree
- Phase 3 reads node_next_degree and writes back to node_degree
Shadertoy only has two buffers (previous frame read-only, current frame write-only), so the shader tries to collapse all three phases into one pass. But this breaks the execution model: when Phase 2 checks if a neighbor is eligible, it needs the neighbor's just-computed eligibility from Phase 1 of the current step, not the previous frame's data.
To properly implement this in a shader, you'd need either:
- A multi-pass setup with three separate render passes and intermediate textures
- Clever state packing to encode multiple values (eligibility + degree) in one buffer
The fact that the algorithm works correctly in Taichi but requires careful buffer management even on GPU demonstrates that "theoretical equivalence to traditional CA" doesn't mean "trivial to implement."
The three-phase execution model with intermediate states is a real architectural requirement, not just an abstraction.
Regarding edge rule tables: LACE has complete UI infrastructure for true edge-to-edge dynamics (edge states evolving based on connection patterns, independent of node eligibility).
The Rule Editor even has a full tab for it (which appears if a rule implements rule tables). But no rule implements the execution logic yet—it's a dormant feature that would provide the dynamic topology you're suggesting.
Thanks for pushing me to be more precise about all this though :)