Image Evolution with Genetic Algorithms

After reading up on some fantastic work in the field of Genetic Algorithms by Karl Sims I thought I'd give implementing his ideas in flash a go.

First and foremost, click the image below to run the application, left click to select the strongest genotype, control click to randomly mutate an image, and shift click to save an image you like...

There were three specific challenges that had to be tackled when working with evolving images. Firstly how to convert DNA into an image, secondly how to cross breed sets of DNA and thirdly how to mutate DNA effectively.

Each gene on a set of DNA is stored as a reference to a function (in this case a Pixelbender shader) and a seed integer. There are 3 types of gene, generators, combiners and affectors. Generators create an image from a blank canvas, affectors transform an image in some way while combiners merge a generated image with another image. Currently there are 5 combine functions, 10 generators and 14 affectors in total, so a choice of 29 genes each with some set of parameters based on a seed value.

In order to generate an image from a set of DNA then, the phenotype of a gene is calculated by applying that gene's function in order. The range of images that can be produced from such an image is impressive to say the least. Here are some examples:

To breed an image two sets of DNA are compared to each other, there is simply a 50% chance of the new DNA choosing a gene from one set and a 50% chance of choosing that gene from the other set.

Mutations work in a similar way, all genes have the potential to mutate with some probability, if they mutate quite marked changes in the phenotype can be seen. Here is an example of a set of images from the same genotype with minor mutations:

Anyway have a play around and let me know if you manage to evolve any cool images!

Update: here is a typical evolution route:

Update: Colourful Turtle

In my last experiment I recreated a turtle vector drawing program, with a simple interface. I'll post a small update to that which adds some color to the output. Here are some screenshots, as usual click the first one to launch the image, and source code can be found at the bottom, enjoy and let me know if you make anything pretty!

Source:

package org.experimentalized
{
 import flash.display.Sprite;
 import flash.events.Event;
 import flash.events.KeyboardEvent;
 import flash.display.Graphics;
 import flash.text.TextField;
 import flash.text.TextFieldType;
 import flash.geom.Rectangle;
 import flash.utils.getTimer;

 [SWF(width='550',height='550',backgroundColor='#000000',frameRate='30')]

 public class Turtle extends Sprite
 {
  private var commandstring:String = new String("mv:30,lt:90,mv:10,rt:30");
  private var S:Sprite = new Sprite();
  private var Angle:Number = new Number(0);

  private var X:Number = 0;
  private var Y:Number = 0;

  private var R:int = 0;
  private var G:int = 0;
  private var B:int = 0;


  private var input:TextField = new TextField();

  
  private function newrun(e:KeyboardEvent):void
  {
    commandstring = input.text;
    S.graphics.clear();
    S.graphics.lineStyle(1,0xFFFFFF);
    S.graphics.moveTo(0,0);
    Angle = 0;
    X = 0;
    Y = 0;
  }

  public function Turtle():void
  {
   addEventListener(KeyboardEvent.KEY_DOWN, newrun);
  
   addChild(S);

   input.width = 530;
   input.height = 20;
                 input.x = 10;
                 input.y = 10;
                 input.background = true;
                 input.backgroundColor = 0xFFFFFF;
   input.type = TextFieldType.INPUT;
   
   input.text = commandstring;


   addChild(input);

   S.x = 275;
   S.y = 200;
      
   this.addEventListener(Event.ENTER_FRAME, handler);
  }
  
  private function handler(e:Event):void
  {
   R = int(128 * (1 + Math.cos(getTimer()/1000-0.8981)));
   G = int(128 * (1 + Math.sin(getTimer()/7473-0.3812)));
   B = int(128 * (1 + Math.sin(getTimer()/1273+0.1787)));
   
   var C:uint = (R<<16|G<<8|B);   
   
   S.graphics.lineStyle(1,C);
   var commands:Array = new Array();
   commandstring = commandstring.split(" ").join("");
   commands = commandstring.split(",");
   var i:int;

   for(i=0;i<commands.length;i++)
   {
    if(commands[i].charAt(0)=="m")
    {
     var dist:Number = Number(commands[i].split(" ").join("").split(":")[1]);
     X = X + dist*Math.cos(Angle);
     Y = Y + dist*Math.sin(Angle);
     S.graphics.lineTo(X,Y);
    }
    else if(commands[i].charAt(0)=="l")
    {
     var changeleft:Number = Number(commands[i].split(" ").join("").split(":")[1]);
     Angle -= Math.PI*changeleft/180;
     if(Angle<0) Angle += 2*Math.PI;
    }
    else if(commands[i].charAt(0)=="r")
    {
     var changeright:Number = Number(commands[i].split(" ").join("").split(":")[1]);
     Angle += Math.PI*changeright/180;
     if(Angle>Math.PI*2) Angle -= 2*Math.PI;
    }
   }
  

   //Resize to fit on the square after each iteration (purely aesthetic choice...)
   
   var Rect:Rectangle = S.getRect(S.parent);
   
   S.x += 275 - (Rect.x+Rect.width/2);
   S.y += 275 - (Rect.y+Rect.height/2);
   S.width = 550;
   S.height = 550;
  }
 }
}

Turtle: 30 minute experiment

I had recently been reminiscing about IT lessons in year 3 where we were allowed to play around with those Turtle vector drawing programs. I thought I'd write one and share the results as a quick break from revision. Although it can't do much at the moment (the only commands are forward, left and right) with a bit more work I'm sure it could be made into quite an exciting program. You'll find the source code below and as usual just click the top image to launch the experiment.

Source code:

package org.experimentalized
{
 import flash.display.Sprite;
 import flash.events.Event;
 import flash.events.KeyboardEvent;
 import flash.display.BitmapData;
 import flash.display.Bitmap;
 import flash.display.Graphics;
 import flash.text.TextField;
 import flash.text.TextFieldType;

 [SWF(width='550',height='400',backgroundColor='#000000',frameRate='30')]

 public class Turtle extends Sprite
 {
  

  private var commandstring:String = new String("mv:30,lt:90,mv:10,rt:30");
  private var S:Sprite = new Sprite();
  private var Angle:Number = new Number(0);

  private var X:Number = 0;
  private var Y:Number = 0;

  private var input:TextField = new TextField();

  
  private function newrun(e:KeyboardEvent):void
  {
    commandstring = input.text;
    S.graphics.clear();
    S.graphics.lineStyle(1,0xFFFFFF);
    S.graphics.moveTo(0,0);
    Angle = 0;
    X = 0;
    Y = 0;
  }

  public function Turtle():void
  {
   addEventListener(KeyboardEvent.KEY_DOWN, newrun);
  
   addChild(S);

   input.width = 530;
   input.height = 20;
                 input.x = 10;
                 input.y = 10;
                 input.background = true;
                 input.backgroundColor = 0xFFFFFF;
   input.type = TextFieldType.INPUT;
   
   input.text = commandstring;


   addChild(input);

   S.x = 275;
   S.y = 200;
   
   S.graphics.lineStyle(1,0xFFFFFF); 
   
   this.addEventListener(Event.ENTER_FRAME, handler);
  }
  
  private function handler(e:Event):void
  {
   var commands:Array = new Array();
   commandstring = commandstring.split(" ").join("");
   commands = commandstring.split(",");
   var i:int;

   for(i=0;i<commands.length;i++)
   {
    if(commands[i].charAt(0)=="m")
    {
     var dist:Number = Number(commands[i].split(" ").join("").split(":")[1]);
     X = X + dist*Math.cos(Angle);
     Y = Y + dist*Math.sin(Angle);
     S.graphics.lineTo(X,Y);
    }
    else if(commands[i].charAt(0)=="l")
    {
     var changeleft:Number = Number(commands[i].split(" ").join("").split(":")[1]);
     Angle -= Math.PI*changeleft/180;
     if(Angle<0) Angle += 2*Math.PI;
    }
    else if(commands[i].charAt(0)=="r")
    {
     var changeright:Number = Number(commands[i].split(" ").join("").split(":")[1]);
     Angle += Math.PI*changeright/180;
     if(Angle>Math.PI*2) Angle -= 2*Math.PI;
    }
   } 
  }
 }
}

To make the output lines automatically fit the stage use the following instead:

package org.experimentalized
{
 import flash.display.Sprite;
 import flash.events.Event;
 import flash.events.KeyboardEvent;
 import flash.display.Graphics;
 import flash.text.TextField;
 import flash.text.TextFieldType;
 import flash.geom.Rectangle;

 [SWF(width='550',height='550',backgroundColor='#000000',frameRate='30')]

 public class Turtle extends Sprite
 {
  private var commandstring:String = new String("mv:30,lt:90,mv:10,rt:30");
  private var S:Sprite = new Sprite();
  private var Angle:Number = new Number(0);

  private var X:Number = 0;
  private var Y:Number = 0;

  private var input:TextField = new TextField();
  
  private function newrun(e:KeyboardEvent):void
  {
    commandstring = input.text;
    S.graphics.clear();
    S.graphics.lineStyle(1,0xFFFFFF);
    S.graphics.moveTo(0,0);
    Angle = 0;
    X = 0;
    Y = 0;
  }

  public function Turtle():void
  {
   addEventListener(KeyboardEvent.KEY_DOWN, newrun);
  
   addChild(S);

   input.width = 530;
   input.height = 20;
                 input.x = 10;
                 input.y = 10;
                 input.background = true;
                 input.backgroundColor = 0xFFFFFF;
   input.type = TextFieldType.INPUT;
   
   input.text = commandstring;


   addChild(input);

   S.x = 275;
   S.y = 200;
      
   this.addEventListener(Event.ENTER_FRAME, handler);
  }
  
  private function handler(e:Event):void
  {
   
   S.graphics.lineStyle(1,0xFFFFFF);
   var commands:Array = new Array();
   commandstring = commandstring.split(" ").join("");
   commands = commandstring.split(",");
   var i:int;

   for(i=0;i<commands.length;i++)
   {
    if(commands[i].charAt(0)=="m")
    {
     var dist:Number = Number(commands[i].split(" ").join("").split(":")[1]);
     X = X + dist*Math.cos(Angle);
     Y = Y + dist*Math.sin(Angle);
     S.graphics.lineTo(X,Y);
    }
    else if(commands[i].charAt(0)=="l")
    {
     var changeleft:Number = Number(commands[i].split(" ").join("").split(":")[1]);
     Angle -= Math.PI*changeleft/180;
     if(Angle<0) Angle += 2*Math.PI;
    }
    else if(commands[i].charAt(0)=="r")
    {
     var changeright:Number = Number(commands[i].split(" ").join("").split(":")[1]);
     Angle += Math.PI*changeright/180;
     if(Angle>Math.PI*2) Angle -= 2*Math.PI;
    }
   }
  

   //Resize to fit on the square after each iteration (purely aesthetic choice...)
   
   var Rect:Rectangle = S.getRect(S.parent);
   
   S.x += 275 - (Rect.x+Rect.width/2);
   S.y += 275 - (Rect.y+Rect.height/2);
   S.width = 550;
   S.height = 550;
  }
 }
}

Generative Art

Just thought I'd have a quick look at creating some generative art after reading Karl Simms' paper on Artificial Evolution for Computer Graphics. Images are created by randomly acting various functions on a bitmap in some predetermined order. Functions might include gradients, convolution filters, shapes amongst others. At this stage I have only made a black and white version of the generator, but I'll look what I can do about a colour one sometime soon. Just click the first images to launch the app, click and click again to stop/start the generator. If you find some cool images just take a screenshot and email them to me.

Pedestrian Playground

Looking through one of my favourite books, Critical Mass, I came across a page I had been meaning to do some research into. The section of the book was on cellular automata, and the creation of complexity from simple rules. I mentioned a few posts ago about a paper I had read about solving the Travelling Salesman problem using ants. The travelling salesman solves the problem of getting between a number of towns using the shortest route possible. This is all well and good but the travelling salesman has an absolute answer, and in my opinion that immediately makes the problem slightly less interesting. The randomness of the human psyche is far more exciting, and the pedestrian motion created when you bring large groups of people together are often quite surprising. Take a look at the image below for example; the trails connect 3 points of interest

around a park. None of the paths join any of the 3 target locations in the most efficient way, yet after years of trampling down grass, and the slow fading of former trails, the most desired route (on average) is the one seen here.

Obviously park planners would have a much easier job keeping their lawns meticulous if they could somehow predetermine where people were most likely to walk, thus keeping pedestrians on the paths, and not trampling their grass. This problem is slightly more subtle than the travelling salesman, there are in fact  many solutions and they depend on a huge number of factors: how many people want to go to each destination, how fast does grass regrow, how fast does a path form, how many people commute along the paths each day, do people have to walk uphill, is there a fence...? Obviously the list goes on for quite a while, after all humans are not predictable, but we can still create a simple model.

The screenshots below show the main interface of my application, just click the first image to launch it. The number of target towns, and the number of people can be changed, as can the size of random fluctuations in direction, the effect of the destination on the direction walked, and the effect of the route on the direction walked. Two factors called visibility, and distance factor also affect the likelyhood that a pedestrian will take the most direct route to their destination. Have a play around with the factors and see if you can reproduce the pattern seen above.

In the below examples you can see paths merging, even though this is not the most efficient route for anyone. The first image still has some "visibility", the second has absolutely none, people just tend to congregate randomly, but it does make a nice pattern, and the third shows path splitting, where two similar but separate routes form spontaneously.

Terrain Generation

Time for another post and another experiment. I was just reading an interesting paper called Procedural Techniques For City Generation by some chaps in working at the ITB in ireland all about how to generate completely algorithmic city plans given a starting point and a landscape to build on. The image below shows an example of some of the stuff that can be produced with these algorithms and it truly is amazing!

Anyway I thought I'd step back a bit and try to produce some of my own landscapes to start with, and then move onto road generation and finally buildings. Its always nice to start with the easy stuff, that way I find at least I get something done!

Since the actionscript random function generates a new random seed each time a program is run I decided to use a custom random number function which could take a seed. The generator I used is the Park-Millar-Carter PRNG which is ideal for the job. I like the idea of using words (like in the original worms) as seeds so using an input string, eg "Terrain1" and then taking an MD5 hash of it, converting this into a number provided a constant seed for a word. The seed would generate every piece of information in the same way every time, very useful when you find an interesting image.

So I built this in then created several layers of bitmap data, each with different resolution with each pixel on each grid set to a random value (in the range [0,0xFF]). The resulting addition of all the bitmaps would produce the data for my final landscape. Here are a few examples of the kinds of landscapes I was able to produce:

To me the third image is a spitting image of europe, with spain, germany and france and even the UK to the very top left! I'm quite happy with the results all in all. To try out the app for yourselves just click here, enter a keyword, and press generate!

Next Step, build some roads!

My Fluid Dynamics Engine in AS3

This post and my recent experiments have been inspired largely by the work of Eugene Zatepyakin and that of Jos Stam on fluid dynamics.

Jos Stam's article on fluid dynamics for games started it all, having a similar effect on this area of research as Thomas Jakobsen's article had on the use of Verlet Integration in physics engines. The beauty of the fluid solver is that it provides a computationally quick and stable approach to simulation of fluid dynamics, which can be easily expanded into 3 dimensions and used to solve many more advanced problems.

Eugene Zatepyakin was the next step in the chain creating a fast engine in AS3 which I talked about in a previous post. I decided to write my own version of the engine and here it is:

The first example shows 4000 particles floating around in the simulated fluid - just click on it to launch to flash file - once it is running click and drag to make the fluid move.

The second example shows the pressure grid being used as a displacement filter for the image below. This starts to add a bit of realism and creates a more three dimensional feel.

Mandelbrot Explorer

As I've mentioned a few times now I've been working on an application for Windows called "Mandelbrot Explorer". Nothing special, just functional exploration of the mandelbrot and julia sets. This is what 3rd year physicists spend their time doing - a lot of C++!

Here are a few screen shots and an outputted jPeg file. The program is capable of producing high resolution "deep zoom" images of 1200 by 800 pixels. These can look amazing. It handles powers of the mandelbrot set, as well as different forms - including the amazing "Burning Ship" fractal.

Here are a few screenshots.

The classic Mandelbrot Cardiods

The burning ship fractal:

A high res output saved as a low quality jpeg

The Program is free of charge to anyone who wants it. Just send me a note and I'll provide download links! Enjoy the beauty of mathematics.

Strange Attractors - Drawing the universe

One of my university projects currently involves me writing a Mandelbrot Explorer application, which is yielding some fairly cool results. I've been looking at multiple dimensions and different forms of the mandelbrot set, which just reinforces my amazement every time I run it.

The mandelbrot is a fractal set, so I thought it might be interesting to look at some other fractal sets. Below is a representation of a Strange Attractor - technically a system with chaotic dynamics and a non-integer dimension. The whole program was written in just a few lines of code and it is actually fairly straight forward to work out, just like the Mandelbrot set, but the results are spectacular. It really does seem like the universe is being drawn out in front of you - and it is true that a lot of the patterns found in fractal mathematics do appear in the structures of macroscopic objects, for example in the spiral arms of galaxies, or in nebula cloud formation.

One amazing thing about the program is that there are more possible combinations of what you can see than there are particles in the universe. Current astronomers put the number of particles in the universe at somewhere between 10⁷² and 10⁸⁷a number quite easy to write down. With accurate enough numbers there are infinitely many manifestations of the strange attractor, but practically for an image with 2000x2000 resolution - as the program has, and 256 colours per pixel the number of manifestations are of the order of 256^4000000 which is an incomprehensible figure! And thats just using  256 colours - ie red or green or blue, and not the whole spectrum available.

These numbers are a little bit scary but it is nice to know that some consistency and calm arises out of these. Its not all white noise! Anyway take a look at the program - It is constantly evolving - and you'll never ever see the same thing more than once! Just click the image below to launch it.

Or click here or here to run it in green or blue!

Fluid Dynamics using AS3

As a physicist I find things like this incredible. Fluids are extremely complex mathematically, so when I came across Eugine Zatepuakin's work on fluid dynamics I was amazed by the speed and accuracy of the simulations!

Just click the right image for a full preview, you'll be blown away! When I've got a bit more time I'll write a thread explaining how fluid dynamics simulations work, and explain the basic principles of coding something like this in flash, but for now check it out!

Move your mouse around to create dense regions and click to change the rendering mode. I love that flash is capable of handling these kinds of calculations. I remember playing a game called plasma pong which used very similar fluid dynamics to Eugine's model. Unfortunately the game is no longer available for download because pong is a trademark of Atari but here is a nice little video of the game in action.

Here is a little youtube clip of the game, just click to launch it! :)

Enjoy!