Zeichnen mit Ameisen: prozedurale Bilder unter Verwendung von Algorithmen zur Optimierung von Ameisenkolonien

Warum wollte ich mit Ameisen zeichnen?

Ich wollte ein Kunstwerk schaffen, das die Komplexität des Software-Designs untersucht. Wenn ich eine riesige Codebasis präsentiere, denke ich an die unabhängig auftretende Komplexität und die miteinander verflochtenen, miteinander verbundenen Teile. Seine allgemeine Form ergibt sich sozusagen aus den Handlungen vieler einzelner Persönlichkeiten.

Ich dachte darüber nach, wie ich das grafisch darstellen könnte, und eines der Bilder, die in mir eine Antwort fanden, war das Bild einer Ameisenkolonie. Ameisen sind ein gutes Beispiel für aufkommende (aufkommende) Komplexität. Keine einzelne Ameise ist Architekt, aber zusammen bauen sie prächtige komplexe Strukturen.

Schema der Formicaria. Quelle: Wikimedia Commons .

Ich suchte zunächst nach Informationen über Simulationen von Ameisenkolonien. Offensichtlich gibt es Literatur darüber, und es ist wunderschön . Der Trick war jedoch, dass die Ameisenhaufen teilweise abhängig von der Physik des Sandes und der Erde entstehen, in der sie gebaut sind - denn ihre Entstehung hängt davon ab, wie sich das Teilchen befindet, wenn die Ameise es einsetzt. Ich wollte etwas in 2D erstellen, also habe ich versucht, direkt zur Simulation zu gelangen, ohne Sandphysikcode zu schreiben, dh ich musste die physikalische Simulation des Ameisenhügels aufgeben.

Aus diesem Grund begann ich erneut zu suchen und sie führten mich zu einer völlig anderen Klasse von Ameisensimulationen:Algorithmen zur Optimierung von Ameisenkolonien (Algorithmen für Ameisenkolonien) .

Die Ameisenkolonieoptimierung ist ein Agentenalgorithmus, mit dem das Problem gelöst wird, den kürzesten Weg zwischen zwei Punkten eines Graphen zu finden. "Agent" bedeutet, dass der Algorithmus aus separaten Prozeduren besteht (in diesem Fall "Ameisen"), deren auftretendes Verhalten das Problem löst.

Es funktioniert sehr einfach. Jede Ameise hinterlässt auf ihrem Weg eine Spur von „Pheromonen“. Ameisen verlassen eine Art von Pheromon, nachdem sie den Ameisenhaufen verlassen haben, und die andere, wenn sie Nahrung finden. Ameisen, die nach Nahrung suchen, suchen nach einer Spur eines "Nahrungs" -Pheromons, während diejenigen, die nach Ameisenhaufen suchen, nach einer Spur eines "Heim" -Pheromons suchen.

Ameisen, die sich auf einem kürzeren Weg befinden, können schneller von zu Hause zum Futter und umgekehrt gelangen. Dies bedeutet, dass sie eine gesättigtere Schicht von Pheromonen bilden. Ameisen, die sich länger bewegen, bevorzugen eine reichhaltigere Spur und bewegen sich auf einem kürzeren Weg. Jede einzelne Ameise arbeitet nach sehr einfachen Regeln, aber im Laufe der Zeit finden die Ameisen einen optimaleren Weg zwischen zwei Punkten.

Simulation

Ich habe meinen Ameisensimulator für Processing 3 geschrieben. Ich habe meine eigene Implementierung gestartet, indem ich den Code aus diesem erstaunlichen Beitrag von Gregory Brown simuliert habe .

Nachdem sich die Ameisen zu bewegen begannen, begann ich, den Code zu erweitern und zu modifizieren, damit er in größeren Pixelgittern besser funktioniert. Ich wollte interessant aussehende Simulationen (nicht unbedingt effektiv ) und das bestimmte meine Arbeit am Code. Ich habe eine sehr rudimentäre Vision für Ameisen erstellt, damit jede Ameise mehrere Pixel vor sich sehen kann. Ich habe den Tod und die Wiedergeburt von Ameisen hinzugefügt, damit sie sich nicht zufällig im Raum verteilen. Schließlich habe ich die Ameisen etwas dümmer gemacht: Sie verlassen das Pheromon ständig, auch wenn die Suche nicht erfolgreich war, was dem tatsächlichen Verhalten der Ameisen ähnelt.

Hier können Sie den Simulationsport auf p5.js direkt in Ihrem Browser abspielen!

Sie können sich auch den portierten Quellcode auf Github ansehen .

Vor allem in der Simulation war ich fasziniert von den schönen, seltsamen und komplexen Formen, die Ameisen erzeugen. Sie marschieren nicht in geraden Linien, sondern bilden Schleifen, Kurven und Zweige. Noch interessanter ist, dass Sie das Erscheinungsbild von Figuren, die von Ameisen erstellt wurden, steuern können, indem Sie verschiedene Variablen ihrer Welt ändern. Sie können beispielsweise die Pheromonverdampfungsrate und den Sichtbereich von Ameisen in Pixel ändern.

Ameisen in Kunst verwandeln

Nachdem die Simulation zu funktionieren begann, bestand der nächste Schritt darin, die ausgegebenen Daten zu untersuchen. Mein Ziel war es, eine Art zweidimensionales Bild zu erstellen, dh ich musste die von den Ameisen erstellten Figuren erfassen und zeichnen.

Am Ende habe ich verschiedene Arten von Ausgaben geschrieben: verschiedene Arten von Rasterausgaben und einen Vektor. Um die Rasterausgabe zu erfassen, habe ich die von den Ameisen besuchten Zellen und die Häufigkeit ihrer Besuche verfolgt. Nachdem Sie mit den Filtern dieser Schlussfolgerung gespielt haben, können Sie eine gespenstische Spur der Orte erhalten, an denen die Ameisen besucht haben.

Ein Beispiel für eine Rasterausgabe. Die Wege sind viel breiter entlang der beliebten Ameisenpfade und wo die Ameisen zufällig um den Ameisenhaufen herumstreiften.

Die Rasterausgabe war interessant, aber ich wollte die einzelnen Pfade klarer sehen, deshalb habe ich die Möglichkeit des Exports nach svg untersucht. Für die Vektorausgabe habe ich die Geschichte jeder Ameise gespeichert, und als sie Nahrung oder Ameisenhaufen erreichten, habe ich diese Geschichte auf die Liste geschrieben. Zum Rendern habe ich jeden gespeicherten Pfad abgetastet und als eine Reihe von Kurven gerendert.

Ein Beispiel für die Vektorausgabe. Hier sehen Sie die einzelnen Wege der Ameisen. Wo es viele Ameisen gab, bilden leicht überlappende Linien breitere Wege.

Verbinde die Punkte

Ich wusste, dass ich Ameisen zeichnen wollte, die zwischen vielen Punkten reisen, daher war der Code zum Verknüpfen mehrerer Simulationen zu einem Bild einer der ersten. Aber was soll ich dann zeichnen?

Zuerst habe ich beschlossen, sehr wörtliche Diagramme zu erstellen: angefangen bei einfachen Binärbäumen bis hin zu komplexeren Visualisierungen. Dies schien ein natürlicher Schritt zu sein, da die Optimierung der Ameisenkolonie das Problem löst, Pfade in Graphen zu finden. Ich dachte auch, dass dies eine interessante Möglichkeit wäre, die Komplexität des Codes zu visualisieren: Warum nicht ein UML-Diagramm oder ein Abhängigkeitsdiagramm nehmen und sie mit Ameisen rendern?

Ich war bereits mit Graphviz vertraut und habe mich daher für dieses Toolkit und die DOT- Grafikbeschreibungssprache entschiedenum die Knoten und Kanten meiner Simulation anzugeben. Graphviz verfügt über einen Modus, der eine DOT-Datei mit Anmerkungen zu Pixelkoordinaten ausgibt. Ich habe einen sehr hässlichen DOT-Datei-Parser geschrieben und ihn mit einer kommentierten DOT-Datei verwendet, um Ameisenhaufen- und Essensstandorte zu simulieren.

Die Experimente mit binären Bäumen schienen vielversprechend und ergaben ein sehr natürliches, organisches Aussehen.

Ein einfacher Binärbaum. Mir wurde gesagt, dass es wie ein Angiogramm ist.

Ein etwas komplexerer Baum, schon ziemlich tief.

Dann fing ich an, mehr Diagramme mit verschiedenen Codebasen als Eingabe zu erstellen. Ich habe einige einfache Python-Skripte geschrieben: Das eine verwandelte den Git-Baum in eine DOT-Datei, das andere verwandelte C-Importabhängigkeiten in eine DOT-Datei.

Diagramm der Objekte im Git-Objektbaum, gezeichnet von Ameisen.

Abhängigkeiten zwischen Dateien im Linux-Kernel. Knoten und Kanten wurden im quadratischen Stil von Graphviz-Diagrammen erstellt. In der Tat nicht viel interessanter als zufällige Grafiken.

Obwohl all diese Grafiken interessant und definitiv komplex sind, war ich enttäuscht, dass sie tatsächlich nichts über die allgemeine Form der Codebasen sagten, auf denen sie aufgebaut waren. Je mehr ich mit Code-Visualisierung experimentierte, desto mehr wurde mir klar, dass das Erstellen eines interessanten Diagramms aus einer Codebasis an sich eine separate, schwierigere Aufgabe ist. Ich mochte jedoch die Komplexität sehr großer Grafiken und kam später wieder darauf zurück.

Mein nächstes Experiment waren Spiele mit einfachen Formen. Ich habe Diagramme aus Linien, Kreisen, Sinuskurven und anderen Formen erstellt, die mit Knoten und Kanten leicht zu beschreiben sind.

Die Punkte auf dem Segment auf der rechten Seite des Segments liegen näher beieinander.

Unterschiedliche Sinuswellenfrequenzen. Ich nehme an, ein ziemlich gutes Oszilloskop wird aus den Ameisen kommen.

Die einfachsten triangulierten Räume schienen mir die interessantesten zu sein. Ich habe viele gleichmäßig verteilte Punkte generiert - entweder zufällig oder durch Zeichnen von Formen - und dann die Verarbeitungsbibliothek verwendet, um diese Punkte in eine Delaunay-Triangulation oder ein Voronoi-Diagramm umzuwandeln. Dann wurden die resultierenden Rippen verwendet, um Ameisen zu simulieren, wobei jede Rippe einen "Ameisenhaufen" oder "Futter" bezeichnete.

Gezeichnet von Ameisen Voronoi Diagramm.

Dies führte zum Erscheinen eines wunderschönen, vollen Raums komplexer Ameisen-Komplikationen, der die Komplexität, die mich interessiert, viel besser beschreibt.

Schließlich näherte ich mich der Aufgabe aus einem anderen Blickwinkel. Ein Freund schaute sich die Simulation an und fragte, was passieren würde, wenn die Ameisen mit der Wand kollidieren - können sie einfache Hindernisse vermeiden? Mein Code wusste bereits, wie man Wände als Grenzfälle behandelt, also fügte ich nur Innenwände hinzu und verbrachte dann viel Zeit damit, Ameisen beizubringen, wie man Labyrinthe löst.

Die Wege der Ameisen, die versuchen, ein einfaches Labyrinth zu lösen. Sie können die Form des Labyrinths sehen, indem Sie feststellen, wohin die Ameisen nicht gehen können.

Ich hatte die Idee, dass Ameisen, wenn sie einfache Labyrinthe lösen können, diese miteinander kombinieren können, um eine größere Arbeit zu schaffen. Ich habe viel Zeit damit verbracht, die Simulationsvariablen so einzurichten, dass die Ameisen sie lösen konnten, aber ich konnte sie immer noch nicht dazu bringen, die Labyrinthe stabil zu lösen. Am Ende verwandelte sich all dies in nur Locken von Ameisenpfaden, die durch die Form des Labyrinths selbst begrenzt waren.

Fertiges Kunstwerk

Zu diesem Zeitpunkt beschloss ich, einen Schritt zurückzutreten und die Ergebnisse aller meiner Experimente zu berücksichtigen. Ich erkannte, dass die interessantesten Bilder aus großen Feldern halbzufälliger Punkte und Kanten stammen, und entschied mich, dies zu meiner endgültigen Entscheidung zu machen, indem ich die Simulation zum Zeichnen von Linien zwischen der Delaunay-Triangulation zufälliger Punkte einrichtete.

Simulationslauf abgeschlossen. Es enthält viele überlagerte Pfade, aus denen unscharfe Punkte erhalten werden.

Die letzte Frage war, wie SVG-Kurven in fertige Arbeiten umgewandelt werden können. Aus den Experimenten wusste ich, dass ich die Pfade irgendwie sortieren wollte, um Pfade mit einer schönen Form hervorzuheben. Der Durchlauf der fertigen Simulation dauerte jedoch ein bis zwei Stunden, weshalb es unpraktisch war, die Variablen bei jedem Durchlauf des Experiments zu ändern.

Ich habe beschlossen, ein zweites Verarbeitungsdiagramm zu schreiben , das die Simulationsausgabe in SVG lädt und dann die benötigten visuellen Effekte anwendet. Außerdem wollte ich das Nachbearbeitungsskript interaktiv gestalten, damit ich mit verschiedenen Gewichten und Farben von Linien sowie Sortierschwellen experimentieren kann.

Ich habe verschiedene Methoden ausprobiert, um die Pfade zu bewerten, die im Vordergrund und im Hintergrund stehen sollten. Es wurden verschiedene Faktoren berechnet: die Anzahl der Selbstschnittpunkte der Linie, die Anzahl der Schnittpunkte durch die Linie ihrer Steigungslinie und die Wahrscheinlichkeit, dass die Linie der durch die beiden vorherigen Punkte vorhergesagten Steigung folgt.

Ich habe das Nachbearbeitungsskript für Experimente mit unterschiedlichen Gewichten und Werten dieser Schätzungen verwendet, bis ich das gewünschte Aussehen erhalten habe.

Schwellenwerteinstellung für Vorder- und Hintergrundlinien.

Zu diesem Zeitpunkt hat das Speichern des Bildes beim Ändern jeder Variablen sehr geholfen. Als ich mich dem Bild näherte, das ich brauchte, war es viel einfacher, einige kleinere Variationen zu vergleichen, als mehrere Faktoren gleichzeitig zu ändern.

Nach einer langen Einrichtung und kleinen Änderungen habe ich aus meiner Simulation das folgende Bild erstellt:

Ich zoomte auf den Bereich, der mir am interessantesten erschien, und beschnitt ihn, um ein gutes Gleichgewicht zwischen leerem und gefülltem Raum herzustellen.

Der letzte Schritt war die Wahl, wie dieses Bild in ein physisches Objekt verwandelt werden soll. Ich habe sie digital als 40 × 50 cm großes Poster gedruckt und versucht (erfolglos), den Bildschirm auf Farbpapier zu drucken. Ein digital gedrucktes Poster sieht gut aus, aber in Zukunft möchte ich das Bild als Teil des Bildes kopieren. Ich finde komplexe Zeichnungen meditativ und denke, dass ich interessante Effekte erzielen kann, indem ich sie manuell zeichne.

Für dieses Projekt wurde viel mehr Zeit aufgewendet als erwartet, und es stellte sich als komplizierter heraus, als es am Anfang schien. Dies ist jedoch eine großartige Möglichkeit, mit allen Arten von Rechengeometrie und algorithmischen Problemen zu experimentieren. Ich finde es ziemlich ironisch, dass ich mehrere tausend Codezeilen für die Arbeit an Komplexität geschrieben habe, aber ich freue mich, dass es cool aussieht und für sich selbst spricht.

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