Dessiner avec des fourmis: images procédurales utilisant des algorithmes d'optimisation des colonies de fourmis

Pourquoi voulais-je dessiner avec des fourmis

Je voulais créer une œuvre d'art explorant la complexité de la conception de logiciels. Lorsque je présente une énorme base de code, je pense à sa complexité indépendante et à ses parties entrelacées et interconnectées. Sa forme générale, pour ainsi dire, résulte des actions de nombreuses personnalités individuelles.

Je réfléchissais à la façon de présenter cela graphiquement, et l'une des images qui a trouvé une réponse en moi était l'image d'une colonie de fourmis. Les fourmis sont un excellent exemple de complexité émergente (émergente). Aucune fourmi n'est architecte, mais ensemble, ils construisent de magnifiques structures complexes.

Schéma de formicaria. Source: Wikimedia Commons .

J'ai commencé par chercher des informations sur les simulations de colonies de fourmis. Évidemment, il y a de la littérature à ce sujet, et c'est magnifique . Mais l'astuce était que les fourmilières surgissent en partie en fonction de la physique du sable et de la terre dans laquelle elles sont construites - parce que leur création dépend de la façon dont la particule sera située lorsque la fourmi la déposera. Je voulais créer quelque chose en 2D, j'ai donc essayé d'aller directement à la simulation sans écrire de code de physique du sable, c'est-à-dire que j'ai dû abandonner la simulation physique de la fourmilière.

Pour cette raison, j'ai recommencé à chercher, et ils m'ont conduit à une classe complètement différente de simulations de fourmis:algorithmes d'optimisation des colonies de fourmis (algorithmes des colonies de fourmis) .

L'optimisation des colonies de fourmis est un algorithme d'agent utilisé pour résoudre le problème de la recherche du chemin le plus court entre deux points d'un graphique. «Agent» signifie que l'algorithme se compose de procédures distinctes (dans ce cas, «fourmis»), dont le comportement émergent résout le problème.

Cela fonctionne très simplement. Chaque fourmi laisse une trace de «phéromones» sur son passage. Les fourmis quittent un type de phéromone après avoir quitté la fourmilière et l'autre lorsqu'elles trouvent de la nourriture. Les fourmis à la recherche de nourriture cherchent une trace d'une phéromone «alimentaire», tandis que celles qui recherchent la fourmilière cherchent une trace d'une phéromone «domestique».

Les fourmis qui se trouvent sur un chemin plus court sont en mesure de passer plus rapidement de la maison à la nourriture et vice versa. Cela signifie qu'ils créeront une couche de phéromones plus saturée. Les fourmis se déplaçant plus longtemps préféreront une piste plus riche et se déplaceront sur un chemin plus court. Chaque fourmi individuelle fonctionne selon des règles très simples, mais au fil du temps, les fourmis trouvent un chemin plus optimal entre deux points.

Simulation

J'ai écrit mon simulateur de fourmi sur Processing 3. J'ai commencé ma propre implémentation en simulant le code de cet article incroyable de Gregory Brown .

Après que les fourmis ont commencé à se déplacer, j'ai commencé à développer et à modifier le code afin qu'il fonctionne mieux dans les grilles de pixels plus grandes. Je voulais obtenir des simulations intéressantes (pas nécessairement efficaces ) et cela a déterminé mon travail sur le code. J'ai créé une vision très rudimentaire pour les fourmis afin que chaque fourmi puisse voir plusieurs pixels devant elle. J'ai ajouté la mort et la renaissance des fourmis afin qu'elles ne se dispersent pas au hasard dans l'espace. Enfin, j'ai rendu les fourmis un peu plus bêtes: elles quittent constamment la phéromone, même si la recherche a échoué, ce qui est similaire au comportement réel des fourmis.

Ici, vous pouvez jouer le port de simulation sur p5.js directement dans votre navigateur!

Vous pouvez également jeter un œil au code source porté sur Github.

Surtout dans la simulation, j'étais fasciné par les formes magnifiques, étranges et complexes créées par les fourmis. Ils ne marchent pas en ligne droite, mais forment des boucles, des virages et des branches. Encore plus intéressant, vous pouvez contrôler l'apparence des figures créées par les fourmis en modifiant diverses variables de leur monde. Par exemple, vous pouvez modifier le taux d'évaporation des phéromones et la portée de vision des fourmis en pixels.

Transformez les fourmis en art

Une fois que la simulation a commencé à fonctionner, l'étape suivante a été d'étudier les données qu'elle produit. Mon objectif était de créer une sorte d'image bidimensionnelle, c'est-à-dire que je devais capturer et dessiner les figures créées par les fourmis.

Au final, j'ai écrit différents types de sortie: plusieurs types de sortie raster et un vecteur. Pour capturer la sortie raster, j'ai suivi les cellules visitées par les fourmis et la fréquence de leurs visites. Après avoir joué avec les filtres de cette conclusion, vous pouvez obtenir une trace fantomatique des endroits où les fourmis ont visité.

Un exemple de sortie raster. Les sentiers sont beaucoup plus larges le long des pistes de fourmis populaires et où les fourmis ont erré au hasard autour de la colline des fourmis.

La sortie raster était intéressante, mais je voulais voir plus clairement les chemins individuels, j'ai donc exploré la possibilité d'exporter en svg. Pour la sortie vectorielle, j'ai sauvegardé l'histoire de chaque fourmi, et quand elles ont atteint la nourriture ou la fourmilière, j'ai écrit cette histoire sur la liste. Pour le rendu, j'ai échantillonné chaque chemin enregistré et je l'ai rendu sous la forme d'une série de courbes.

Un exemple de sortie vectorielle. Ici, vous pouvez voir les chemins individuels des fourmis. Là où il y a eu beaucoup de fourmis, les lignes qui se chevauchent légèrement forment des chemins plus larges.

Relier les points

Je savais que je voulais dessiner des fourmis voyageant entre plusieurs points, donc le code pour lier plusieurs simulations en une seule image était l'un des premiers. Mais alors, que dois-je dessiner?

Au début, j'ai décidé de créer des graphes très littéraux: en commençant par des arbres binaires simples, puis en passant à des visualisations plus complexes. Cela semblait être une étape naturelle, car l'optimisation de la colonie de fourmis résout le problème de la recherche de chemins dans les graphiques. J'ai aussi pensé que ce serait une façon intéressante de visualiser la complexité du code: pourquoi ne pas prendre un diagramme UML ou un graphe de dépendances et les rendre avec des fourmis?

Je connaissais déjà Graphviz , j'ai donc décidé d'utiliser cette boîte à outils et le langage de description des graphiques DOTpour spécifier les nœuds et les bords de ma simulation. Graphviz dispose d'un mode qui génère un fichier DOT avec des annotations de coordonnées de pixels. J'ai écrit un analyseur de fichiers DOT très laid et je l'ai utilisé avec un fichier DOT annoté pour simuler des emplacements de fourmilière et de nourriture.

Les expériences avec des arbres binaires semblaient prometteuses et donnaient un aspect organique très naturel.

Un arbre binaire simple. On m'a dit que c'est comme une angiographie.

Un arbre un peu plus complexe, déjà assez profond.

Ensuite, j'ai commencé à construire plus de graphiques en utilisant différentes bases de code en entrée. J'ai écrit quelques scripts Python simples: l'un a transformé l'arbre git en un fichier DOT, l'autre a transformé les dépendances d'importation C en un fichier DOT.

Graphique des objets dans l'arbre d'objets git dessiné par des fourmis.

Dépendances entre les fichiers du noyau Linux. Les nœuds et les bords ont été créés en utilisant le style carré des graphiques Graphviz. En fait, pas beaucoup plus intéressant que les graphiques aléatoires.

Bien que tous ces graphiques soient intéressants et définitivement complexes, j'ai été déçu qu'en fait ils n'aient rien dit sur la forme générale des bases de code sur lesquelles ils ont été construits. Plus j'expérimentais la visualisation de code, plus je réalisais que la construction d'un graphique intéressant à partir d'une base de code en soi était une tâche distincte et plus difficile. Cependant, j'ai aimé la complexité des très grands graphiques et plus tard, j'y suis retourné.

Ma prochaine expérience était des jeux avec des formes simples. J'ai créé des graphiques à partir de lignes, de cercles, de sinusoïdes et d'autres formes faciles à décrire avec des nœuds et des bords.

Les points sur le segment, sur le côté droit du segment, les points sont plus proches les uns des autres.

Différentes fréquences d'onde sinusoïdale. Je suppose qu'un assez bon oscilloscope sortira des fourmis.

Les espaces triangulés les plus simples me semblaient les plus intéressants. J'ai généré de nombreux points uniformément répartis - soit au hasard, soit en dessinant des formes - puis j'ai utilisé la bibliothèque de traitement pour transformer ces points en triangulation de Delaunay ou en diagramme de Voronoi. Ensuite, les côtes résultantes ont été utilisées pour simuler des fourmis, chaque côte désignant une «fourmilière» ou «nourriture».

Dessiné par les fourmis diagramme Voronoi.

Cela a conduit à l'apparition d'un bel espace plein de subtilités complexes de fourmis, qui décrivait la complexité qui m'intéresse beaucoup mieux.

Enfin, j'ai abordé la tâche sous un autre angle. Un ami a regardé la simulation et a demandé ce qui se passerait lorsque les fourmis entreraient en collision avec le mur - peuvent-elles éviter de simples obstacles? Mon code savait déjà comment gérer les murs comme des cas limites, alors j'ai simplement ajouté des murs internes, puis j'ai passé beaucoup de temps à essayer d'enseigner aux fourmis comment résoudre les labyrinthes.

Les chemins des fourmis essayant de résoudre un labyrinthe simple. Vous pouvez voir la forme du labyrinthe en remarquant où les fourmis ne peuvent pas aller.

J'ai eu l'idée que si les fourmis peuvent résoudre des labyrinthes simples, alors vous pouvez les combiner ensemble pour créer une œuvre plus grande. J'ai passé beaucoup de temps à configurer les variables de simulation afin que les fourmis puissent les résoudre, mais je n'arrivais toujours pas à les faire résoudre les labyrinthes de manière stable. En fin de compte, tout cela s'est transformé en de simples boucles de chemins de fourmis, limitées par la forme du labyrinthe lui-même.

Oeuvre d'art finie

À ce stade, j'ai décidé de prendre du recul et de considérer le résultat de toutes mes expériences. J'ai réalisé que les images les plus intéressantes étaient obtenues à partir de grands champs de points et de bords semi-aléatoires, et j'ai décidé d'en faire ma décision finale en configurant la simulation pour tracer des lignes entre la triangulation de Delaunay des points aléatoires.

Cycle de simulation terminé. Il contient de nombreux chemins superposés à partir desquels des points flous sont obtenus.

Le dernier problème était de savoir comment transformer les virages SVG en travail fini. D'après les expériences, je savais que je voulais trier les chemins d'une certaine manière pour mettre en évidence les chemins avec une belle forme. Mais l'exécution de la simulation terminée a pris une à deux heures, c'est pourquoi il n'était pas pratique de modifier les variables à chaque exécution de l'expérience.

J'ai décidé d'écrire un deuxième diagramme de traitement qui chargera la sortie de simulation dans SVG, puis appliquera les effets visuels dont j'ai besoin. De plus, je voulais rendre le script de post-traitement interactif afin de pouvoir expérimenter différents poids et couleurs de lignes, ainsi que des seuils de tri.

J'ai essayé plusieurs façons d'évaluer les chemins qui devraient être au premier plan et en arrière-plan. Plusieurs facteurs différents ont été calculés: le nombre d'auto-intersections de la ligne, le nombre d'intersections par la ligne de sa ligne de pente et la probabilité que la ligne suive la pente prédite par les deux points précédents.

J'ai utilisé le script de post-traitement pour des expériences avec différents poids et valeurs de ces estimations, jusqu'à ce que j'obtienne l'apparence dont j'avais besoin.

Réglage du seuil pour les lignes avant et arrière-plan.

À ce stade, l'enregistrement de l'image lors du changement de chaque variable a beaucoup aidé. Lorsque j'ai approché l'image dont j'avais besoin, il était beaucoup plus facile de comparer un certain nombre de variations mineures que de changer plusieurs facteurs à la fois.

Après une longue configuration et de petits changements, j'ai créé l'image suivante à partir de ma simulation:

J'ai zoomé sur la zone qui me semblait la plus intéressante et l'ai recadrée pour créer un bon équilibre entre l'espace vide et l'espace rempli.

La dernière étape a été le choix de la manière de transformer cette image en objet physique. Je les imprimais numériquement sous forme d'affiche de 40 × 50 cm et tentais (sans succès) d'imprimer l'écran sur du papier couleur. Une affiche imprimée numériquement a fière allure, mais à l'avenir, je veux copier l'image en tant que partie de l'image. Je trouve les dessins complexes méditatifs et je pense que je peux obtenir des effets intéressants en les dessinant manuellement.

Beaucoup plus de temps a été consacré à ce projet que ce à quoi je m'attendais, et il s'est avéré plus compliqué qu'il n'y paraissait au début. Mais c'est un excellent moyen d'expérimenter toutes sortes de problèmes de géométrie de calcul et d'algorithmes. Je pense que c'est assez ironique d'avoir écrit plusieurs milliers de lignes de code pour travailler sur la complexité, mais je suis heureux que cela ait l'air cool et parle de lui-même.

Source: https://habr.com/ru/post/undefined/