Deterministic branching

Je veux créer un système d’embranchements pour mon système de botanique algorithmique qui ne repose pas sur le hasard, de façon à ce que mes algorithmes génétiques puissent déterminer quels sont les types d’arbres les plus « performants » (je ne sais toujours pas comment ces performances pourront être évaluées).

Mon système d’embranchement m’a permis de créer une grande quantité d’arbres différents ; chaque arbre possède clairement une apparence, ou un caractère visuel, qui lui est propre. On peut voir un montage de plusieurs de ces arbres en croissance sur mon fil Twitter.

J’ai rassemblé ci-dessous beaucoup de notes techniques prises lors de ce travail.

Notes de travail

En ce moment, tout dépend d’une probabilité, définie dans le prototype DNA :

this.branchingProbability = 0.02;

Et ensuite, dans la méthode grow d’un objet Segment, un simple test permet de déterminer si un embranchement doit se faire :

if (Math.random() <= this.dna.branchingProbability) {
    this.branch();
}

Les embranchements sont ainsi complètement probabilistes, et peuvent aussi se faire à répétition. Ils ne sont pas limités. Ce qu’il me faut, maintenant, ce sont des objets Segment qui aient deux nouvelles propriétés lors de leur création :

this.branchedLeft = false;
this.branchedRight = false;

Et une fois qu’un embranchement se ferait, une de ces deux booléennes deviendrait true et cet embranchement ne pourrait plus se faire. Il pourrait quand même y avoir une probabilité qu’un embranchement se fasse ou non… Ce serait quand même beau de voir certains petits rameaux se former sur des segments d’arbres qui ont déjà créé des embranchements plus grands.

Fréquence d’embranchement

Le problème plus compliqué est celui de la fréquence d’embranchement. Il doit y avoir quatre valeurs différentes pour gérer cette fréquence dans l’objet DNA. Chaque gène du génotype d’un arbre sera, comme on le voit ici, normalisé, c’est-à-dire que sa valeur sera située entre 0 et 1. Je ne suis pas certain que ce soit la meilleure solution mais, pour l’instant, j’avance avec cette idée.

this.branchingFrequencyLeft = 0.1;
this.branchingFrequencyRight = 0.20;
this.branchingOffsetLeft = 0.5;
this.branchingOffsetRight = 0.9;

Cependant, ces quatres valeurs devront être transformées en nombres entiers par la partie du code qui interprétera l’objet DNA.

Maintenant, je dois avoir un nombre qui représente la distance en segments d’un segment à la base de l’arbre. Je pourrais déclarer une propriété segmentID lors de la création d’un arbre.

let Tree = function(x, y, dna) {
    //...
    this.segmentID = 0;
};

Et ensuite, incrémenter cette valeur à chaque nouveau segment.

let Segment = function(parent) {
    this.parent = parent;
    this.dna = parent.dna;
    this.isRoot = this.parent instanceof Tree;
    this.segmentID = parent.segmentID + 1;

Maintenant, un embranchement à gauche peut être réalisé si…

let fL = this.dna.branchingFrequencyLeft;
let oL = this.dna.branchingOffsetLeft;
if ((this.segmentID - oL) % fL == 0) {
    branchLeft();
}

À moins que… j’initialise les booléennes branchedLeft et branchedRight avec ce test.

let Segment = function(parent) {
    //...
    let fL = this.dna.branchingFrequencyLeft;
    let oL = this.dna.branchingOffsetLeft;
    let fR = this.dna.branchingFrequencyRight;
    let oR = this.dna.branchingOffsetRight;
    this.branchedLeft = (this.segmentID + oL) % fL == 0;
    this.branchedRight = (this.segmentID + oR) % fR == 0;
    this.branchedForward = false;

Ainsi, lorsque branchedLeft ou branchedRight sont true, ces embranchements ne peuvent pas se faire, peu importe s’ils se sont déjà faits. Et si elles sont false, le petit test probabiliste peut être exécuté.

Il me faut donc deux nouvelles méthodes, branchLeft et branchRight, dans le prototype Segment. Elles seront bien entendu presque identiques.

Segment.prototype.branchLeft = function() {
    this.children.push(new Segment(this));
    this.energy -= this.dna.branchingCost;
    this.branchedLeft = true;
};

Quand je crée un nouveau segment, maintenant, ce segment doit pouvoir recevoir un second argument, direction, qui pourra être égal à left, forward, ou right. Ah, et pendant tout ce temps, j’ai aussi besoin d’une propriété branchedForward déclarée dans le constructeur du prototype Segment. L’argument direction ne sert qu’à ajuster l’angle du nouveau segment créé. Je crois bien, si j’y pense, qu’un segment n’a pas besoin de savoir s’il est à gauche, devant ou à droite de son parent.

Dont je peux préserver la propriété branchingProbability du prototype DNA telle quelle, mais maintenant elle servira dans trois contextes — elle déterminera l’embranchement à gauche, devant et à droite.

Segment.prototype.branch = function(direction) {
    this.children.push(new Segment(this, direction));
    this.energy -= this.dna.branchingCost;
    if (direction == "left") {
        this.branchedLeft = true;
    } else if (direction == "forward") {
        this.branchedForward = true;
    } else if (direction == "right") {
        this.branchedRight = true;
    } else {
        console.error("Invalid branching direction.");
    }
};

Notes éparses

J’aimerais bien aussi explorer ce type d’arbre.

Context

This blog post is part of my research project Towards an algorithmic cinema, started in April 2018. I invite you to read the first blog post of the project to learn more about it.