On Generative Algorithms
Differential Lattice Github
When working on Differential Line, Differential Mesh and Differential Mesh 3d the most tedious part was managing the data structure. Partly because I decided to try to learn to use the half-edge data structure properly in the process. Partly because I failed to do just that. And finally because I was writing it in Cython, which was new to me at the time.
Regardless of all of this, I got there eventually. This process led me to wish for a more loosely connected system. Such a system would be more easy to manage. I also had the idea that such a system could be similar to slime mold, in the same way that Differential Mesh is more or less recognizable as lichen.
With this in mind I started Differential Lattice. Part of the algorithm is very similar to Differential Mesh; it consists of connected nodes, and the connected nodes attempt to remain close together. It also shares the behaviour where each node tries to avoid all non-connected nodes within a certain radius. The important difference is that the connections between nodes is re-calculated before every iteration. This means that we need a nice way of deciding whether two nearby nodes should be neighbors or not.
It turns out that Relative neighborhoods work well for this. Relative neighborhoods are introduced in the previously mentioned leaf venation algorithm. Somewhat simplified we can say that two nodes are relative neighbors if a sufficiently large area between the two nodes does not contain any other nodes.
Another thing to consider in this system is how new nodes are introduced. In Differential Mesh new nodes are introduced by splitting edges in half. This is one of the somewhat tedious processes of a half-edge data structure. Especially if you have stubbornly implemented your own version of the data structure, like me. In a loosely connected system, such as Differential Lattice, adding a new node is simply a matter deciding on a position, introducing the node, and recalculating the neighborhoods. As you would in any step of the simulation.
Because of this, the challenge is reduced to deciding where to place the new nodes, and how often new nodes should appear. In these examples, new nodes appear in areas where the local density of nodes is greater than zero, yet sufficiently low. This causes new nodes to largely appear on the outside of the existing structure. In a manner somewhat similar to slime mold which is gradually growing outwards.
So far this system does not have any kind of food distribution, which is an interesting aspect to explore at a later time. E.g. is this simple system somehow able to replicate the Tokyo Railway System or display other kinds of interesting behaviours?
This algorithm has been implemented using pyCUDA, which means that all distance calculations, and neighborhood calculations can be done on the GPU. Because of this it is probably one of the fastest algorithms I have ever implemented. It is possible to make systems with hundreds of thousands of nodes surprisingly quickly, considering the amount of computation involved.
Below is an image with about 80 000 nodes which has been plotted on my mechanical plotter.
