Sign in to follow this  
dfkj

Genetic algorithm in a game

Recommended Posts

Hey,

 

I have to make a project for university - a game using A*, genetic algorithm and if possible some kind of a 'building a strategy' algorithm for the enemies. I can come up with ideas about using A*, but I am not sure how can I implement a genetic algorithm in a game. Can you tell me a popular games using genetic algorithm in their implementation and what is the purpose, so I can get the idea of how to use it in my project.

 

Thanks

Share this post


Link to post
Share on other sites

Hey,

 

I have to make a project for university - a game using A*, genetic algorithm and if possible some kind of a 'building a strategy' algorithm for the enemies. I can come up with ideas about using A*, but I am not sure how can I implement a genetic algorithm in a game. Can you tell me a popular games using genetic algorithm in their implementation and what is the purpose, so I can get the idea of how to use it in my project.

 

Thanks

 

What sort of genetic algorithm? What do you want to evolve? In the somewhat literal sense the creatures series has simplified genetics. I'm not sure how A* which is primarily used for pathfinding would fit into this. I suppose you could have entities which start out using A* and then see if you can select for more effective pathfinding by making the algorithm mutatable.

Edited by Jarwulf

Share this post


Link to post
Share on other sites

 

Hey,

 

I have to make a project for university - a game using A*, genetic algorithm and if possible some kind of a 'building a strategy' algorithm for the enemies. I can come up with ideas about using A*, but I am not sure how can I implement a genetic algorithm in a game. Can you tell me a popular games using genetic algorithm in their implementation and what is the purpose, so I can get the idea of how to use it in my project.

 

Thanks

 

What sort of genetic algorithm? What do you want to evolve? In the somewhat literal sense the creatures series has simplified genetics. I'm not sure how A* which is primarily used for pathfinding would fit into this.

 

My idea is to create a 2d game in which the human player will have to reach a destination, but there will be some obstacles and some computer bots that will try to hunt and catch you. And now i am thinking of how to make the bots learn from their experience or include some sort of genetic algorithm 

Share this post


Link to post
Share on other sites

 

 

Hey,

 

I have to make a project for university - a game using A*, genetic algorithm and if possible some kind of a 'building a strategy' algorithm for the enemies. I can come up with ideas about using A*, but I am not sure how can I implement a genetic algorithm in a game. Can you tell me a popular games using genetic algorithm in their implementation and what is the purpose, so I can get the idea of how to use it in my project.

 

Thanks

 

What sort of genetic algorithm? What do you want to evolve? In the somewhat literal sense the creatures series has simplified genetics. I'm not sure how A* which is primarily used for pathfinding would fit into this.

 

My idea is to create a 2d game in which the human player will have to reach a destination, but there will be some obstacles and some computer bots that will try to hunt and catch you. And now i am thinking of how to make the bots learn from their experience or include some sort of genetic algorithm 

 

 

 

random small changes. highest score for capture. Probably should make the player automated too unless you want to manually 'evolve' your bots.

Share this post


Link to post
Share on other sites

I was thinking of the same sort of thing for enemy AI for a top down shooter. 

There really isn't enough information provided to be able to recommend a solution, but what I was thinking was something along the lines of letting bots stats determine their speed/accuracy/toughness/damage etc, with a caveat that the combined stats couldn't breach a maximium in addition movement patterns and tracking strategies would be part of the DNA. Then setting up some kind of metrics to measure how well they did against the player. How long did the bot live, how many times did it score a hit, how much damage did it cause etc. Then use those metrics to define which AI's should have the higher fitness scores. 

  I was hoping that this would make it such that players that are very accurate will find themselves fighting quick nimble erratic bots while those that didn't dodge as much/well would find them selves against tougher slower more powerful ai's. I never got to the point to implement any of this though, so I don't know how well it would have panned out.

Share this post


Link to post
Share on other sites
You may find this paper interesting. The paper describes an experiment in which player weapons were procedurally generated at the beginning of each match. The players were able to choose between their current weapons and new procedurally generated one and their choices and performance were used to evolve the weapon generation algorithm.

Share this post


Link to post
Share on other sites
thank you for the info :)
i think im going with the idea of manually "evolving" my bots depending on their performance or something like that.
do you think that, for example the terrain dificulty can be generated with a genetic algorithm where i'll try to get a more harder level for the player along the game?

i also thought of making the game self played but it was a requirement to be playable..

Share this post


Link to post
Share on other sites
I suggest a simple but nontrivial small-scale and symmetric RTS or TBS game with two modes: human vs. AI with a spartan GUI and AI vs. AI with no display and accelerated simulation.

Small scale (e.g. very few fast units on small maps) to reduce simulation cost, symmetric to make AI vs AI battles possible, with optional human opponents to provide high-quality training and fitness evaluation from time to time.

Genetic algorithms can evolve army-level and unit-level AI; armies can be rewarded for winning, units can be rewarded mainly for being part of a winning army and secondarily for performing better (e.g. more damage dealt) than other units of the same type in the same battle.

Share this post


Link to post
Share on other sites

There are only two requirements for a genetic algorithm to be able to evolve a system.

 

First you need to be able to define the "DNA", and second you need to be able to apply a fitness algorithm.

 

The DNA needs to be a series of interchangeable data fields. For example:

Assume you are able to serialize the data into segments, each segment defining a different attribute of the system, and each attribute having multiple variations.

I.E: An enemy unit

[Attribute]: Possible values

[HP]: 1-100

[Dmg]:1-5*10

[Speed]: 25- 250

[MovementPattern]: Sine, Strait Line, Circular, Zig-Zag

 

A particular unit is composed of 4 segments of DNA

[HP][DMG][Speed][MovementPattern]

One instance might be [30][20][112][Sine]

another instance might be [60][10][201][Zig-Zag]

 

Then, when the unit is killed it calculates some fitness function..  perhaps DmgDealtToPlayer/TimeAlive

Now when you create a new unit, find two dead units randomly (weighted by fitness) and randomly combine their DNA so you may end up with

[30][20][201][Sine] -> Hp, dmg and movementpattern from instance 1, speed from instance 2

Then randomly choose to mutate or not, perhaps this unit would get lucky and randomly decided to mutate the dmg to [30]

the new unit is [30][30][201][Sine]

 

Now look at terrain... perhaps its Dna is a series of N segments each segment defining a square area of the board.

[Attribute]: possible values

[TerrainType]: Lava, Spikes, Clear, Slow

 

 A three by thee terrains DNA would look something like

[lava][clear][clear][clear][spikes][clear][lava][slow][slow]

 

A level may be comprised of 9 3x3 areas.

The fitness function may be simply, how much dmg the player received while in the area

 

The second level would be 9 more 3x3 areas where each area is composed the same way a new enemy unit was composed.

 

Of course, in this instance I wouldn't be surprised if the player eventually ended up in 9 3x3 areas made entirly of lava... Obviously the most difficult terrain, but also not fun because it is impossible to survive, then again if the player ended up with Lava protection or something, the board would start to evolve toward... spikes or slow (as long as the lava protection was effective enough).

Share this post


Link to post
Share on other sites
@paragon123 i am extremely thankful for the examples you gave. that was exactly the information i was searching for - an example of a real use case. i think i have cleared the picture about the idea of the algorithm and now i can focus on thinking about the game itself.

thank you guys :)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this