How to implement the differential line growth algorithm with Processing
I wanted to implement the differential line growth algorithm since long time and finally I took the time to do it. My main sources were this and this. Thanks a lot then to Inconvergent and Entagma for sharing their approach!
Let’s go straight into the algorithm that, following Inconvergent’s description, goes like this:
First we start with a set of connected nodes in some shape (circles or lines are good). Then we randomly introduce new nodes between pairs of existing nodes. In every iteration the nodes will try to optimize their positions. They want to be close, but not too close, to their two neighbors. At the same time they want to be as far away as possible from all other nodes within a certain distance. Note that there is no actual collision detection involved here.
I made few attempts to implement this idea and at the end I realized that the behawior described is very similar to the one encountered in flocks, with few variations. So I went straight to the flocking example written by Daniel Shiffman on Processing’s website and copy-pasted the whole thing 😀
Compared to the flocking algorithm, the differential growth has two main differences: there is no alignement of the agents, so we can get rid of the align() method and the cohesion() method, instead of involving all the agents is only addressed to the two neighbors forming an edge. We also need a way to growth our structure and that’s what our growth() method does, adding a new Node when an edge becomes too long.
In order to get new patterns out of our structure, you can modify the base parameters and/or intervene on the growth() method, by changing when and where the new nodes are added and also by giving a different value to each node by adding, for example, a noise() function to the parameters, like: addNodeAt(new Node(middleNode.x, middleNode.y, maxForce*noise(i), maxSpeed, desiredSeparation, separationCohesionRation), index);
That’s it. The rest is some renaming and refactoring and then the magic of self-organizing structures with simple rules. If you are unfamiliar with vectors and forces I suggest you to read the first chapter of the great “The Nature of Code“, also by Daniel Shiffman. Here’s the code (check also the edit at the end), which you can also find on GitHub:
// PARAMETERS
float _maxForce = 0.9; // Maximum steering force
float _maxSpeed = 1; // Maximum speed
float _desiredSeparation = 9;
float _separationCohesionRation = 1.1;
float _maxEdgeLen = 5;
DifferentialLine _diff_line;
void setup() {
size(1280, 720);
_diff_line = new DifferentialLine(_maxForce, _maxSpeed, _desiredSeparation, _separationCohesionRation, _maxEdgeLen);
float nodesStart = 20;
float angInc = TWO_PI/nodesStart;
float rayStart = 10;
for (float a=0; a<TWO_PI; a+=angInc) {
float x = width/2 + cos(a) * rayStart;
float y = height/2 + sin(a) * rayStart;
_diff_line.addNode(new Node(x, y, _diff_line.maxForce, _diff_line.maxSpeed, _diff_line.desiredSeparation, _diff_line.separationCohesionRation));
}
}
void draw() {
background(255);
_diff_line.run();
_diff_line.render();
}
class DifferentialLine {
ArrayList<Node> nodes;
float maxForce;
float maxSpeed;
float desiredSeparation;
float separationCohesionRation;
float maxEdgeLen;
DifferentialLine(float mF, float mS, float dS, float sCr, float eL) {
nodes = new ArrayList<Node>();
maxSpeed = mF;
maxForce = mS;
desiredSeparation = dS;
separationCohesionRation = sCr;
maxEdgeLen = eL;
}
void run() {
for (Node n : nodes) {
n.run(nodes);
}
growth();
}
void addNode(Node n) {
nodes.add(n);
}
void addNodeAt(Node n, int index) {
nodes.add(index, n);
}
void growth() {
for (int i=0; i<nodes.size()-1; i++) {
Node n1 = nodes.get(i);
Node n2 = nodes.get(i+1);
float d = PVector.dist(n1.position, n2.position);
if (d>maxEdgeLen) { // Can add more rules for inserting nodes
int index = nodes.indexOf(n2);
PVector middleNode = PVector.add(n1.position, n2.position).div(2);
addNodeAt(new Node(middleNode.x, middleNode.y, maxForce, maxSpeed, desiredSeparation, separationCohesionRation), index);
}
}
}
void render() {
for (int i=0; i<nodes.size()-1; i++) {
PVector p1 = nodes.get(i).position;
PVector p2 = nodes.get(i+1).position;
line(p1.x, p1.y, p2.x, p2.y);
if (i==nodes.size()-2) {
line(p2.x, p2.y, nodes.get(0).position.x, nodes.get(0).position.y);
}
}
}
void exportFrame() {
saveFrame(day()+""+hour()+""+minute()+""+second()+".png");
}
}
class Node {
PVector position;
PVector velocity;
PVector acceleration;
float maxForce;
float maxSpeed;
float desiredSeparation;
float separationCohesionRation;
Node(float x, float y) {
acceleration = new PVector(0, 0);
velocity =PVector.random2D();
position = new PVector(x, y);
}
Node(float x, float y, float mF, float mS, float dS, float sCr) {
acceleration = new PVector(0, 0);
velocity =PVector.random2D();
position = new PVector(x, y);
maxSpeed = mF;
maxForce = mS;
desiredSeparation = dS;
separationCohesionRation = sCr;
}
void run(ArrayList<Node> nodes) {
differentiate(nodes);
update();
//render();
}
void applyForce(PVector force) {
acceleration.add(force);
}
void differentiate(ArrayList<Node> nodes) {
PVector separation = separate(nodes);
PVector cohesion = edgeCohesion(nodes);
separation.mult(separationCohesionRation);
//cohesion.mult(1.0);
applyForce(separation);
applyForce(cohesion);
}
void update() {
velocity.add(acceleration);
velocity.limit(maxSpeed);
position.add(velocity);
acceleration.mult(0);
}
PVector seek(PVector target) {
PVector desired = PVector.sub(target, position);
desired.setMag(maxSpeed);
PVector steer = PVector.sub(desired, velocity);
steer.limit(maxForce);
return steer;
}
void render() {
fill(0);
ellipse(position.x, position.y, 2, 2);
}
PVector separate(ArrayList<Node> nodes) {
PVector steer = new PVector(0, 0);
int count = 0;
for (Node other : nodes) {
float d = PVector.dist(position, other.position);
if (d>0 && d < desiredSeparation) {
PVector diff = PVector.sub(position, other.position);
diff.normalize();
diff.div(d); // Weight by distance
steer.add(diff);
count++;
}
}
if (count>0) {
steer.div((float)count);
}
if (steer.mag() > 0) {
steer.setMag(maxSpeed);
steer.sub(velocity);
steer.limit(maxForce);
}
return steer;
}
PVector edgeCohesion (ArrayList<Node> nodes) {
PVector sum = new PVector(0, 0);
int this_index = nodes.indexOf(this);
if (this_index!=0 && this_index!=nodes.size()-1) {
sum.add(nodes.get(this_index-1).position).add(nodes.get(this_index+1).position);
} else if (this_index == 0) {
sum.add(nodes.get(nodes.size()-1).position).add(nodes.get(this_index+1).position);
} else if (this_index == nodes.size()-1) {
sum.add(nodes.get(this_index-1).position).add(nodes.get(0).position);
}
sum.div(2);
return seek(sum);
}
}
I think that something like this would look very cool as a laser print on some wood! Once I get access to a laser tool-head I will update the post and show the results 😉
Edit
After the suggestions of Frederik Vanhoutte on FB, here’s an improved version of the code, faster and more efficient. You can see the difference especially if you want to get a bigger shape. I’ve decided to leave both versions here because this is a good example of refactoring and optimization. The for loops now are less heavy and part of the code has been moved to the higher level class DifferentialLine. Thanks Frederik!
// PARAMETERS
float _maxForce = 0.2; // Maximum steering force
float _maxSpeed = 2; // Maximum speed
float _desiredSeparation = 10;
float _separationCohesionRation = 1.1;
float _maxEdgeLen = 5;
DifferentialLine _diff_line;
void setup() {
size(1280, 720, FX2D );
_diff_line = new DifferentialLine(_maxForce, _maxSpeed, _desiredSeparation, _separationCohesionRation, _maxEdgeLen);
float nodesStart = 20;
float angInc = TWO_PI/nodesStart;
float rayStart = 10;
for (float a=0; a<TWO_PI; a+=angInc) {
float x = width/2 + cos(a) * rayStart;
float y = height/2 + sin(a) * rayStart;
_diff_line.addNode(new Node(x, y, _diff_line.maxForce, _diff_line.maxSpeed));
}
}
void draw() {
background(0, 5, 10);
stroke(255, 250, 220);
_diff_line.run();
_diff_line.renderLine();
}
class DifferentialLine {
ArrayList<Node> nodes;
float maxForce;
float maxSpeed;
float desiredSeparation;
float sq_desiredSeparation;
float separationCohesionRation;
float maxEdgeLen;
DifferentialLine(float mF, float mS, float dS, float sCr, float eL) {
nodes = new ArrayList<Node>();
maxSpeed = mF;
maxForce = mS;
desiredSeparation = dS;
sq_desiredSeparation = sq(desiredSeparation);
separationCohesionRation = sCr;
maxEdgeLen = eL;
}
void addNode(Node n) {
nodes.add(n);
}
void addNodeAt(Node n, int index) {
nodes.add(index, n);
}
void run() {
differentiate();
growth();
}
void growth() {
for (int i=0; i<nodes.size()-1; i++) {
Node n1 = nodes.get(i);
Node n2 = nodes.get(i+1);
float d = PVector.dist(n1.position, n2.position);
if (d>maxEdgeLen) { // Can add more rules for inserting nodes
int index = nodes.indexOf(n2);
PVector middleNode = PVector.add(n1.position, n2.position).div(2);
addNodeAt(new Node(middleNode.x, middleNode.y, maxForce, maxSpeed), index);
}
}
}
void differentiate() {
PVector[] separationForces = getSeparationForces();
PVector[] cohesionForces = getEdgeCohesionForces();
for (int i=0; i<nodes.size(); i++) {
PVector separation = separationForces[i];
PVector cohesion = cohesionForces[i];
separation.mult(separationCohesionRation);
nodes.get(i).applyForce(separation);
nodes.get(i).applyForce(cohesion);
nodes.get(i).update();
}
}
PVector[] getSeparationForces() {
int n = nodes.size();
PVector[] separateForces=new PVector[n];
int[] nearNodes = new int[n];
Node nodei;
Node nodej;
for (int i=0; i<n; i++) {
separateForces[i]=new PVector();
}
for (int i=0; i<n; i++) {
nodei=nodes.get(i);
for (int j=i+1; j<n; j++) {
nodej=nodes.get(j);
PVector forceij = getSeparationForce(nodei, nodej);
if (forceij.mag()>0) {
separateForces[i].add(forceij);
separateForces[j].sub(forceij);
nearNodes[i]++;
nearNodes[j]++;
}
}
if (nearNodes[i]>0) {
separateForces[i].div((float)nearNodes[i]);
}
if (separateForces[i].mag() >0) {
separateForces[i].setMag(maxSpeed);
separateForces[i].sub(nodes.get(i).velocity);
separateForces[i].limit(maxForce);
}
}
return separateForces;
}
PVector getSeparationForce(Node n1, Node n2) {
PVector steer = new PVector(0, 0);
float sq_d = sq(n2.position.x-n1.position.x)+sq(n2.position.y-n1.position.y);
if (sq_d>0 && sq_d<sq_desiredSeparation) {
PVector diff = PVector.sub(n1.position, n2.position);
diff.normalize();
diff.div(sqrt(sq_d)); //Weight by distacne
steer.add(diff);
}
return steer;
}
PVector[] getEdgeCohesionForces() {
int n = nodes.size();
PVector[] cohesionForces=new PVector[n];
for (int i=0; i<nodes.size(); i++) {
PVector sum = new PVector(0, 0);
if (i!=0 && i!=nodes.size()-1) {
sum.add(nodes.get(i-1).position).add(nodes.get(i+1).position);
} else if (i == 0) {
sum.add(nodes.get(nodes.size()-1).position).add(nodes.get(i+1).position);
} else if (i == nodes.size()-1) {
sum.add(nodes.get(i-1).position).add(nodes.get(0).position);
}
sum.div(2);
cohesionForces[i] = nodes.get(i).seek(sum);
}
return cohesionForces;
}
void renderShape() {
beginShape();
for (int i=0; i<nodes.size(); i++) {
vertex(nodes.get(i).position.x, nodes.get(i).position.y);
}
endShape(CLOSE);
}
void renderLine() {
for (int i=0; i<nodes.size()-1; i++) {
PVector p1 = nodes.get(i).position;
PVector p2 = nodes.get(i+1).position;
line(p1.x, p1.y, p2.x, p2.y);
if (i==nodes.size()-2) {
line(p2.x, p2.y, nodes.get(0).position.x, nodes.get(0).position.y);
}
}
}
}
class Node {
PVector position;
PVector velocity;
PVector acceleration;
float maxForce;
float maxSpeed;
Node(float x, float y, float mF, float mS) {
acceleration = new PVector(0, 0);
velocity =PVector.random2D();
position = new PVector(x, y);
maxSpeed = mF;
maxForce = mS;
}
void applyForce(PVector force) {
acceleration.add(force);
}
void update() {
velocity.add(acceleration);
velocity.limit(maxSpeed);
position.add(velocity);
acceleration.mult(0);
}
PVector seek(PVector target) {
PVector desired = PVector.sub(target, position);
desired.setMag(maxSpeed);
PVector steer = PVector.sub(desired, velocity);
steer.limit(maxForce);
return steer;
}
}
