Simulating Tree Growth Through Digital Evolution
28 May, 2024Why are trees that shape? How do the cells know where to go and what specialized cell to turn into? And how can all that complex information be stored in a tensie weensie seed?
Michael Levin told me that we don’t actually understand the general morphogenesis of trees. And every time I step outside and look at trees, I feel like it’s an insult that we have no clue why they’re like that. They’re all around us, all the time!! How can we possibly not know this!
And so I decided I need to do something about this.
(check out the trees being simulated live here, hosted on replit at the time of writing)
Thoughts on Approaches
First, I looked into L-systems. Maybe I could figure out the minimal instruction set required to generate specific looking trees. But the more I thought about it, the more this didn’t seem like the right approach. It’s got the tree-like structure baked into how it’s generated. But we’re trying to figure out why this structure exists in the first place.
An interesting potential clue to this problem is that lightning, slime mold, rivers, and trees all have similar, well, tree-like structures. Which implies that this is actually a deeper problem.
I’ve been reading a lot of Stephen Wolfram’s work, and recently went down a rabbit hole of Michael Levin’s and I figured I could mix the two. Wolfram’s work has very minimal models. Levin’s work deals with higher level biology.
If I could mix the two to create a slightly less abstract cellular automata that could potentially represent a minimal model of a tree, I could try and evolve a minimal instruction set that the CA use that could ‘generate’ tree like structures.
Highly ‘fit’ cells learning to generate tree like structures could mean that trees are that way because that is the ‘best’ shape to take.
My Approach
I decided to make a hacky model ASAP, so I used p5js.
What are the minimal things required to represent a tree? For this experiment, I defined the living cells as one of two types:
- Structure
- Leaf
Non living cells can be soil or air.
Water could be found in the soil, and leaves generate energy inversely proportional to how many cells are above them. Structure cells diffuse both energy and water.
The issue with this, compared to simpler CA, is a combinatorial explosion. With 9 cells, 4 cell types, and a continuous range of energy and water, that’s a combinatorial explosion of possibilities. Which also makes you think about how crazy it is that life can adapt to so many factors in an environment.
I fixed this by making a hash function that deterministically mapped the environment to a number. I then selected an index from the genome by modding that number against the genome’s length.
One instruction set is a long string, each of which comes in pairs. The first indicates what cell to spawn, and the second which direction.
E.g. SA means a structure cell pointing up. LD means a leaf in the bottom right.
If cells don’t have enough water or energy for a predefined amount of time, they die.
Results
Because this was a hacky exploration, this raised more questions than answers. Here’s a few interesting general outcomes I learnt:
- In general, there’s something here. Cells do evolve into having instruction sets that get ‘fitter’ over time.
- The cells evolve into learning to create ‘roots’ first, and being conservative with growing upwards until they have enough energy.
Here's an example of a random, not so fit tree to compare
We aren’t seeing too many tree like structures, but we are seeing ‘interesting’ behavior.
- I think trees likely became tall to compete with other trees. Since there isn’t any competition between trees, it makes sense that ours don’t learn to get that much taller
- There’s no embedded physics, e.g. weight/gravity, that would incentivize trees to have thicker trunks. And so it’s natural for them to branch out in large clumps. In a sense, this is closer to the slime mold.
The physics of the world really impacts the structures, both their shapes and survival times. I might need to play around with the diffusion equations for energy/water, and how much energy/water each cell uses up each cycle.
Nothing could happen for a really long time, and then suddenly there would be a huge jump in fitness. This seems similar to an observation in the post on biological evolution by Wolfram.
Moving forward
Refactoring: I think I’m kind of constrained by how hacky the code is at this point. I’m going to need to refactor the entire thing into nice classes that allow me to specific environments, to track which tree a seed is a part of so I can have multiple trees, and to tweak the physics and live/die criteria easier.
Speeding it up: No more p5js. Being able to run this 10-100x faster means I can train several generations across multiple physics configurations for worlds in a reasonable amount of time.
More quantitative tests
- How fit can the cells become in a given environment?
- How does changing physics parameters change the highest fitness reached within a given amount of time?
- How does changing the length of the ‘genome’ affect the fitness curves?
And some questions about the validity of all this in general:
- Can we even use a deterministic hash function? This means that there’s a ton of states that get mapped to the same index. This might be a good thing, since the cells might evolve to use the same instruction to ‘solve’ for many different problems. This also could be bad, and prevent the cell from becoming fitter by placing two ‘incompatible’ neighborhoods together. This might be fixed by increasing the genome length.
- Is my method of evolution even valid? I’m taking the fittest tree we’ve seen so far, slightly varying the genes, and then adding the trees generated to the list of trees so far.
Really I need to clean the code up and become a bit more rigorous with testing everything from the physics, to the way I map to instructions, to the way I’m evolving.
But I thought I'd write down a quick update to checkpoint what I've got so far. If this is interesting, please feel free to reach out!
Here's the code and a live sim on a website. Be warned, the code is extremely hacky.