![](https://habrastorage.org/getpro/habr/post_images/59e/d31/366/59ed31366bcf08b906a07e476152a66c.png)
Почему мне захотелось рисовать муравьями
Я хотела создать произведение искусства, исследующее сложность проектирования программного обеспечения. Когда я представляю огромную кодовую базу, то думаю о её самостоятельно возникающей сложности и о её переплетённых, взаимосвязанных частях. Её общая форма, если так можно выразиться, возникает из действий множества отдельных личностей.
Я думала о том, как представить это графически, и одной из нашедших во мне отклик картинок стало изображение муравьиной колонии. Муравьи — прекрасный пример возникающей (эмерджентной) сложности. Ни один отдельный муравей не является архитектором, но вместе они строят великолепные сложные структуры.
![](https://habrastorage.org/getpro/habr/post_images/5b1/4f3/a72/5b14f3a72a15eefbeef534448a51647b.jpg)
Схема формикария. Источник: Wikimedia Commons.
Я начала с поиска информации о симуляциях колоний муравьёв. Очевидно, что литература об этом существует, и она прекрасна. Но хитрость заключалась в том, что муравейники возникают частично в зависимости от физики песка и земли, в которых они строятся — ведь их создание зависит от того, как расположится частица, когда её положит муравей. Я хотела создать что-то в 2D, поэтому стремилась сразу перейти к симуляции без написания кода физики песка, то есть мне пришлось отказаться от физической симуляции муравейника.
Из-за этого я снова принялась за поиски, и они привели меня к совершенно другому классу симуляций муравьёв: алгоритмам оптимизации муравьиной колонии (муравьиным алгоритмам).
Оптимизация муравьиной колонии — это агентный алгоритм, используемый для решения задачи нахождения кратчайшего пути между двумя точками графа. «Агентный» означает, что алгоритм состоит из отдельных процедур (в данном случае — «муравьёв»), эмерджентное поведение которых решает задачу.
Работает это очень просто. Каждый муравей оставляет на своём пути след из «феромонов». Муравьи оставляю один тип феромонов после выхода из муравейника и другой — когда найдут еду. Ищущие еду муравьи стремятся найти след «пищевого» феромона, а ищущие муравейник — след «домашнего» феромона.
Муравьи, оказавшиеся на более коротком пути, способны быстрее проделать маршрут от дома до еды и обратно. Это означает, что они создадут более насыщенный слой феромонов. Муравьи, движущиеся более долго, будут предпочитать более насыщенный след и двигаться по более короткому пути. Каждый отдельный муравей работает по очень простым правилам, но со временем муравьи находят более оптимальный путь между двумя точками.
Симуляция
Я написала свой симулятор муравьёв на Processing 3. Собственную реализацию я начала с имитирования кода из этого потрясающего поста Грегори Брауна.
После того, как муравьи начали двигаться, я приступила к расширению и модификации кода, чтобы он лучше работал в более масштабных сетках пикселей. Я хотела получить интересно выглядящие симуляции (необязательно эффективные) и это определило мою работу над кодом. Я создала для муравьёв очень рудиментарное зрение, чтобы каждый муравей мог видеть на несколько пикселей вперёд. Я добавила смерть и возрождение муравьёв, чтобы они не разбредались хаотично по всему пространству. Наконец, я сделала муравьёв немного глупее: они оставляют феромон постоянно, даже если поиск оказался неудачным, что похоже на реальное поведение муравьёв.
Здесь можно сыграть в порт симуляции на p5.js прямо в браузере!
Можете также взглянуть на портированный исходный код на Github.
Больше всего в симуляции меня восхитили красивые, странные и сложные формы, создаваемые муравьями. Они не маршируют по прямым линиям, а образуют петли, витки и ответвления. Ещё интереснее то, что вы можете управлять видом создаваемых муравьями фигур, изменяя различные переменные их мира. Например, можно изменять скорость испарения феромона и дальность зрения муравьёв в пикселях.
Превращаем муравьёв в искусство
После того, как симуляция начала работать, следующим шагом стало исследование выводимых ею данных. Моя цель заключалась в создании некоего двухмерного изображения, то есть мне нужно было захватывать и отрисовывать создаваемые муравьями фигуры.
В конечном итоге я написала разные типы вывода: несколько типов растрового вывода и один векторный. Для захвата растрового вывода я отслеживала посещённые муравьями ячейки и частоту их визитов. Поиграв с фильтрами этого вывода, можно получить призрачный след тех мест, где побывали муравьи.
![](https://habrastorage.org/getpro/habr/post_images/b02/930/8ca/b029308ca64dee625eccbe87749bfc87.png)
Пример растрового вывода. Пути намного шире вдоль популярных следов муравьёв и там, где муравьи случайным образом бродили вокруг муравейника.
Растровый вывод был интересным, но я хотела, чтобы были чётче видны отдельные пути, поэтому исследовала возможность экспорта в svg. Для векторного вывода я сохраняла историю каждого муравья, и когда они достигали пищи или муравейника, записывала эту историю в список. Для рендеринга я сэмплировала каждый сохранённый путь и отрисовывала его как серию кривых.
![](https://habrastorage.org/getpro/habr/post_images/069/397/a81/069397a81dcb254778ab2ce864bab992.png)
Пример векторного вывода. Здесь можно увидеть отдельные пути муравьёв. Там, где прошло много муравьёв, немного накладывающиеся друг на друга линии образую более широкие пути.
Соединяем точки
Я знала, что хотела отрисовать муравьёв, путешествующих между множеством точек, поэтому одним из первых стал код для компоновки нескольких симуляций в одно изображение. Но что же тогда мне рисовать?
Сначала я решила создать очень буквальные графы: начав с простых двоичных деревьев, перейти потом к более сложным визуализациям. Это казалось естественным шагом, ведь оптимизация муравьиной колонии решает задачи поиска путей в графах. Ещё я подумала, что это будет интересным способом визуализации сложности кода: почему бы не взять UML-диаграмму или граф зависимостей и не отрендерить их при помощи муравьёв?
Я уже была знакома с Graphviz, поэтому решила использовать этот набор инструментов и язык описания графов DOT для задания узлов и рёбер моей симуляции. Graphviz имеет режим, выводящий файл DOT с аннотациями координат пикселей. Я написала очень уродливый парсер файлов DOT и использовала его с аннотированным файлом DOT для симулирования местоположений муравейников и пищи.
Эксперименты с двоичными деревьями показались многообещающими и придавали очень естественный, органический внешний вид.
![](https://habrastorage.org/getpro/habr/post_images/971/59e/e53/97159ee533223d92707a989ba83c10c3.png)
Простое двоичное дерево. Мне сказали, что оно походит на ангиограмму.
![](https://habrastorage.org/getpro/habr/post_images/278/845/f30/278845f30db3fab5dc9085c6261130b7.png)
Немного более сложное дерево, уже довольно глубокое.
Затем я начала строить графы побольше, используя в качестве входных данных различные кодовые базы. Я написала несколько простых скриптов на Python: один превращал git-дерево в файл DOT, другой превращал зависимости импорта C в файл DOT.
![](https://habrastorage.org/getpro/habr/post_images/d41/699/426/d41699426c3cf2e31c97b2ee429dc34b.png)
Граф объектов в дереве объектов git, нарисованный муравьями.
![](https://habrastorage.org/getpro/habr/post_images/813/525/30d/81352530da26c9e3cdf334d6909c479e.png)
Зависимости между файлами в ядре Linux. Узлы и рёбра были созданы при помощи квадратного стиля графов Graphviz. На самом деле, ненамного интереснее случайных графов.
Хотя все эти графы интересны и определённо сложны, меня разочаровало то, что на самом деле они ничего не говорили об общей форме кодовых баз, на основе которых были построены. Чем больше я экспериментировала с визуализацией кода, тем больше осознавала, что построение интересного графа из кодовой базы само по себе является отдельной, более сложной задачей. Однако мне понравилась сложность очень больших графов и позже я к этому снова вернулась.
Моим следующим экспериментом стали игры с простыми формами. Я создавала графики из линий, окружностей, синусоид и других фигур, которые легко описать при помощи узлов и рёбер.
![](https://habrastorage.org/getpro/habr/post_images/fab/5f3/287/fab5f32876434586bafc780db2d897d9.png)
Точки на отрезке, в правой части отрезка точки расположены ближе друг к другу.
![](https://habrastorage.org/getpro/habr/post_images/2d5/8e5/ef1/2d58e5ef1de0f74706ee2e47321b94d0.png)
Различные частоты синусоиды. Полагаю, из муравьёв выйдет вполне неплохой осциллограф.
Наиболее интересными мне показались простые триангулированные пространства. Я сгенерировала множество равномерно распределённых точек — или случайным образом, или рисованием фигур — а затем использовала библиотеку Processing, чтобы превратить эти точки в триангуляцию Делоне или диаграмму Вороного. Затем получившиеся рёбра были использованы для симуляции муравьёв, где каждое ребро обозначало один «муравейник» или «пищу».
![](https://habrastorage.org/getpro/habr/post_images/59e/d31/366/59ed31366bcf08b906a07e476152a66c.png)
Нарисованная муравьями диаграмма Вороного.
Это привело к появлению красивого полного пространства сложных муравьиных хитросплетений, которое гораздо лучше описывало интересующую меня сложность.
Наконец, я подошла к задаче под ещё одним углом. Один друг взглянул на симуляцию и спросил, что случится, когда муравьи столкнутся со стеной — смогут ли они обходить простые препятствия? Мой код уже умел обрабатывать стены как пограничные случаи, поэтому я просто добавила внутренние стены, а потом потратила много времени, пытаясь научить муравьёв решать лабиринты.
![](https://habrastorage.org/getpro/habr/post_images/e74/803/088/e74803088c3d09ddb1b2b77902004c72.png)
Пути муравьёв, пытающихся решить простой лабиринт. Вы можете увидеть форму лабиринта, заметив, куда муравьи не могут пройти.
У меня была задумка, что если муравьи могут решать простые лабиринты, то можно объединить их вместе, чтобы создать более масштабную работу. Я потратила много времени на настройку переменных симуляции, чтобы муравьи могли решать их, но мне так и не удалось заставить их решать лабиринты стабильно. В конечном итоге всё это превратилось просто в завитки муравьиных путей, ограниченные формой самого лабиринта.
Готовое произведение искусства
На этом этапе я решила сделать шаг назад и рассмотреть выходные данные всех своих экспериментов. Я поняла, что самые интересные изображения получались из больших полей полуслучайных точек и рёбер, и решила сделать это своим окончательным решением, настроив симуляцию на отрисовку линий между триангуляцией Делоне случайных точек.
![](https://habrastorage.org/getpro/habr/post_images/3b3/09f/a33/3b309fa331b59c059e4b722d4e4c7c10.png)
Завершённый прогон симуляции. Он содержит множество наложенных друг на друга путей, из которых получаются нечёткие пятна.
Последняя проблема заключалась в том, как превратить изгибы SVG в готовую работу. Из экспериментов я знала, что хочу каким-то образом сортировать пути, чтобы выделить пути с красивой формой. Но прогон готовой симуляции занимал один-два часа, из-за чего изменять переменные при каждом прогоне эксперимента было неудобно.
Я решила написать вторую диаграмму Processing, которая будет загружать вывод симуляции в SVG, а затем применять нужные мне визуальные эффекты. Более того, я хотела сделать скрипт постобработки интерактивным, чтобы можно было экспериментировать с разными весами и цветами линий, а также порогами сортировки.
Я попробовала несколько разных способов оценки путей, которые должны быть на переднем и на заднем плане. Были вычислены несколько различных факторов: количество самопересечений линии, количество пересечений линией её линии уклона и вероятность того, что линия будет следовать по уклону, предсказанному предыдущими двумя точками.
Я использовала скрипт постобработки для экспериментов с разными весами и значениями этих оценок, пока не добилась нужного мне внешнего вида.
![](https://habrastorage.org/getpro/habr/post_images/6ac/8a0/5e7/6ac8a05e7e250a030461dab605e0770f.gif)
Настройка порога для передних и фоновых линий.
На этом этапе очень помогло сохранение изображения при изменении каждой переменной. Когда я приближалась к нужному мне изображению, было намного проще сравнивать ряд незначительных вариаций, чем менять несколько факторов за раз.
После длительной настройки и внесения небольших изменений я создала из своей симуляции такое изображение:
![](https://habrastorage.org/getpro/habr/post_images/781/a92/940/781a92940d65d658abfd788b7e0a27db.jpg)
Я приблизила область, которая показалась мне наиболее интересной, и откадрировала её для создания хорошего баланса между пустым и заполненным пространством.
Последним этапом был выбор способа превращения этого изображения в физический объект. Раньше я печатала их цифровым образом как постер размером 40×50 см и предприняла попытку (неудачную) печати экрана на цветной бумаге. Постер с цифровой печатью выглядит отлично, но в дальнейшем я хочу скопировать изображение как часть картины. Я нахожу сложные рисунки медитативными и думаю, что смогу добиться интересных эффектов, отрисовывая их вручную.
На этот проект было потрачено намного больше времени, чем я ожидала, и он оказался сложнее, чем представлялось в начале. Но это отличный способ экспериментирования со всевозможной вычислительной геометрией и алгоритмическими задачами. Думаю, довольно иронично, что я написала несколько тысяч строк кода для работы, посвящённой сложности, но довольна тем, что она выглядит круто и говорит сама за себя.