A while ago I started experimenting with an algorithm for creating web-like structures in two dimensions. Arguably the results are a little strange when compared to most spider webs, but interesting nonetheless. The image below is a picture of a plotter drawing made using a variation of the following algorithm.
This algorithms relies on a graph
structure. A triangle can be viewed as a graph consisting of three nodes
A, B and C. Connected with three edges
AB, BC and CA.
We need to be able to split edges in the graph. Assuming we have a single
edge, CD. We can split this edge by inserting a new node,
E, somewhere between C and D. To do
this we first delete CD, then add two new edges
CE and ED.
We will also be using this graph structure to apply forces between
connected nodes. In this use case the edges are undirected, which
means that means that an edge, CE, will cause C to
be affected by E and E to be equally affected by
C, except in the opposite direction. More on this later.
Now that we know the basic graph manipulations, the procedure for growing the web structure is the following:
- Create a few edges on the canvas. How you place them will greatly impact the result. Try scattering them at random, or using a geometrical shape.
- Create a single (candidate) line that intersects at least two of the existing edges.
- Find two neighboring intersections along the candidate line. Make sure you know which of the existing edges these intersections correspond to.
- According to the splitting method described above, insert a node at each of the intersection points on the two intersected edges.
- Create a new edge between the two new nodes.
- Repeat with a new candidate line.
Implementing the algorithm above will yield some kind of web structure. To make it more organic, we can apply interaction between connected nodes by assuming that the edges are elastic bands. Then we simulate that the bands try to retract back to some comfortable length.
A possible version of this can be achieved by doing the following for each node:
- Find all edges connected to the current node. Keep only the edges that are sufficiently long. This gives you the relevant connected nodes.
- Calculate vectors pointing towards each of the connected nodes.
- Normalize the length of these vectors to length
1. - Sum the normalized vectors.
- The new position of the current node is the original position plus the sum of the normalized vectors. You probably want to scale the sum by some small number to adjust the rate of movement.
When you have done this for all nodes, you can update the node positions to their corresponding new position. Make sure you don't change the current node positions until you are done calculating all the elastic band forces. Otherwise you will affect the end result.
To put it all together, you should create a loop that performs the elastic band calculations for every step. Then insert new edges every so often.
One more thing to consider is to always leave the nodes of the initial edges in their original position. If you don't you will end up with the web shrinking a lot; depending on how long your elastic bands are. There are a lot of other things to tweak in this algorithm. I will leave that to you.
Extending this idea to three dimensions is not too complicated. You can read more in the next post.
- Manipulating graphs like this can be a little tedious. If this is unfamiliar to you, I suggest using adjacency lists for storing your edges, and a separate list for storing node positions.
- Here is a Javascript example that illustrates how to find intersections between line segments. This code relies on p5.js.
- They don't have to be neighboring, but doing this ensures that edges do not cross each other.
- My implementation of this does not really calculate forces as such, but doing this could be an interesting extension. If you are interested, you can look at Hooke's Law. Another possible extension is adding some kind of gravity to the entire web.
- There are some ways to make this more efficient, but this is a reasonably straightforward method.
- As an aside, this kind of algorithm is well-suited for the pattern described in this post. Which is also how I implemented my version.