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  
Blogger Michel Turner said...

Our client can choose Ahmedabad Russian Escorts any of them as per their convenient.Air hostess Call Girls in Aerocity We are also open to send our angels any other place of your choice. Ahmedabad Russian Escorts are waiting eagerly to meet you. You need to decide whether you want to meet them at home or at any hotel.Air hostess Call Girls in Aerocity If you are facing any challenges in arranging any place, let me inform you that we have tie-ups with 3 start hotels as well as 5 start hotels. Check our other services...

May 12, 2021 at 4:59 AM  
Blogger Michel Turner said...

We have a List of Girls who are in financial problems.Air hostess Call Girls in Aerocity They need your help.Air hostess Call Girls in Agra They are ready to sleep with you in some small amounts. Call us for their contact no and help them. To book an escort just drop a call to the given number and ask them what kind of service you want!.Air hostess Call Girls in Agra You will also WhatsApp us for the availability of our Air hostess Call Girls in Aerocity . If you’re in the end determined and ready to enjoy the amusing of being at duration the corporate of one of our beautiful girls. Check our other Services...

May 12, 2021 at 5:08 AM  
Blogger Sonam Sharma said...

Book High-class Delhi Escort Girls To Fulfill Your Desires
Our All Delhi Escorts Are In Vip Yet, You Can Choose Anyone, How Do You Like. For That Reason, You Will Not Bear Any Cost. It Is Totally Free For Our Client And Customer.Delhi Call Girls Are A Top-level Escorts Company With Secured And Also Have Verified. You Can Call Us Friendly And Without Hesitation.
Delhi Escorts Services
Delhi Escorts

May 28, 2021 at 3:54 AM  
Blogger Bed Pari Bangalore Escorts said...

Thanks for sharing this brilliant article it was a very useful and helpful article.

Bangalore Escorts
Bangalore escorts service
Bangalore escorts
Bangalore Escorts
VIP Escorts Bangalore
Call Girls in Bangalore

June 7, 2021 at 3:33 AM  
Blogger Divya Goal said...

delhi escorts
ahmedabad escorts
morbi escorts
escort service in rudrapur
Independent Bangalore Escorts
Bangalore Escorts Services
Hifi Escorts

June 7, 2021 at 11:59 PM  
Blogger Payal Singh said...

Dehradun Escort We promise you a very good service, our service girl will be full and well with you, you can take full-time service day and night, and we will continuously get great and Amazing service from you and the girls will stay with you and take you any place you are. Call girls in Dehradun | Escort Service in Dehradun

June 10, 2021 at 11:39 PM  
Blogger nikithaescor said...

Thank For this blog.
grand mercure bangalore escorts
Shanthala Nagar Escorts
call girls in bellandur
Taj Yeshwantpur Escorts

June 18, 2021 at 3:00 AM  
Blogger KEMAL UZUN said...

instagram takipçi satın al - instagram takipçi satın al - tiktok takipçi satın al - instagram takipçi satın al - instagram beğeni satın al - instagram takipçi satın al - instagram takipçi satın al - instagram takipçi satın al - instagram takipçi satın al - binance güvenilir mi - binance güvenilir mi - binance güvenilir mi - binance güvenilir mi - instagram beğeni satın al - instagram beğeni satın al - polen filtresi - google haritalara yer ekleme - btcturk güvenilir mi - binance hesap açma - kuşadası kiralık villa - tiktok izlenme satın al - instagram takipçi satın al - sms onay - paribu sahibi - binance sahibi - btcturk sahibi - paribu ne zaman kuruldu - binance ne zaman kuruldu - btcturk ne zaman kuruldu - youtube izlenme satın al - torrent oyun - google haritalara yer ekleme - altyapısız internet - bedava internet - no deposit bonus forex - erkek spor ayakkabı - - minecraft premium hesap - - tiktok jeton hilesi - tiktok beğeni satın al - microsoft word indir - misli indir

June 23, 2021 at 4:27 PM  
Blogger Unknown said...

Our agency has the capability to fulfill your dreams with our Dwarka Escorts Service. We have so many girls in our agency to your day/night pleasures.
Dwarka Escorts | Delhi Escorts

July 2, 2021 at 4:53 AM  
Blogger Unknown said...

instagram takipçi satın al
instagram takipçi satın al
takipçi satın al
takipçi satın al
instagram takipçi satın al
takipçi satın al
instagram takipçi satın al
aşk kitapları
tiktok takipçi satın al
instagram beğeni satın al
youtube abone satın al
twitter takipçi satın al
tiktok beğeni satın al
tiktok izlenme satın al
twitter takipçi satın al
tiktok takipçi satın al
youtube abone satın al
tiktok beğeni satın al
instagram beğeni satın al
trend topic satın al
trend topic satın al
youtube abone satın al
beğeni satın al
tiktok izlenme satın al
sms onay
youtube izlenme satın al
tiktok beğeni satın al
sms onay
sms onay
perde modelleri
instagram takipçi satın al
takipçi satın al
tiktok jeton hilesi
pubg uc satın al

July 24, 2021 at 4:28 PM  

Post a Comment

Subscribe to Post Comments [Atom]

<< Home