Playing Around With Genetic Algorithms

I played around with some genetic algorithms today for the enemies in my next flash game. 

Here's a quick overview of the game (without giving away too many spoilers about it):

The player is given a planet which he can grow trees on. Trees which attack against these swarms of space bugs that are coming to do something to the planet. There's a lot of customization and balancing the player needs to do when growing trees, and a lot of options there. It'd be a shame for them to discover a dominant strategy within 5 minutes of starting the game and not try anything different to defend against incoming bugs.

That can be prevented by making different kinds of enemies that counter common strategies, but that still leaves open a possibility for a dominant one based on the limitations of having a finite set of enemies or a hand controlled difficulty curve.

There's 2 parts to each "enemy". The "swarm" and the "bugs". A swarm has one behavior. It is invisible, but moves around the world physically and contains data about how it wants to orbit the planet and how fast it can move and how spread out the bugs in it are going to be. Each bug has its own behaviors and variables too, life, speed, how fast it keeps up with its swarm, how often it changes direction etc. With some defaults set it looked very "swarmy" and felt like very much like a swarm of gnats orbiting a planet.

 Anyway, the thought came up today to use some genetic algorithms to make the enemies dynamic. I don't like to do too much research on topics before experimenting (rather learn for myself after knowing basic knowledge about it), so I didn't.

Some issues that came up, there wouldn't be enough enemy swarms throughout the game to make for interesting adaptation or fast enough for how much control the player will have (although there'd definitely be enough individual bugs), so there had to be some sort of a way to "control" the evolution or speed it up a bit.

Secondly, there's more than one type of enemy, each with different classifications for what counts as "success". I haven't actually implemented more than one enemy yet (or made them attack you) so I didn't worry about that one right now, but I have some ideas.

This is the structure I came up with and implemented today.

There's a base class called "Breedable" and a class called "Gene". Breedable contains a basic interface for species, with a mother and father reference, a "score" (ranking on how well it performs), and a function called "Breed" which child classes need to override. Gene is a wrapper around a Number (flash's "double" type) which defines mother and father genes, which breedable owns it, and some constants for how to combine genes during breeding.

"Mix" specifies if the parent genes get averaged, or if it just randomly picks one or the other. "Mutation" is a range for how much to randomly mutate the number during breeding. "Inertia" is my solution for "speeding" up evolution. During breeding, it looks at it's parents' scores and their parents' scores to see if the previous mutation made the species "better" or "worse". It will then use that to randomly mutate the number again to lead it in the direction of "most success".

A "GenePool" contains a list of species and the scores they got. It has a maximum size (for how many of an individual species can exist at once in the pool). Before breeding, you refresh it which sorts itself by score and extincts the species which make it go over the limit. You then get species from it by calling "extract", which grabs 2 randomly (weighted by score), breeds them, and returns the new species which you pass on to the bug or swarm to create itself out of.

When the bug/swarm is done, it grades it's species and puts it in the gene pool. When a species breeds, it's marked as old and gets sorted near the end of the pool the next time it's refreshed to ensure old species don't hang around forever (as species never get rescored once they're in the pool, just their new children do).

There's 2 species types I have right now. "SwarmSpecies" and "BugSpecies". Each swarm species contains a GenePool of bug species. When breeding swarm species together, it combines the bug genepools together too. The main game controller contains the swarm's GenePool. At each wave, it refreshes the pool and generates new species from it. Since enemies don't have a good metric for how well they performed right now (as I don't have the enemies being dangerous yet), the "score" is just how many ticks they could stay alive for.

Initial results look promising. After killing some basic bugs, I played with it a few times. Enemies realized that when they were close to the planet they were harder to hit (since less bullets could reach them when the planet was in the way), so new generations got progressively closer to the surface of the planet. I didn't like this cause if they were inside it makes them impossible to kill, so I added a minimum orbit distance.

Yet again though, they found a way to burrow into the planet by orbiting fast and moving slow (they never had much time to catch up to where they were orbiting, so they lagged behind, conveniently inside the planet). After about 6 waves I had enemy swarms completely inside the planet, unable to be hit, effectively invincible. Trying again, I shot just the swarms who liked to bunch together before clearing out the rest, and sure enough the enemies got smaller and more spread out (= way harder to hit with big powerful shots, but much easier to hit with lots of tiny low power shots).

I had to impose some limits on the speed too, enemies found out that if they moved very slowly, it would take them way longer to get in range of being shot in the first place. I even had an enemy just sitting there on the blind side of the planet not orbiting cause I couldn't hit it there. Variables that mattered less for survival tended to stay pretty random throughout the game, as expected too.

I'll probably keep this in the game. It makes it interesting, even though it still needs a lot of tweaking to get right (and of course, I need to make real enemies too).

Enemies have learned to burrow and grow huge