Saturday, May 1, 2010

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


Blogger Darkjedi said...

Wow, this sound like it's coming along well.

You're an amazing game developer!

May 13, 2010 at 10:25 PM  
Blogger john said...

We Provide Our Customers With Latest and up-to-date Dumps Questions & Answers with 100% Exam Passing Guarantee. We Promise Exceptional Success in First Attempt. 700-651 Dumps Questions

November 29, 2018 at 10:56 PM  
Blogger KaKa said...

Thanx for sharing such useful post keep it up. This blog has a lot of good information
skup samochodów używanych Wrocław

May 29, 2019 at 7:48 AM  
Blogger madin said...

I bought this copy of gucci shoes and bags and clothes from this store,cheap gucci australia the quality is very good, has been repurchased many times, recommended to friends around, they all praise the quality of shoes and bags,cheap gucci ties the store service attitude is good.

July 2, 2019 at 8:41 PM  
Blogger csyan said...

I have been paying attention to replica watches. After receiving the goods,perfect swiss replica iwc watches uk I was very surprised, the leather strap is comfortable, the watch is light weight, high quality and the price is good.perfect replica IWC portofino watches If you are looking for a watch that suits your everyday wear, this replica watch is definitely the perfect outfit. I will buy again!

October 29, 2019 at 12:00 AM  
Blogger Jackesmith said...

frases You did really good work. I really appreciate your new and different post. Please guys keep it up and share with us some unique post in the future

December 10, 2019 at 4:11 AM  
Blogger csyan said...

The store has been solving the problem for me, and the service is very patient,cheap Jimmy Choo shoes this is a perfect shopping experience.replica jimmy choo women When I received the shoes, I thought it was a good copy. I like this online store, this shoe is simple and generous. Very satisfied with this purchase.

April 27, 2020 at 8:29 PM  
Blogger said...

Great post, Which you have shared here about the genetic algorithm. Your article is very interesting and I really enjoyed reading it. Thank you. steam key shop

August 19, 2020 at 10:05 PM  
Blogger for ict 99 said...

Machine Learning Projects for Final Year machine learning projects for final year

Deep Learning Projects assist final year students with improving your applied Deep Learning skills rapidly while allowing you to investigate an intriguing point. Furthermore, you can include Deep Learning projects for final year into your portfolio, making it simpler to get a vocation, discover cool profession openings, and Deep Learning Projects for Final Year even arrange a more significant compensation.

Python Training in Chennai Python Training in Chennai Angular Training Project Centers in Chennai

January 2, 2021 at 4:02 AM  

Post a Comment

Subscribe to Post Comments [Atom]

<< Home