Saturday, March 21, 2009

My brain is open

This week was Brain Awareness Week. I found that my university was giving some lectures on the brain, so I attended them all. As expected, it was quite interesting. I knew the basic concepts from before, but it really helps to hear different people talk about different subtopics, as it gives me a fuller picture of how this wonderful organ works.

In any case, I couldn't help feeling inspired, so yesterday I started writing my very own brain simulator. No, it doesn't really do all that much. But here's what it does do:

  • Implements a brain using a neural network. The neural network is actually just a fully connected, weighted graph, where the weights represent the strengths of the synapses. The neural network is currently static (it remains unchanged during the lifetime of the organism), and the model is extremely simple. It supports two types of neurones, excitatory and inhibitory neurones, but that's about it.

  • Implements an environment for the brain, e.g. a body and a physical world with which the creature can interact. Actually, this particular environment consists of an empty space (no gravity), and a target, which, when touched by the creature, regenerates in a different position. The body of the creature has two sensors (relative position, i.e. distance to the target and relative velocity, i.e. the speed at which we are moving towards the target) and four outputs. Each of the four outputs can be thought of as a jet pack that can be used to accelerate the creature in a particular direction (up, down, left, right).

    This creature's purpose in life is therefore, as you might have guessed, to reach targets.

I've been using two programs to simulate my worlds, these are:

  • The "evolver": This program is responsible for developing the "genes" of the creature. Those genes are actually just the NxN matrix that represents the neural network graph (where N is the number of neurones, or nodes in the graph). It works quite simply by randomizing the genes and running a simulation with a creature that has this brain. By checking the number of times that the creature reaches the target (each simulation runs only a fixed number of steps), we have a measure of how successful that particular set of genes is.

    When we have found a reasonable brain configuration (e.g. a creature that can reach a target in around 2-3% of the simulations), we start duplicating it and perturbing the configuration slightly. In this way, we have, in each generation, a set of brain configurations corresponding to the original brain plus nine different variations of the original brain. Now each of the brain configurations are given their chances to reach their targets; the most successful configuration becomes the parent of the next generation of creatures. And we have evolution!

    It actually took about 8 hours to find the configuration of the creature that is shown in the video below.

  • The "player": This program will run a simulation, but also display it on the screen. By default, it uses the most successful brain configuration found so far. This program is what generated the video below. There's not much more to it; the simulation is exactly the same as in the "evolver". (But without visualization, the evolver can run much faster.)

So without much further ado, here's the result:

Notice how it often overshoots a little. A problem with an earlier brain configuration was that it would start circling around the target in bigger and bigger orbits, eventually disappearing from the screen altogether. I think it's really interesting, though, to see that it actually works. It surprised me.

The source code for these programs can be found at the GitHub project website. I'm not really planning to make a project out of this (other than what you see here), but patches are welcome, as always :-) Source code is GPL version 2.

Sunday, March 15, 2009

Chipmunk experiments

I've been playing with Chipmunk lately. It is a C library that simulates physics in two dimensions, and is intended for use in games. It's quite easy to use, but there is a bit of overhead in setting up graphics since I have to do that on my own. I'm using OpenGL through the SDL library, and it works quite smoothly. Here is the result of today's dabbling:

There are two important fundamental concepts in Chipmunk: Bodies and collision shapes. What is the difference? A body has the usual properties like mass, position, velocity, etc. However, a body does not have an area (a shape). That is the purpose of collision shapes. A collision shape does not have any of the properties of a body, it merely defines a shape (such as a circle or a rectangle). The relationship between these two concepts is that multiple shapes can be attached to a body. Only shapes can collide; bodies do not collide by themselves.

The balls in the video above were constructed using one collision shape (a circle shape) for each of the three bodies. They were rendered using an 8x8 OpenGL 2D texture (loaded from a PNG image) on a quadrilateral (GL_QUADS). Easy as pie.

The rope was more difficult to make. For a long time, the rope would either disintegrate slowly (because it was being pulled apart by gravity), or explode (the line segments would vibrate quite violently).

When making the rope, we need another fundamental Chipmunk object: The joint. Joints are used as constraints in the simulation. A constraint is something that keeps an object from moving freely. There are different kinds of joints: Pin joints, slide joints, pivot joints, and groove joints. For example, the pin joint simply stitches together two bodies at certain offsets from the body's centre. When one body moves, the joint will cause the other to follow.

My rope uses slide joints. The only difference from a normal pin joint is that the joint allows a certain flexibility: The "stitch" can be given a minimum and a maximum length, so that the bodies can get closer together or further apart before the joint's constraint takes effect. We can easily imagine the maximum length property as that of a string connecting two objects. The string will keep the objects from getting too far apart, but it will also bend if the objects are closer together than the length of the string.

The slide joints connect the line segments of the rope. Each line segment consists of four collision shapes attached to a single body. The four collision shapes are all circles, laid out side by side. These four circles have fixed positions with regards to each other. They're not actually drawn as circles, but as solid rectangles (GL_QUADS). The rope has 30 such line segments, so that's 30 bodies and 120 collision shapes.

Finally, we have two fixed bodies at either end of the rope. These bodies have infinite mass, are not affected by gravity, and have no collision shapes. (Actually, they're not added to the Chipmunk space, so they are not affected by any forces at all.) This is what keeps the rope in place. And to my great surprise, the way in which these bodies are connected to the rope seems to be what determines the quality of the simulation. At first, I was using pin joints to connect these stationary bodies to the endpoints of the rope. It wasn't until I replaced them with slide joints that the rope actually got as smooth as it is in the video above.

I'm currently toying with the idea of putting a cart with wheels on the thread and controlling the wheels with the arrow keys. If that works, I think it could make for a nice game element as a variation on the paddle of e.g. Breakout.