Nanolife: Evolução, vida artificial e maquinas de Turing.

    A alguns meses atrás, pesquisando sobre vida artificial encontrei um projeto chamado Nanopond. Um simulador de vida artificial com uma ideia muito interessante. O programa roda uma matriz, onde os espaços vazios podem ser ocupados por "celulas". Cada célula é uma maquina de Turing, pois seu código genético é lido como um programa. Tal código genético é escrito numa linguagem parecida com brainfuck, que já foi várias vezes comprovado ser uma linguagem Turing Completa. Então, teoricamente, cada célula pode fazer tudo o que um computador faz. Mas além dos comandos básicos da linguagem brainfuck, este código genético tem comandos que essa célula executará, como se reproduzir ou girar 90°. Com esses comandos básicos e um pouco de tempo de computação resultados, no mínimo, interessantes aparecem, verdadeiras colônias de células começam a emergir até um ponto que falta espaço e alimento. Nesse momento a competição começa e é possível ver a seleção natural agindo em tempo real.
    Inspirado com esse programa, resolvi criar uma versão minha desse, com algumas modificações, que ao meu ver deixam a coisa um pouco mais interessante.
Na minha versão cada célula tem um código genético como a versão original, uma array, que serve de memória, inicialmente preenchida por zeros, um valor que determina a posição atual da memória (memoria[valor]), outro valor que determina a energia que essa célula tem e outro valor que determina o tempo restante de vida dessa célula (valor que é igual para todas as células). Há 9 tipos de "opcodes genéticos", que são executados a cada turno do programa. Tais comandos são: adiciona ou subtrai 1 do index da memória; adiciona ou subtrai 1 do valor da memória em que o index aponta; abre ou fecha um loop while; verifica se a célula em frente é compatível (a compatibilidade é verificada pegando 4 index randômicos e verifica-se se o valor do código genético nesses endereços são iguais entre as 2 células), se for compatível o valor no endereço atual da memória é igual a 1, se não for compatível ou for um espaço vazio o endereço da memória é 0; o endereço da memória é igual a rotação (0 - de frente para direita, 1 - para cima, 2 - para esquerda e 3 - para baixo); e por ultimo um comando que lê o valor que está no endereço atual da memória. Dependendo o valor que estiver nesse endereço a célula toma alguma ação, consumindo energia.
Se o for valor no endereço atual da memória for:

1. A célula gira no sentido horário.
2. A célula gira no sentido anti-horário.
3. A célula move um pixel para a direção que está virada.
4. A célula move um pixel para a direção contrária a que está virada.
5. A célula cria uma cópia quase(mutação) idêntica de si mesma à sua frente e dá 1/5 de sua energia para ela.
6. A célula pega metade da energia da célula à sua frente.
7. A célula tenta dividir sua energia com a célula à frente, é somada a energia dessas 2 células e é dividia entre as duas (média aritmética).

    A cada turno é verificado o tempo de vida e a quantidade de energia de cada célula, se em um momento a célula tiver idade maior que um valor predeterminado ou sua energia for menor ou igual a zero, essa célula será deletada. Energia é adicionada ao sistema criando novas células com código genético randômico a cada turno.

20 minutos de simulação, e já é possível ver uma colônia com um padrão bem evidente.

    Como é um programa simples, com complexidade O(n) e foi implementado em C não há problemas com velocidade (a simulação roda com 500.000 células a 1 FPS). Após 20 minutos rodando o programa já é possível ver colonias adaptadas (imagem à cima). Normalmente demora um tempo até aparecer alguma espécie que consiga vingar, mas depois que o processo começa a espécia tende a super população, limitada somente pela disponibilidade de alimento e espaço. Logo a mutação começa a agir e grupos de células começam a desenvolver novos comportamentos. Até o ponto que começam a competir com os outros grupos. Formando assim uma nova espécie.
Imagens:

2 espécies evidentes ainda se expandindo.

Código fonte no github (Sobre GPLv3 - Mateus Zitelli).

L-System em Python

Nesse fim de semana fiz mais um dos meus projetos. Estava já a um tempo vendo sobre fractais, sempre fui fascinado pela teoria do caos, e não precisou muito para que os fractais chamassem minha atenção. Fiz um gerador do fractal de mandelbrot. E quando vi sobre L-System achei incrível. Para que não sabe L-System é uma gramática formal, que com ela é possível criar algoritmos para arvores até para um floco de neve. L-System funciona assim:

1.  É passado o estado inicial, por exemplo uma string "F" que chamaremos de string_inicial.
2. Logo depois são criadas regras, por exemplo, substituir onde há "F" na string_inicial por "F+F-F-F+F".
3. Fazemos o processo de substituição por N vezes. Perceba que quanto maior N mais complexo vai ser nossa string.
4. Depois de gerar a string final após as N substituições, essa string vai ser interpretada caracter por caracter e gerará uma imagem. O processo mais comum é que "F" seja uma linha reta, "+" seja somar um anglo determinado ao ângulo da última reta para a próxima reta - Por exemplo, a última reta era horizontal (90°) e o ângulo determinado pra esse sistema é 30°, a próxima reta terá um anglo de 120° - e "-" subtrai o ângulo determinado do ângulo da reta anterior.

Esse é basicamente o L-System, temos também caracteres como "[" e "]", onde "[" salva os valores atuais de anglo e localização da última linha e "]" retoma esses valores para a próxima linha.
Segue alguns exemplos:

Triângulo de Sierpinski:

• Início = "F"
• Regra = "F" => "F+F-F-F+F"
• Ângulos das curvas = 240° 
• Complexidade = 6

Variante da Curva de Koch:

• Início = "F"
• Regra = "F" => "F+F-F-F+F"
• Ângulo das curvas = 270°
• Complexidade = 6

Planta Fractal:

• Início = "F"
• Regra = "F" => "FF-[-F+F+F]+[+F-F-F]"
• Ângulo das curvas = 22.5°
• Complexidade = 4

Obs.:As cores das linhas veriam de acordo com o ângulo que elas formam com a base da figura.

As duas primeira imagens tem o mesmo início e a mesma regra, o que muda é somente o ângulo, gerando uma imagem bem diferente. A complexidade dos sistemas é quantas substituições consecutivas elas geram. Um exemplo de como o tamanho do sistema cresce de forma exponencial em relação a complexidade está aqui:

• Complexidade 1 => "F"
• Complexidade 2 => "F+F-F-F+F"
• Complexidade 3 => "F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F"
• Complexidade 4 => "F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F+F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F-F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F-F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F+F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F"

Para quem estiver interessado, segue o script em python: script L-System(Necessita da biblioteca PyGame).

No próximo post (provavelmente no sábado), postarei novidades usando o L-System.

Big Bang

Esse é o meu primeiro post aqui no MZ Experiments e aqui falarei o que esse blog será e o motivo de ele existir.

Meu nome é Mateus Zitelli (Dai o nome MZ Experimets), tenho 16 anos, sou estudante de ensino médio. Sempre fui muito curioso com tudo, então com o tempo desenvolvi muitos Hobbies, como por exemplo: Estudar Astronomia, Física (matérias extra curriculares, sem ligação com a escola), matemática (também extra curricular) e como meu principal Hobbie a programação. Venho ao longo de 2 anos frequentemente estudando linguagens e fazendo programinhas, simplesmente peguei o tempo que usava pra jogar MMORPG's para programar. Sinceramente acho muito mais divertido e sem dúvida mais produtivo.

Esse blog será meu mural, onde colocarei minhas idéias, meus programas, abertos a todos. E espero que receba críticas, elogios e principalmente conheça pessoas novas com os mesmos interesses.

Imagem do meu ultimo projetinho de fim
de semana (Tema do próximo post).