Implementaion of the genetic algorithm – mutation

Here I will give some details on how the current implementation of the genetic algorithm works.
The genetic code for each creature is structured as a Dna object, this object contains an array called chromosomes where each position holds a 2D vector, and it also contains an integer value representing how long the chromosomes array is. As mentioned on a previous post, this vectors are used to determine each of the creature’s jumps.
When a new creature is created their Dna is also created and initialized. For the initialization the amount of vectors is the only information required. After that the vectors on the array will be filled with random values within a predetermined range. This range is determined by a global variable that will be referred to as maximum initial impulse.
Given that the maximum initial impulse is 3, one possible Dna could look like this:

Amount of Dna code:

3

Chromosomes:

Pos. 0	Pos. 1	Pos. 2
x = 2.3	x = 1.2	x = -2.8
y = -1.2	y = -2.6	y = -0.5

As these values are intended to compose the impulse that makes the creature jump when applied to its body, the Y value of every vector has to be always negative (a positive value would make the creature launch itself onto the ground and the resulting “jump” would actually be due to the creature’s bounce on the floor. It would not look very physically realistic and also most of the impulse would be lost).

Mutation

When mutation is applied to a Dna a chance of mutation and an amount of mutation has to be provided. In the case of version 0.3, the chance is 50%, and the amount is also 50%. What this means is that there is a 50% chance of each jump (vector) being mutated and when it is, the resulting value will be the previous plus a random value between -50% and 50% of the maximum initial impulse.

A possible mutated version of the previous Dna example, considering the chance of mutating and the amount of mutation both equals to 50%, could be this:

Pos. 0	Pos. 1	Pos. 2
x = 2.3 (not changed)	x = 1.8 (mutated: 1.2 + 0.6)	x = -2.8 (not changed)
y = -1.2 (not changed)	y = -3.5 (mutated: -2.6 + (-0.9))	y = -0.5 (not changed)

On the example only the second position (jump) was mutated (there was a 50% chance of this happening).
This is what happened to X:
Mutated X = previous X + (maximum initial impulse * random value between -50% and 50%)
Mutated X = 1.2 + (3 * 20%)
Mutated X = 1.8
And to Y:
Mutated Y = previous Y + (maximum initial impulse * random value between -50% and 50%)
Mutated Y = -2.6 + (3 * (-30%))
Mutated Y = -3.5

First playable version

First playable version

Version 0.3 can be sort of played here.

The point is to reach the rotating blue square, but if you manage to do that, nothing will happen, actually…

You can switch between creatures using the number keys and then hit Space to see them jump. If you think those were good jumps, hit Enter and nine new creatures will be created from the one you chose. By repeating this process you should, after some generations, shape the creatures’ jumps so that at least one of them is able to reach the blue square.

A bit about the implementation

The creatures

The shape of a creature in this game is intended to be oval, so to the way used to create a creature’s body, so that is can collide with the static objects in the level, was giving the creature two shapes: one big circle at the bottom and one small one at the top. Later I will be able to put an oval sprite with the art representing the creature’s appearance over this body made of two circles. They will overlap nicely enough so that the sprite will appear to be colliding with the other objects in the level.

After doing this initial setup for a creature’s body I noticed that it was taking a very long time for the creature to stop moving after a jump. As I was allowing a creature to jump only after it stopped moving completely, this became a problem. What I did then was add a trapezoidal shape to the bottom of the creature and make it a hundred times more dense than the other circular shapes. On top of giving the creature’s body a straight base it also gave it a tumbler toy-like behavior, meaning that creature would most of the times and up standing up straight after a jump.

As for the way the creature’s jumps, it was done by applying an impulse to the creature’s body. The impulse is given in the form of a 2D vector with the Y value being negative, so that the impulse is always upwards. This brings us to the next topic which is about what these jump-determining vectors really represent in the game.

The DNA code

For now the only thing that differentiates one creature from the other is how they jump, that is, what are the amplitude and direction of each jump. As we know, these jumps are determined by 2D vectors. Having that in mind it appeared logical to make these vectors the creature’s DNA code. This way, whenever a creature has to be mutated, their vectors’ values are changed somehow, and whenever two creatures mate, some crossover method is applied to their vectors.

Details about what happens to the DNA code when creatures mutate and mate are subject to another topic.

Obs.: Even though mating is mentioned here (for it is implemented already), it cannot be observed on version 0.3 of the game.

How will the game look like?

To answer that question, even to myself, and to have a better idea of how the game mechanics will be I made a series of drawings. Here they are:

1. Level and initial creatures

Here the level can be seen and the generated creatures are represented inside squares on a row at the top left of the drawing. Each creature is identified by a number.

2. Third creature after its trial

Here a creature is shown in the level after jumping five times. It is the third one, as the arrow on the top left is showing. Thin arrows illustrate the trajectory of each random jump previously performed by the creature.

3. The player selects the winning creatures

Here the player drags creature number 7 to a slot on the column to the right, where the selected creatures will be. As shown on the next drawing, the player can choose the same creature several times by dragging it to more than one slot (if the player could only choose any given creature once, the selected set would be the same as the original set).

5. All slots filled and ready for the next generation

With all the slots filled, the player has the option of going to the next generation. The next generation will be formed by nine new creatures, each one based on the corresponding creature on the slots to the right. Taking the drawing above as example, the new creature on slot 1 on the generation to come will be a possibly mutated version of creature 7, because creature 7 is the one occupying the first slot on the column to the right.

Here we should note that the player was able to drag two creatures into one single slot, instead of just one (on the column to the right containing the selected creatures, notice the slots that have the word “mate” in front of them). In this case, the two creatures will mate in order to make the new creature, and then the new creature will be subject to mutation just as the ones bred from one single creature.

Very early stage prototype

After doing some drawings to figure out how a level of Evolution Nine should look like, I used Box2D to draw what could be the first level and then put a rectangle jumping about randomly on it.

First I did it by creating one more test to the Box2D Testbed application, but after switching the project from Box2D/C++ to Box2dWeb/JavaScript on HTML5’s canvas I rewrote it accordingly.

Here is what it looked like:

I did this by modifying the demo.html file included with Box2dWeb.

A link for a newer version of this prototype will be up soon.

First test with genetic algorithms

What can be seen on the video are 10 lines that evolve so that their tips get closer to the target. When the target is moved by the user, the lines follow.
After every frame the best 5 lines, that is, the lines with tips closer to the target, are selected to continue to the next frame. They are duplicated and all of them are subjected to mutation. When the lines get mutated their joints’ angles change a little. Before the next frame the selection of the 5 best happens again and the process repeats. This process drives the lines’ tips closer and closer to the target.

On the video you can see all the lines being reset several times. When this happens they all are regenerated and start with totally random positions but quickly converge towards the target again. It can also be observed that the number of joints are increased and decreased sometimes, and some aspects of the drawing are changed (curved lines are replaced by straight lines, black dots appear on every joint).

This is my first experiment with genetic algorithms. This application was done so that I could put to practice some of the basic principles of genetic algorithms and also learn more about them.

After I came to the idea of making a platform game using genetic simulation on it, making a test applications using those algorithms was a good way to see them working in practice and start having ideas of how to use them on the actual game.

The application was made in Xcode using openframeworks with a modified version of the ofxDna add-on.

Proposal submitted

Today the project proposal was submitted to Dr. Mick Grierson as part of the assignment.
It can be downloaded here.