Desenhar com formigas: imagens procedurais usando algoritmos de otimização de colônias de formigas

Por que eu queria desenhar com formigas

Eu queria criar uma obra de arte explorando a complexidade do design de software. Quando apresento uma enorme base de códigos, penso na complexidade que surge independentemente e nas partes interconectadas e interconectadas. Sua forma geral, por assim dizer, surge das ações de muitas personalidades individuais.

Eu estava pensando em como apresentar isso graficamente, e uma das imagens que encontrou uma resposta em mim foi a imagem de uma colônia de formigas. As formigas são um ótimo exemplo de complexidade emergente (emergente). Nenhuma formiga é um arquiteto, mas juntos eles constroem estruturas complexas magníficas.

Esquema de formicária. Fonte: Wikimedia Commons .

Comecei procurando informações sobre simulações de colônias de formigas. Obviamente, há literatura sobre isso, e é bonito . Mas o truque era que os formigueiros surgem em parte, dependendo da física da areia e da terra em que são construídos - porque sua criação depende de como a partícula será localizada quando a formiga a colocar. Eu queria criar algo em 2D, então tentei ir direto para a simulação sem escrever o código da física da areia, ou seja, tive que abandonar a simulação física do formigueiro.

Por causa disso, comecei a pesquisar novamente e eles me levaram a uma classe completamente diferente de simulações de formigas:algoritmos de otimização de colônia de formigas (algoritmos de colônia de formigas) .

A otimização de colônias de formigas é um algoritmo de agente usado para resolver o problema de encontrar o caminho mais curto entre dois pontos de um gráfico. "Agente" significa que o algoritmo consiste em procedimentos separados (neste caso, "formigas"), cujo comportamento emergente resolve o problema.

Funciona de maneira muito simples. Cada formiga deixa um rastro de “feromônios” em seu caminho. As formigas deixam um tipo de feromônio depois de sair do formigueiro e o outro quando encontram comida. As formigas que procuram comida procuram encontrar um traço de um feromônio "alimentar", enquanto as que procuram formigueiro procuram um traço de um feromônio "doméstico".

As formigas que se encontram em um caminho mais curto são capazes de percorrer mais rapidamente de casa até a comida e vice-versa. Isso significa que eles criarão uma camada mais saturada de feromônios. Formigas que se movem por mais tempo preferem uma trilha mais rica e se movem por um caminho mais curto. Cada formiga trabalha de acordo com regras muito simples, mas com o tempo as formigas encontram um caminho mais ideal entre dois pontos.

Simulação

Eu escrevi meu simulador de formigas no Processing 3. Comecei minha própria implementação simulando o código desta postagem incrível de Gregory Brown .

Depois que as formigas começaram a se mover, comecei a expandir e modificar o código para que funcionasse melhor em grades de pixels maiores. Eu queria obter simulações interessantes (não necessariamente eficazes ) e isso determinou meu trabalho no código. Criei uma visão muito rudimentar para as formigas, para que cada formiga possa ver vários pixels à frente. Acrescentei a morte e o renascimento das formigas para que elas não se dispersem aleatoriamente pelo espaço. Por fim, tornei as formigas um pouco mais estúpidas: elas deixam o feromônio constantemente, mesmo que a pesquisa não tenha sido bem-sucedida, o que é semelhante ao comportamento real das formigas.

Aqui você pode jogar a porta de simulação em p5.js. diretamente no seu navegador!

Você também pode dar uma olhada no código-fonte portado no Github.

Acima de tudo, na simulação, fiquei fascinado pelas formas bonitas, estranhas e complexas criadas pelas formigas. Eles não marcham em linhas retas, mas formam laços, curvas e galhos. Ainda mais interessante é que você pode controlar a aparência das figuras criadas pelas formigas, alterando várias variáveis ​​do seu mundo. Por exemplo, você pode alterar a taxa de evaporação dos feromônios e o alcance da visão das formigas em pixels.

Transforme formigas em arte

Depois que a simulação começou a funcionar, o próximo passo foi estudar os dados que ela gera. Meu objetivo era criar algum tipo de imagem bidimensional, ou seja, eu precisava capturar e desenhar as figuras criadas pelas formigas.

No final, escrevi diferentes tipos de saída: vários tipos de saída raster e um vetor. Para capturar a saída raster, rastreei as células visitadas pelas formigas e a frequência de suas visitas. Depois de brincar com os filtros desta conclusão, você pode obter um rastro fantasmagórico dos lugares onde as formigas visitaram.

Um exemplo de saída raster. Os caminhos são muito mais largos ao longo dos populares trilhos de formigas e onde as formigas vagavam aleatoriamente ao redor do formigueiro.

A saída de varredura foi interessante, mas eu queria ver os caminhos individuais mais claramente, então explorei a possibilidade de exportar para svg. Para produção vetorial, salvei a história de cada formiga e, quando chegaram à comida ou ao formigueiro, escrevi essa história na lista. Para renderização, eu amostrava todos os caminhos salvos e os renderizava como uma série de curvas.

Um exemplo de saída vetorial. Aqui você pode ver os caminhos individuais das formigas. Onde existem muitas formigas, linhas ligeiramente sobrepostas formam caminhos mais amplos.

Ligue os pontos

Eu sabia que queria desenhar formigas viajando entre muitos pontos; portanto, o código para vincular várias simulações em uma imagem era um dos primeiros. Mas então o que devo desenhar?

No começo, decidi criar gráficos muito literais: começando com árvores binárias simples e depois passando para visualizações mais complexas. Pareceu um passo natural, porque a otimização da colônia de formigas resolve o problema de encontrar caminhos nos gráficos. Também pensei que seria uma maneira interessante de visualizar a complexidade do código: por que não pegar um diagrama UML ou gráfico de dependência e renderizá-los com formigas?

Eu já estava familiarizado com o Graphviz , então decidi usar este kit de ferramentas e a linguagem de descrição gráfica do DOTpara especificar os nós e as bordas da minha simulação. O Graphviz possui um modo que gera um arquivo DOT com anotações de coordenadas de pixel. Escrevi um analisador de arquivos DOT muito feio e o usei com um arquivo DOT anotado para simular locais de formigueiros e alimentos.

As experiências com árvores binárias pareciam promissoras e davam uma aparência muito natural e orgânica.

Uma simples árvore binária. Disseram-me que é como um angiograma.

Uma árvore um pouco mais complexa, já bastante profunda.

Então comecei a construir mais gráficos usando várias bases de código como entrada. Escrevi alguns scripts Python simples: um transformou a árvore do git em um arquivo DOT, o outro transformou as dependências de importação C em um arquivo DOT.

Gráfico de objetos na árvore de objetos git desenhada por formigas.

Dependências entre arquivos no kernel do Linux. Nós e arestas foram criados usando o estilo quadrado dos gráficos Graphviz. De fato, não é muito mais interessante do que gráficos aleatórios.

Embora todos esses gráficos sejam interessantes e definitivamente complexos, fiquei desapontado por eles não terem dito nada sobre a forma geral das bases de código nas quais foram construídas. Quanto mais experimentei a visualização de código, mais percebi que construir um gráfico interessante a partir de uma base de código é uma tarefa separada e mais difícil. No entanto, gostei da complexidade de gráficos muito grandes e depois voltei a isso novamente.

Meu próximo experimento foram jogos com formas simples. Criei gráficos a partir de linhas, círculos, sinusóides e outras formas fáceis de descrever com nós e arestas.

Os pontos no segmento, no lado direito do segmento, estão mais próximos um do outro.

Diferentes frequências de ondas senoidais. Suponho que um osciloscópio muito bom saia das formigas.

Os espaços triangulares mais simples me pareciam os mais interessantes. Gerei muitos pontos uniformemente distribuídos - aleatoriamente ou desenhando formas - e então usei a biblioteca Processing para transformar esses pontos em uma triangulação de Delaunay ou diagrama de Voronoi. Em seguida, as costelas resultantes foram usadas para simular formigas, onde cada costela denotava um “formigueiro” ou “comida”.

Desenhado pelo diagrama de formigas Voronoi.

Isso levou ao aparecimento de um belo espaço completo de complexas complexidades de formigas, que descreviam a complexidade que me interessa muito melhor.

Finalmente, aproximei a tarefa de outro ângulo. Um amigo olhou para a simulação e perguntou o que aconteceria quando as formigas colidissem com a parede - elas podem evitar obstáculos simples? Meu código já sabia como lidar com paredes como casos limítrofes, então adicionei paredes internas e passei muito tempo tentando ensinar formigas a resolver labirintos.

Os caminhos das formigas tentando resolver um labirinto simples. Você pode ver a forma do labirinto observando onde as formigas não podem ir.

Tive a ideia de que, se as formigas puderem resolver labirintos simples, você poderá combiná-las para criar um trabalho maior. Passei muito tempo configurando as variáveis ​​de simulação para que as formigas pudessem resolvê-las, mas ainda não consegui fazê-las resolver os labirintos de forma estável. No final, tudo isso se transformou em apenas cachos de caminhos de formigas, limitados pela forma do próprio labirinto.

Obra de arte finalizada

Nesse estágio, decidi dar um passo atrás e considerar o resultado de todas as minhas experiências. Percebi que as imagens mais interessantes foram obtidas de grandes campos de pontos e arestas semi-aleatórias e decidi tomar essa decisão final configurando a simulação para desenhar linhas entre a triangulação de pontos aleatórios em Delaunay.

Execução de simulação concluída. Ele contém muitos caminhos sobrepostos dos quais pontos difusos são obtidos.

A questão final foi como transformar dobras SVG em trabalhos concluídos. Com os experimentos, eu sabia que queria classificar os caminhos de alguma maneira para destacar caminhos com uma forma bonita. Mas a execução da simulação final levou de uma a duas horas, motivo pelo qual foi inconveniente alterar as variáveis ​​em cada execução do experimento.

Decidi escrever um segundo diagrama de processamento que carregará a saída da simulação no SVG e aplicaria os efeitos visuais necessários. Além disso, eu queria tornar o script de pós-processamento interativo para que eu pudesse experimentar diferentes pesos e cores de linhas, além de classificar limites.

Tentei várias maneiras diferentes de avaliar os caminhos que deveriam estar em primeiro plano e em segundo plano. Vários fatores diferentes foram calculados: o número de auto-interseções da linha, o número de interseções pela linha de sua linha de inclinação e a probabilidade de a linha seguir a inclinação prevista pelos dois pontos anteriores.

Usei o script de pós-processamento para experimentos com diferentes pesos e valores dessas estimativas, até obter a aparência necessária.

Configuração de limite para as linhas frontal e de fundo.

Nesse ponto, salvar a imagem ao alterar cada variável ajudou muito. Quando me aproximei da imagem de que precisava, era muito mais fácil comparar uma série de pequenas variações do que alterar vários fatores ao mesmo tempo.

Após uma longa configuração e fazendo pequenas alterações, criei a seguinte imagem da minha simulação:

Aumentei o zoom na área que me parecia mais interessante e a recortei para criar um bom equilíbrio entre o espaço vazio e o preenchido.

O último passo foi a escolha de como transformar essa imagem em um objeto físico. Eu costumava imprimi-los digitalmente como um pôster de 40 × 50 cm e tentei (sem sucesso) imprimir a tela em papel colorido. Um pôster impresso digital parece ótimo, mas no futuro eu quero copiar a imagem como parte da imagem. Acho desenhos complexos meditativos e acho que posso conseguir efeitos interessantes desenhando-os manualmente.

Muito mais tempo foi gasto neste projeto do que eu esperava, e acabou sendo mais complicado do que parecia no começo. Mas essa é uma ótima maneira de experimentar todos os tipos de geometria computacional e problemas algorítmicos. Eu acho que é bastante irônico que eu escrevi vários milhares de linhas de código para trabalhar com complexidade, mas estou satisfeito por parecer legal e falar por si.

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