For all programmers who are skilled in C-style languages, and beginners who fish for new experience with these!

Report article RSS Feed Programming Evolution, take one.

An introduction to programming software based on evolution.

Posted by moci on Mar 10th, 2011
Basic Client Side Coding.

Introduction

First let’s make sure we are all on the same page here. Earth wasn’t made 6000 years ago and all things on this planet were not created by some grand designer called “God” (or whatever you call him/her). We see evolution as Darwin explained it to us, everything starts somewhere and with more or less random mutation and survival of the fittest you get to the results you see today. With that out of the way, let’s continue.

The goal of this article is to create a simple program that will allow you to “evolve” something into something else. Evolution here means that we start with some form of DNA and we derive next generations from it by random mutation. In our program we are going to generate images from the DNA and the user will select which image is used as a basis for the next generation.

The coding itself will be done in ActionScript 3 but should translate well to other languages.

What we need

Everything is based from some sort of DNA. In our case DNA is a string of numbers. We need something that gives us a DNA string. At first it should be randomly generated but the next generation should be based on some previous DNA. We also need a way to randomly mutate any given DNA to produce a variation of it.

The other main function should be to generate an image out of a DNA string. An image consists of colors and points. This function should always generate the same image from the same DNA string. And any change in the DNA should have a maximum effect on the resulting image; this is also called the avalanche effect.

The program

The final program will look like this (without the text).

Evolution Take one, final solution.

The user will be able to click on any of the children which will generate the next generation based on the selected image and so forth. As you can see most of the children resemble the parent pretty closely, but with a closer look they should all have something different. Of course each generation can have some major changes as well. (Someone with 6 toes for example)

Let’s go

The theory behind this program is simple, but it’s interesting how you go about generating the DNA and the resulting image from that DNA string so I’ll explain how I approached this problem.

Generating the DNA string

The DNA represents everything about the image, a complete DNA string consists of several elements. In this case you could generate an image from a DNA with 10 elements, but it wouldn’t be anything interesting so we need “a lot” of elements. The elements in this example are integers that go from 0 to 9. Just like how our base DNA elements are A, C, G and T (look it up if you want to know more about our DNA).

We have to start somewhere so the first DNA string should be generated by itself, but the others are all derived from a previous DNA string. We can do this simply by adding a parameter in our function that defaults to null and check whether we have a “parent” or not.

If we are deriving from a previous DNA string, then we should allow a certain amount of mutations, we are assuming that evolution progresses in small steps and over a long time span (the other theory is that evolution happens in big steps over a short amount of time, people are still debating over this theory). We can also make sure that there is a certain degree of mutation.

Here’s the code:

actionscript code:
public function DNA(seed:DNA = null)
{
    //The DNA object will have fixed amount of elements
    _dna = new Vector.(200, true);
    //If we are using a seed, how many mutations can we get?
    var allowedMutations:int = 2;
    //Should we always mutate?
    var forceMutations:Boolean = true;
    //Keep a list of mutated elements
    var mutations:Vector. = new Vector.();
               
    //Generate the DNA object
    for (var i:int = 0; i < _dna.length; i++) {
        if (seed == null) {
            //If there is no seed, generate a completely new DNA object
            _dna[i]= generateDNAElement();
            allowedMutations = 0;
        } else {
            //If we are basing the new DNA on a previous one, there is a chance of mutation
            if (allowedMutations > 0 &amp;&amp; Math.random() * 20 == 10) {
                allowedMutations--;
                _dna[i]= generateDNAElement();
                mutations.push(i);
            } else {
                _dna[i]= seed.getElement(i);
            }
        }
    }
   
    //Make sure we have a certain amount of mutation, if needed
    if (forceMutations) {
        while (allowedMutations > 0) {
            allowedMutations--;
            var index:int = Math.random() * (_dna.length - 1);
            var newElement:int = generateDNAElement();
           
            //Make sure we are always mutation a new element
            while (mutations.indexOf(index) >= 0) {
                index = Math.random() * (_dna.length - 1);
            }
           
            //Make sure the mutated element isn't the same as the original
            while (newElement == _dna[index]) {
                newElement = generateDNAElement();
            }
           
            mutations.push(index);
            _dna[index] = newElement;
        }
    }
}

So now we have our DNA string and we can generate a mutated version by simply giving the original DNA string as a parameter in the constructor.

Generating the image

With the DNA string we are halfway done; the other half is visualizing it. From the DNA string, essentially a group of numbers, we need to derive coordinates and colors. I’ve tried a few ways of doing this and for now settled, the problem here is that we want to have some sort of avalanche effect when an element in the DNA string changes. This means we cannot simple group 1234 as x = 12 and y = 34, a rather boring image would result from that code.

Here’s what I do. The x value is the sum of a defined amount of numbers defined by squaring the current number, we modulo every step so it always falls in the range of the list. The y value is basically the same but instead of looking in the list from beginning to the end, for y you go from the end to the beginning. Here’s an example for a few x values:

Quote: 01234567
||||||||
list: 32462146
length: 8

Generating the first x coordinate we will need to sum up 3 values (list[0] = 3).
x = 0
x = x + list[3 mod 8] = 0 + list[1] = 0 + 2 = 2
x = x + list[2 mod 8] = 2 + list[4] = 2 + 2 = 4
x = x + list[4 mod 8] = 4 + list[0] = 4 + 0 = 4

Generating the second x coordinate we will need to sum up 2 values (list[1] = 2).
x = 0
x = x + list[3 mod 8] = 0 + list[1] = 0 + 2 = 2
x = x + list[2 mod 8] = 2 + list[4] = 2 + 2 = 4

Generating the third x coordinate we will need to sum up 4 values (list[3] = 4).
x = 0
x = x + list[3 mod 8] = 0 + list[1] = 0 + 2 = 2
x = x + list[2 mod 8] = 2 + list[4] = 2 + 2 = 4
x = x + list[4 mod 8] = 4 + list[0] = 4 + 0 = 4
x = x + list[6 mod 8] = 4 + list[4] = 4 + 4 = 8

Etc...


As a final step we multiply the x value and modulo it with 100, the same goes for the y value. Also notice that we are working without knowing the dimensions of the image. All coordinates will go from 0 to 100, which will make it pretty easy to rescale it to any given dimension.
To make our coordinates list a bit bigger (double it) we use the original set to make a “new” one. Where the x value is 100 – y and y is 100 – x.

Here’s the code:

actionscript code:
private function getCoordsFromDNA(dna:Vector.<int>, width:int, height:int):Vector.<Point>
{
    var ret:Vector.<Point> = new Vector.<Point>();
    var coordsFirst:Vector.<Point> = new Vector.<Point>();
    var coordsLast:Vector.<Point> = new Vector.<Point>();
   
    //For every element in the DNA object generate 2 (x, y) coordinates
    for (var i:int = 0; i < dna.length; i++) {
        var x:int = 0;
        var y:int = 0;
       
        //Generate the x value
        for (var j:int = 0; j < dna[i]; j++) {
            x += dna[(dna[j] * dna[j]) % dna.length];
        }
       
        //Generate the y value
        for (j = 0; j < dna[dna.length - 1 - dna[i]]; j++) {
            y += dna[dna.length - 1 - ((dna[j] * dna[j]) % dna.length)];
        }
       
        //Modulo with 100 so it's always between 0 and 100
        x = (x * dna[i]) % 100;
        y = (y * dna[dna.length - 1 - dna[i]]) % 100;
       
        //Add the generated coordinate and create an extra one as well
        coordsFirst.push(new Point(x, y));
        coordsLast.push(new Point(100 - y, 100 - x));
    }
   
    //Randomize these coordinates a bit and put them in one list
    for (i = 0; i < coordsLast.length; i++) {
        ret.push(coordsFirst[i]);
        ret.push(coordsLast[coordsLast.length - 1 - i]);
    }
   
    return ret;
}
 

Great, we’ve got our coordinates all we need is some color. As you know every pixel is divided in 3 values (4 with transparency) red, green and blue. The hexadecimal representation goes from 0x000000 to 0xFFFFFF (256 * 256 * 256 is about 16.5 million colors) and is set up as 0xRRGGBB. The way I generate the colors is far from ideal. It depends a lot from the coordinates (obviously because I use the coordinates to generate the colors…). I do get many color variations so for now this is good enough.

The idea behind this code is again to go from 0 to 100 (eventually from 0 to 255 because it gets multiplied by 0xFF). The R value looks at current coordinate value and at an offset from the end of the coordinate list. G does this as well, but switches the x and y values. I got B by playing with the values a bit until I got the right amount of color variation. I finally bit-shift the values and get them in the 0xRRGGBB format.

Here’s the code:

actionscript code:
private function getColorsFromCoords(coords:Vector.):Vector.
{
    var ret:Vector. = new Vector.();
   
    //For each pair of coordinates, generate some color value
    for (var i:int = 0; i < coords.length - 2; i += 2) {
        //Trying to randomize the color generation a bit
        var procR:Number = ((coords[i].x + coords[coords.length - 1 - i].y * 10) % 100) / 100;
        var procG:Number = ((coords[i].y * 10 + coords[coords.length - 1 - i].x) % 100) / 100;
        var procB:Number = (((coords[i].y * 2 + (coords[i].x) +
                            (coords[coords.length - 1 - i].x * 4 + coords[coords.length - 1 - i].y)) / 2) % 100) / 100;
       
        //All colors go from 0x000000 to 0xFFFFFF; bit-shift the R, G and B values into place
        ret.push(procR * 0xFF << 16 | procG * 0xFF << 8 | procB * 0xFF);
    }
   
    return ret;
}

To get a better idea look at the complete source code. I tried to get as much “randomization” without really using a random function. The code itself isn’t all that difficult, the evolution part here is that we can mutate a given input and get “major” changes in the output (images).

The only code needed for the application itself is to let the user select which image looks better and generate a new generation from that image. This process can go on forever. If you would keep a list of DNA strings, you could eventually print them out and see all the changes from generation to generation.

I hope you found this subject interesting, I did. This was a first try at creating something like this; the logical next step would be to evolve with some goal (in nature there is no goal, just improving what is already there).

To see other small tests check out my site: Mathiasverboven.net , there is no source code but you can always ask.

Have fun

Download the source here: Moddb.com

Post a Comment
click to sign in

You are not logged in, your comment will be anonymous unless you join the community today (totally free - or sign in with your social account on the right) which we encourage all contributors to do.

2000 characters limit; HTML formatting and smileys are not supported - text only

Established
Jul 20, 2010
Privacy
Public
Subscription
Open to all members
Contact
Send Message
Email
Members Only
Membership
Join this group
Group Watch
Track this group
Tutorial
Browse
Tutorials
Report Abuse
Report article
Related Groups
Curly Bracket Programming Realm
Curly Bracket Programming Realm Hobbies & Interests group with 74 members
Indie Devs
Indie Devs Hobbies & Interests group with 1,125 members
IntoGames
IntoGames Developer & Publisher