Draw with ants: procedural images using ant colony optimization algorithms

Why did I want to draw with ants

I wanted to create a work of art exploring the complexity of software design. When I present a huge code base, I think about its independently arising complexity and its intertwined, interconnected parts. Its general form, so to speak, arises from the actions of many individual personalities.

I was thinking about how to present this graphically, and one of the images that found a response in me was the image of an ant colony. Ants are a great example of emerging (emergent) complexity. No single ant is an architect, but together they build magnificent complex structures.

Scheme of formicaria. Source: Wikimedia Commons .

I started by looking for information on simulations of ant colonies. Obviously, literature exists about this, and it is beautiful . But the trick was that the anthills arise in part depending on the physics of the sand and the earth in which they are built - because their creation depends on how the particle will be located when the ant puts it. I wanted to create something in 2D, so I tried to go straight to the simulation without writing sand physics code, that is, I had to abandon the physical simulation of the anthill.

Because of this, I began to search again, and they led me to a completely different class of ant simulations:ant colony optimization algorithms (ant colony algorithms) .

Ant colony optimization is an agent algorithm used to solve the problem of finding the shortest path between two points of a graph. “Agent” means that the algorithm consists of separate procedures (in this case, “ants”), the emergent behavior of which solves the problem.

It works very simply. Each ant leaves a trace of “pheromones” in its path. Ants leave one type of pheromone after leaving the anthill and the other when they find food. Food-seeking ants seek to find a trace of a “food” pheromone, while those seeking anthill seek a trace of a “home” pheromone.

Ants who find themselves on a shorter path are able to faster route from home to food and vice versa. This means that they will create a more saturated layer of pheromones. Ants moving longer will prefer a richer track and move along a shorter path. Each individual ant works according to very simple rules, but over time the ants find a more optimal path between two points.

Simulation

I wrote my ant simulator on Processing 3. I started my own implementation by simulating the code from this amazing post by Gregory Brown .

After the ants began to move, I began to expand and modify the code so that it works better in larger pixel grids. I wanted to get interesting looking simulations (not necessarily effective ) and that determined my work on the code. I created a very rudimentary vision for ants so that each ant can see several pixels ahead. I added the death and rebirth of ants so that they do not randomly disperse throughout the space. Finally, I made the ants a little dumber: they leave the pheromone constantly, even if the search was unsuccessful, which is similar to the real behavior of the ants.

Here you can play the simulation port on p5.js right in your browser!

You can also take a look at the ported source code on Github.

Most of all in the simulation, I was fascinated by the beautiful, strange and complex shapes created by ants. They do not march in straight lines, but form loops, turns and branches. Even more interesting is that you can control the appearance of figures created by ants by changing various variables of their world. For example, you can change the pheromone evaporation rate and the range of vision of ants in pixels.

Turn ants into art

After the simulation began to work, the next step was to study the data it outputs. My goal was to create some kind of two-dimensional image, that is, I needed to capture and draw the figures created by the ants.

In the end, I wrote different types of output: several types of raster output and one vector. To capture the raster output, I tracked the cells visited by the ants and the frequency of their visits. After playing with the filters of this conclusion, you can get a ghostly trace of those places where the ants visited.

An example of raster output. The paths are much wider along the popular ant tracks and where the ants randomly roamed around the ant hill.

The raster output was interesting, but I wanted to see the individual paths more clearly, so I explored the possibility of exporting to svg. For vector output, I saved the history of each ant, and when they reached food or anthill, I wrote down this story on the list. For rendering, I sampled every saved path and rendered it as a series of curves.

An example of vector output. Here you can see the individual paths of ants. Where there have been many ants, slightly overlapping lines form wider paths.

Connect the dots

I knew that I wanted to draw ants traveling between many points, so the code for linking several simulations into one image was one of the first. But then what should I draw?

At first I decided to create very literal graphs: starting with simple binary trees, then move on to more complex visualizations. This seemed like a natural step, because optimization of the ant colony solves the problem of finding paths in graphs. I also thought that this would be an interesting way to visualize code complexity: why not take a UML diagram or a dependency graph and render them with ants?

I was already familiar with Graphviz , so I decided to use this toolkit and the DOT graph description languageto specify the nodes and edges of my simulation. Graphviz has a mode that outputs a DOT file with annotations of pixel coordinates. I wrote a very ugly DOT file parser and used it with an annotated DOT file to simulate anthill and food locations.

The experiments with binary trees seemed promising and gave a very natural, organic appearance.

A simple binary tree. I was told that it is like an angiogram.

A slightly more complex tree, already quite deep.

Then I began to build more graphs using various code bases as input. I wrote some simple Python scripts: one turned the git tree into a DOT file, the other turned C import dependencies into a DOT file.

Graph of objects in the git object tree drawn by ants.

Dependencies between files in the Linux kernel. Nodes and edges were created using the square style of Graphviz graphs. In fact, not much more interesting than random graphs.

Although all these graphs are interesting and definitely complex, I was disappointed that in fact they did not say anything about the general form of the code bases on which they were built. The more I experimented with code visualization, the more I realized that constructing an interesting graph from a code base in itself is a separate, more difficult task. However, I liked the complexity of very large graphs and later I returned to this again.

My next experiment was games with simple forms. I created graphs from lines, circles, sinusoids, and other shapes that are easy to describe with nodes and edges.

The points on the segment, on the right side of the segment, the points are closer to each other.

Different sine wave frequencies. I suppose a quite good oscilloscope will come out of the ants.

The simplest triangulated spaces seemed to me the most interesting. I generated a lot of evenly distributed points — either randomly or by drawing shapes — and then used the Processing library to turn these points into a Delaunay triangulation or Voronoi diagram. Then, the resulting ribs were used to simulate ants, where each rib denoted one “ant hill” or “food”.

Drawn by ants Voronoi diagram.

This led to the appearance of a beautiful full space of complex ant intricacies, which described the complexity that interests me much better.

Finally, I approached the task from another angle. One friend looked at the simulation and asked what would happen when the ants collide with the wall - can they avoid simple obstacles? My code already knew how to handle walls as borderline cases, so I just added internal walls, and then spent a lot of time trying to teach ants how to solve mazes.

The paths of ants trying to solve a simple maze. You can see the shape of the maze by noticing where the ants cannot go.

I had the idea that if ants can solve simple mazes, then you can combine them together to create a larger work. I spent a lot of time setting up the simulation variables so that the ants could solve them, but I still could not get them to solve the mazes stably. In the end, all this turned into just curls of ant paths, limited by the shape of the labyrinth itself.

Finished work of art

At this stage, I decided to take a step back and consider the output of all my experiments. I realized that the most interesting images were obtained from large fields of semi-random points and edges, and decided to make this my final decision by setting up the simulation to draw lines between the Delaunay triangulation of random points.

Completed simulation run. It contains many superimposed paths from which fuzzy spots are obtained.

The final issue was how to turn SVG bends into finished work. From the experiments, I knew that I wanted to sort the paths in some way to highlight paths with a beautiful shape. But the run of the finished simulation took one to two hours, which is why it was inconvenient to change the variables at each run of the experiment.

I decided to write a second Processing diagram that will load the simulation output into SVG and then apply the visual effects I need. Moreover, I wanted to make the post-processing script interactive so that I could experiment with different weights and colors of lines, as well as sorting thresholds.

I tried several different ways to evaluate the paths that should be in the foreground and in the background. Several different factors were calculated: the number of self-intersections of the line, the number of intersections by the line of its slope line, and the probability that the line will follow the slope predicted by the previous two points.

I used the post-processing script for experiments with different weights and values ​​of these estimates, until I got the look I needed.

Threshold setting for front and background lines.

At this point, saving the image when changing each variable helped a lot. When I approached the image I needed, it was much easier to compare a number of minor variations than to change several factors at a time.

After a long setup and making small changes, I created the following image from my simulation:

I zoomed in on the area that seemed most interesting to me, and cropped it to create a good balance between empty and filled space.

The last step was the choice of how to turn this image into a physical object. I used to print them digitally as a 40 × 50 cm poster and attempted (unsuccessfully) to print the screen on color paper. A digitally printed poster looks great, but in the future I want to copy the image as part of the picture. I find complex drawings meditative and I think that I can achieve interesting effects by drawing them manually.

Much more time was spent on this project than I expected, and it turned out to be more complicated than it seemed at the beginning. But this is a great way to experiment with all kinds of computational geometry and algorithmic problems. I think it's pretty ironic that I wrote several thousand lines of code for work on complexity, but I am pleased that it looks cool and speaks for itself.

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