Rather than doing a postmortem, I’d rather do a post detailing how my game actually works. At first glance, Cytosine (shown above) is just a Space Invaders clone, but there’s a lot going on under the hood: this is both a quite playable game and an experiment in genetic algorithms. (Oh, and in case it had slipped your mind, cytosine is one of the four bases that make up DNA.)
Each of the aliens in the game is unique, both in appearance and in behaviour. Unlike their great-grandparents in old-school Space Invaders, they don’t sit in a fixed formation, but are allowed to roam around as free agents. The key concept of the game is that the aliens evolve, making the game harder over time. Lots of playtesting suggests that this actually works, up to a point.
An alien’s DNA is made of 18 genes, each a floating-point number between -1 and 1:
0.2, -0.7, 1.0, 0.3, -0.4, ...
The fun thing is that most genes have two meanings: one for appearance, and one for behaviour. This was originally a debugging aid, but I kept it and rearranged the meanings to make some degree of sense. For instance, aliens with a happy mouth are more inclined to move towards others, whereas those with a sad mouth are loners.
The range -1…1 gets encoded in the URL as the letters a…zA…Z, ‘a’ being -1, ‘z’ and ‘A’ being close to 0, and ‘Z’ being 1:
Different individuals are separated by underscores. It’s fun to fiddle with the URL string and see what happens.
The aliens’ behaviour is the result of a balance between attracting and repelling forces. Each force is governed by one or more genes. There are genes for moving towards fellow aliens, genes for aligning velocity with them, genes for moving away when they get uncomfortably close, genes for dodging bullets (or indeed being attracted to them), genes for avoiding the wall (which I was forced to put in to prevent wall-hugging), genes for moving towards or away from the player, and genes for when to drop bombs (based on the relative location and movement of the player’s tank).
There are also a few genes that are purely cosmetic, and don’t affect behaviour at all. Interestingly, we still see convergence in these: in one game, all aliens ended up with the same eyes, even though most of the eye genes do not correspond to behavioural traits. These genes just happened to correlate with genes that did have some evolutionary advantage. Such gene hitchhiking also happens in nature!
Breeding happens simply by randomly interpolating the values between the corresponding parents’ genes; unlike real life, genes are not copied from one or the other, but are actually a mix of the two. And, of course, to avoid complete convergence into a boring uniform alien soup, each gene has a 20% chance of being mutated by a value of up to 1.
Initially, I had a breeding stage after the level was complete; the last 6 survivors would get to pass on their genes. But as it turns out, it’s much more interesting if the aliens have to mate during the game. If they get close to each other and remain within that range for a certain amount of time, they will produce three babies that fly off the top of the screen and come back as grown-ups in the next round. One of my aims here was to stimulate flocking behaviour. This might not be good for the aliens’ chance of survival, but it’s so cool to see somewhat coordinated groups of aliens fly around the screen!
In order to prevent aliens from clumping together all the time, I added collision detection, penalized by immediate and gruesome death. So they have to find a balance: too far away and they don’t reproduce, too close and they die. In the first round of the game, you will probably see some misfits who go kamikaze, but this behaviour dies out after a round or two.
To prevent over-crowding, each level has exactly 20 aliens. If too many babies were produced in the last round, they get picked randomly. If there were too few babies, the extra slots are filled by new, completely random aliens. Initially I reused aliens from the previous generation, but random is better: it ensures that a “bad” gene pool that doesn’t reproduce properly gets an injection of new genetic material.
Well, Mr Frozen Fractal, that’s all very nice, but does it actually work? I say it does, but don’t take my word for it. Fire up a browser that’s not IE and play a few rounds of Cytosine to see for yourself!