Lors de la réalisation du jeu A-Graphe, je m'étais frotté à « la représentation graphique automatisée d'arbres mathématiques ». Ouch, dit ainsi ça fait mal.

Pour ceux qui ne connaîtraient pas, un arbre est une forme particulière de graphe dans lequel on n'autorise pas les cycles : c'est-à-dire que si on descend d'élément en élément, on atteindra forcément un nœud final (les nœuds atteints de cette façon sont nommés feuille). À l'inverse, si on remonte n'importe quel élément, on finira toujours par tomber sur le même nœud (la racine de l'arbre).

Un arbre au sens strict est une structure mathématique abstraite de sa représentation graphique : si l'on veut, on peut représenter tous les nœuds (le terme nœud désigne les sommets ; donc la racine, les feuilles, et les nœuds qui les relient) au même point (au détriment de la lisibilité) ou faire des imbroglios de « fils » en plaçant les éléments au hasard. Bien entendu, on a souvent besoin de présenter une information claire à l'internaute, et on ne peut se permettre de lui donner un pâté immonde (sauf si le but du jeu est de démêler ledit pâté). Le but de cet article sera d'envisager deux façons de structurer l'arbre automatiquement : d'abord, par un positionnement statique (le plus simple), ensuite par un positionnement dynamique (plus complexe, mais avec des meilleurs résultats).

Allez, la partie aride est terminée, maintenant on s'amuse !

Pré-requis

Pour illustrer mes propos, je passerai encore une fois par le langage ActionScript3 utilisé par Flash.
Dans les deux cas, je ferai trois tests distincts de la méthode présentée :

• D'abord, sur un arbre prédéterminé (c'est un niveau extrait d'A-graphe) ;
• Ensuite, sur un arbre généré aléatoirement à chaque lancement ;
• Enfin, sur un gros arbre (plus de 100 nœuds) généré aléatoirement.

La majorité du code source reste le même dans les deux cas (statique et dynamique), je ne détaillerai donc pas le code, juste les algorithmes.

Représentation graphique d'un arbre par la méthode statique

L'approche la plus intuitive est la méthode statique.
Comme on ne sait pas de combien de niveaux on va devoir « creuser » dans l'arbre, on utilise une méthode récursive. Au départ, on place la racine au milieu du dessin, puis on boucle pour placer chacun de ses enfants en cercle régulier autour de lui (c'est simple, il suffit d'un minimum de trigonométrie avec un angle qui varie selon le nombre d'enfants).
Ensuite, on reproduit la méthode sur chacun des enfants, mais plutôt que d'accorder 360° de liberté pour le placement, on restreint l'intervalle à utiliser (on veut une impression d'éclaté, et pas des ronds : à chaque itération, on va donc réduire l'amplitude autorisée). Ceci se traduit par un angle initial (l'angle du parent par rapport à son maître) et une amplitude de liberté : autrement dit, on confine le nœud dans un espace bien déterminé et on les place régulièrement dans l'amplitude autorisée.

Au début, l'amplitude est donc de 360°. Si on a quatre enfants, chacun des enfants d'enfants aura alors 90° de liberté. Ces 90° seront centrés autour de l'angle du parent : pour le premier enfant, on placera les enfants d'enfants entre -45° et 45° (ce qui donne bien une amplitude – centrée – de 90°), pour le second entre 90-45° et 90+45°, et ainsi de suite, le 90 correspondant ici à l'angle que fait l'enfant avec la racine.
Ce n'est pas clair ? La méthode suivante devrait vous aider :

 
/**
 * Permet un placement de l'arbre par une méthode récursive.
 * @param  Noeud Le noeud à placer. Ses enfants seront ensuite placés récursivement.
 * @param  Rayon Le rayon d'écart avec ses enfants
 * @param  Amplitude L'angle à utilier : 2Pi au début, il se réduit au fur et à mesure de l'enfoncement dans l'arbre.
 * @param  Angle L'angle de départ.
 */
private function placement(Noeud:Node,Rayon:search?q=int%20inurl:http://livedocs.adobe.com/flex/201/langref/%20inurl:int.html&filter=0&num=100&btnI=lucky">int,Amplitude:search?q=Number%20inurl:http://livedocs.adobe.com/flex/201/langref/%20inurl:Number.html&filter=0&num=100&btnI=lucky">Number=2*search?q=Math%20inurl:http://livedocs.adobe.com/flex/201/langref/%20inurl:Math.html&filter=0&num=100&btnI=lucky">Math.PI,AngleCentral:search?q=Number%20inurl:http://livedocs.adobe.com/flex/201/langref/%20inurl:Number.html&filter=0&num=100&btnI=lucky">Number=0):void
{
  //Calculer le pas qui sépare deux enfants. Par exemple, si on est sur le noeud principal et qu'on a une amplitude de 2Pi pour quatre enfants, le pas sera de Pi/2 (un noeud à chaque point cardinal).
  var Step:search?q=Number%20inurl:http://livedocs.adobe.com/flex/201/langref/%20inurl:Number.html&filter=0&num=100&btnI=lucky">Number = Amplitude / Noeud.Enfants.length;
  //L'angle initial : il suffit de décaler l'angle central par la moitié de l'amplitude. On ajoute aussi la moitié du pas pour équilibrer l'arbre ; sinon l'intervalle n'est pas centré et c'est moche.
  var Angle:search?q=Number%20inurl:http://livedocs.adobe.com/flex/201/langref/%20inurl:Number.html&filter=0&num=100&btnI=lucky">Number = AngleCentral - Amplitude / 2 + Step / 2;
 
  for each(var Enfant:Node in Noeud.Enfants)
  {
    //placer l'enfant relativement au père
    Enfant.x = Noeud.x + Rayon * search?q=Math%20inurl:http://livedocs.adobe.com/flex/201/langref/%20inurl:Math.html&filter=0&num=100&btnI=lucky">Math.cos(Angle);
    Enfant.y = Noeud.y + Rayon * search?q=Math%20inurl:http://livedocs.adobe.com/flex/201/langref/%20inurl:Math.html&filter=0&num=100&btnI=lucky">Math.sin(Angle);
 
    //Puis demander le placement des enfants de l'enfant (c'est téchenique ça)
    placement(Enfant, Rayon * .8, Step, Angle);
 
    //Et incrémenter le pas pour le prochain noeud :
    Angle += Step;
  }
}
 

Et le premier appel, qui déclenche la cascade d'évènements :

 
//Placer la racine, et placer ses enfants sur un cercle de 200 de rayon.
placement(Racine,200);
 

Voilà de quoi tester. Cliquez sur le cercle noir pour faire démarrer l'animation :

Quelques exemples de rendus :

Représentation graphique d'un arbre par la méthode dynamique

La méthode statique présente l'avantage d'être rapide et efficace dans la plupart des cas. Cependant, on peut difficilement faire des animations (dans le cas de l'ajout d'un nœud en direct, on obtient des sauts peu esthétiques), et les structures obtenues sont trop « mathématiques ». Enfin, quand le nombre de nœuds augmente, on obtient un fratras incompréhensible… et pas forcément optimisé, puisque de grands vides peuvent rester si un nœud de haut niveau n'a pas d'enfants.

Pour pallier à ces problèmes, on va étudier une solution plus intéressante.
L'idée, c'est de maximiser en permanence les écarts entre chaque nœud : après tout, plus ils sont loins, plus l'utilisation de l'espace est optimisée ! Cela ne vous rappelle rien ? Mais si, souvenez-vous de vos cours de lycée et de la loi de l'attraction du sieur Newton : on a là une formule parfaitement adaptée pour modéliser le comportement de nos sommets ! Deux nœuds très proches vont fortement se repousser, deux nœuds plus loin vont encore s'éloigner mais de façon plus poussive. On pourra intelligemment se référer à AI Game : Programming Wisdom pour une utilisation de cette méthode dans la positionnement d'agent sur un terrain.

Mais il y a un problème : avec cette loi, les nœuds vont s'éloigner à l'infini (comme les galaxies dans l'univers). C'est vrai ; il faut donc ajouter une contrainte pour éviter ce fâcheux comportement. Et cette contrainte, c'est justement notre arbre : certains nœuds doivent garder une distance faible entre eux pour modéliser le lien. On pourrait donc se contenter d'indiquer au système « la distance entre ces deux nœuds doit être constante », mais il me parait plus intéressant d'accrocher un ressort virtuel entre chaque extrémité ; comme ça tout est représenté sous forme de forces physiques. Il ne reste plus quà y appliquer le célèbre PFD (Σ F = ma [n'oublions pas que ce sont des vecteurs]) pour avoir un positionnement correct, avec animation s'il vous plaît !

Avant d'en dire plus, le résultat (comme tout à l'heure, cliquez sur le rond noir. Soyez patient, même quand les nœuds n'apparaissent plus il y a du mouvement) :

Deuxième version, avec ajout d'objets en continu (placements initial aléatoire, arrêt après 150 ronds).

Développons un peu… à la création d'un nœud, on ajoute une liste de contraintes :

• D'abord, le nœud est repoussé par tous les autres nœuds. Pour simplifier les calculs, on a mis la masse à 1 ; la formule devient alors 1/d².
• Ensuite, le nœud s'accroche avec son père : on met un ressort entre les deux, de constante de raideur 0,2 et de longueur à vide 40 (sauf dans le cas du nœud principal, pour lequel on donne plus de libertés avec une longueur à vide plus forte).

Puis à chaque mise à jour de l'affichage, on calcule pour chacun des nœuds la liste des forces et on applique le PFD pour en déduire l'accélération. Comme on est dans un quanta de temps très faible, on n'intègre pas l'accélération et on se contente d'ajouter la valeur obtenue à la vitesse, puis d'ajouter la vitesse à la position. C'est brutal, mais cela permet d'accélérer énormément les calculs (intégrer numériquement peut prendre du temps… ) et donne des résultats tout à fait corrects tant qu'on calcule bien la position de tout le monde en même temps.
Accessoirement, on gère le cas des forces infinies (distance = 0) pour éviter les forces infinies ! Et c'est tout. Comme on le voit, le résultat est agréable à regarder, relativement performant (tant qu'on reste en dessous de 500 nœuds), ajustable (l'ajout d'un nœud minimise les déplacements à effectuer) et tout cela pour un code qui reste simple.

De plus, on est certain d'obtenir un système stable après un temps suffisament long : les nœuds sont alors placés sur des minimums locaux utilisant le moins d'énergie (on dit que l'ensemble minimise les contraintes, une des lubies principales de mère nature).

Quelques exemples de rendus :

Et pour les amateurs, la structure de l'arbre des catégories d'Omnilogie, pour donner un exemple d'application pratique :)

Quelques preuves que le codage n'est pas si complexe :

 
/* CALCUL DE LA FORCE D'UN RESSORT*/
 
//Mettre à jour la force.
var Distance:search?q=int%20inurl:http://livedocs.adobe.com/flex/201/langref/%20inurl:int.html&filter=0&num=100&btnI=lucky">int = search?q=Math%20inurl:http://livedocs.adobe.com/flex/201/langref/%20inurl:Math.html&filter=0&num=100&btnI=lucky">Math.max(1,search?q=Math%20inurl:http://livedocs.adobe.com/flex/201/langref/%20inurl:Math.html&filter=0&num=100&btnI=lucky">Math.sqrt(search?q=Math%20inurl:http://livedocs.adobe.com/flex/201/langref/%20inurl:Math.html&filter=0&num=100&btnI=lucky">Math.pow(Bout.x - AutreBout.x, 2) + search?q=Math%20inurl:http://livedocs.adobe.com/flex/201/langref/%20inurl:Math.html&filter=0&num=100&btnI=lucky">Math.pow(Bout.y - AutreBout.y, 2)));//penser à éviter la division par zéro
 
//Calculer la valeur absolue (scalaire, pas un vecteur)
var absForce:search?q=Number%20inurl:http://livedocs.adobe.com/flex/201/langref/%20inurl:Number.html&filter=0&num=100&btnI=lucky">Number = k * (Longueur - Distance);
 
//Puis la projeter sur l'axe défini par les deux points
AttractionBout.x = absForce * (Bout.x - AutreBout.x) / Distance;
AttractionBout.y = absForce * (Bout.y - AutreBout.y) / Distance;
 
//Calculer la force inverse (une force s'applique sur A, l'autre sur B)
AttractionAutreBout.x = - AttractionBout.x;
AttractionAutreBout.y = - AttractionBout.y;
 
//Et appliquer la force aux objets pour le prochain calcul du PFD
Bout.applyForce(AttractionBout);
AutreBout.applyForce(AttractionAutreBout);  
 

 
/* APPLICATION DU PFD */
 
//Calcul de la somme des forces
for each(var Force:Vecteur in Forces)
  Resultante.ajouter(Force);
 
//application du PFD : Somme des forces = masse * Accélération
//Resultante.scalarMul(1/this.Masse);//Inutile, masse à 1
 
//Puis mise à jour de la vitesse. À ce point là, le vecteur Resultante correspond au vecteur accélération.
//Il faut noter qu'on fait les calculs à chaque itération : l'intégration du vecteur accéleration pour obtenir le vecteur vitesse se transforme alors en une simple addition.
Vitesse.ajouter(Resultante);    
//Ajouter des frottements pour éviter d'avoir les ressorts qui oscillent à l'infini
Vitesse.scalarMul(FROTTEMENTS);
 
//Calcul de la nouvelle position selon la même logique intégration = addition.
this.x += Vitesse.x;
this.y += Vitesse.y;
 
//Vidage de la liste des forces pour le prochain calcul
Forces.splice(0,Forces.length);
Resultante.reset();  
 

Bref, encore un exemple de modélisation simple d'un système complexe… en voulant extraire les paramètres macroscopiques, on devait affronter des équations mathématiques et des cas particuliers de plus en plus retors pour améliorer le système initial ; avec des contraintes microscopiques (atomiques au sens étymologique) on se contente de donner des règles simples à satisfaire qui permettent d'obtenir un comportement complexe. Une sorte de jeu de la vie… qui montre l'importance de la réflexion avant le codage.

Télécharger les codes. Le code statique n'est pas optimisé du tout car il incorpore aussi les ressorts et les interactions (sans les afficher bien entendu). Pour passer en mode auto, changez la variable "MODE" avant de compiler.