Evolution

The last topic on our list of game AI concepts is evolution. Evolving AI bots gradually change their behavior over time, ideally becoming more adept at offensive and defensive tactics against the player. The advantage of adding evolution in a game is that the bots can become more challenging to an individual user's playing style. The idea is that each user will play a game using different tactics, and evolving bots will be able to adjust accordingly and gradually become more difficult for the player. You can implement evolution in a game in several ways. It can be done on the fly or with a bot occasionally modifying its own attributes to become better at attacking the player. Here are a few examples:

Another way to implement evolution is the old-fashioned way: through reproduction and genetic mutation. No, you won't actually make bots mate and have children-sorry to disappoint. But you can implement the idea of reproduction and mutation. Here it goes:

The idea behind mutation is that if a "bad" brain is created, it will be at the low end of the gene pool and won't be able to reproduce. But "good" brains will be at the high end of the gene pool and can reproduce. So, over time, the high end of the gene pool will get better and result in better bots. Here's how you'll implement evolution in this chapter:

Before we get to implementing evolution, though, we need to fill in one concept: bot regeneration.

Regeneration

Regeneration is a technique common in many games. This technique allows bots to "regenerate" after they die, restoring themselves to their starting location and state. This can be useful if you want to create a never-ending supply of baddies. You implement regeneration in the AIBot class in . Instead of destroying the bot when it dies, it has the option to regenerate itself by completely restoring its state.

Listing 13.24 Regeneration Code of AIBot

/**
 Returns true if this bot regenerates after it dies.
*/
public boolean isRegenerating() {
 return isRegenerating;
}
/**
 Sets whether this bot regenerates after it dies.
*/
public void setRegenerating(boolean isRegenerating) {
 this.isRegenerating = isRegenerating;
}
/**
 Causes this bot to regenerate, restoring its location
 to its start location.
*/
protected void regenerate() {
 setHealth(maxHealth);
 setState(STATE_ACTIVE);
 setAiState(DECESION_READY, null);
 getLocation().setTo(startLocation);
 getTransform().stop();
 setJumping(false);
 setPathFinder(null);
 setFacing(null);
 // let the game object manager know this object regenerated
 // (so collision detection from old location to new
 // location won't be performed)
 addSpawn(this);
}
public void update(GameObject player, long elapsedTime) {
 ...
 elapsedTimeInState+=elapsedTime;
 // record first location
 if (startLocation == null) {
 startLocation = new Vector3D(getLocation());
 }
 // regenerate if dead for 5 seconds
 if (aiState == WOUNDED_STATE_DEAD) {
 if (elapsedTimeInState >= 5000) {
 if (isRegenerating()) {
 regenerate();
 }
 else {
 setState(STATE_DESTROYED);
 }
 }
 return;
 }
 ...
}

The update() method is modified so that the regenerate() method is called if the bot has been dead for a few seconds and the bot has regeneration capabilities (isRegenerating()). The regenerate() method resets the bot and, in this case, sets its location to the place where it originated (startLocation). Also in the regenerate() method, you call the addSpawn() method to mark itself as a spawn. This is like sending a note to the game object manager that says, "Hey, I'm regenerating. Please don't perform collision detection on me this time." If collision detection were performed, the engine could think the bot virtually moved from the place where it died to the place where it regenerated instead of just reappearing there, and the bot could get stuck on a wall or against another object between those two locations. Not performing collision detection means the bot can correctly reappear at the location where it originated.

Evolving Bots

To allow only the best brains to reproduce, you need a way to track which brains are, in fact, the best. You can include many different factors in determining what makes one brain better than another, but in this case, you'll just look at the average amount of damage a bot caused with that brain. It's summed up in the BrainStat class in , which is a subclass of the Brain class. It keeps track of the damage caused and the generation of the brain.

Listing 13.25 BrainStat Inner Class of EvolutionGenePool

private class BrainStat extends Brain implements Comparable {
 long totalDamageCaused;
 int numBots;
 int generation;
 /**
 Gets the average damage this brain causes.
 */
 public float getAverageDamageCaused() {
 return (float)totalDamageCaused / numBots;
 }
 /**
 Reports damaged caused by a bot with this brain
 after the bot was destroyed.
 */
 public void report(long damageCaused) {
 totalDamageCaused+=damageCaused;
 numBots++;
 }
 /**
 Mutates this brain. The specified mutationProbability
 is the probability that each brain attribute
 becomes a different value, or "mutates."
 */
 public void mutate(float probability) {
 ...
 }
 /**
 Returns a smaller number if this brain caused more
 damage that the specified object, which should
 also be a brain.
 */
 public int compareTo(Object obj) {
 BrainStat other = (BrainStat)obj;
 if (this.numBots == 0 || other.numBots == 0) {
 return (other.numBots - this.numBots);
 }
 else {
 return (int)MoreMath.sign(
 other.getAverageDamageCaused() -
 this.getAverageDamageCaused());
 }
 }
}

The BrainStat class implements the Comparable interface so that a list of brains can easily be sorted from best to worst. You could use lots of other criteria to decide which brains are better, but using the amount of damage works well in this case. When a bot's projectile hits the player, the projectile needs to report back to the bot to tell it how much damaged was caused. You'll accomplish this when you implement the EvolutionBot in a little bit. The mutate() method isn't shown here, but it simply mutates each brain attribute if a certain random chance occurs. For example, if mutationProbability is 0.10, each attribute has a 10% chance of mutating. The code for mutating the aim time would look like this: 

if (MoreMath.chance(mutationProbability)) {
 aimTime = MoreMath.random(300, 2000);
}

When a brain is mutated, its generation count is incremented. Also, we're not showing the clone() method because it's a trivial method. Next, you must come up with a storage mechanism for all these brains in the EvolutionGenePool class in .

Listing 13.26 EvolutionGenePool.java

public class EvolutionGenePool {
 private static final int NUM_TOP_BRAINS = 5;
 private static final int NUM_TOTAL_BRAINS = 10;
 private List brains;
 ...
 /**
 Gets a new brain from the gene pool. The brain will either
 be a "top" brain or a new, mutated "top" brain.
 */
 public Brain getNewBrain() {
 // 50% chance of creating a new, mutated brain
 if (MoreMath.chance(.5f)) {
 BrainStat brain =
 (BrainStat)getRandomTopBrain().clone();
 // 10% to 25% chance of changing each attribute
 float p = MoreMath.random(0.10f, 0.25f);
 brain.mutate(p);
 return brain;
 }
 else {
 return getRandomTopBrain();
 }
 }
 /**
 Gets a random top-performing brain.
 */
 public Brain getRandomTopBrain() {
 int index = MoreMath.random(NUM_TOP_BRAINS-1);
 return (Brain)brains.get(index);
 }
 /**
 Notify that a creature with the specified brain has
 been destroyed. The brain's stats are recorded. If the
 brain's stats are within the top total brains
 then we keep the brain around.
 */
 public void notifyDead(Brain brain, long damageCaused) {
 // update statistics for this brain
 if (brain instanceof BrainStat) {
 BrainStat stat = (BrainStat)brain;
 // report the damage
 stat.report(damageCaused);
 // sort and trim the list
 if (!brains.contains(stat)) {
 brains.add(stat);
 }
 Collections.sort(brains);
 while (brains.size() > NUM_TOTAL_BRAINS) {
 brains.remove(NUM_TOTAL_BRAINS);
 }
 }
 }
}

This keeps track of 10 brains total, and only the top 5 brains are allowed to have offspring. When a bot dies, it calls the notfyDead() method to let the gene pool know how much damage it caused using the specified brain. When a new bot is created or regenerated, it calls the getNewBrain() method to get a brain. This method has a 50% chance of creating a mutated offspring and a 50% chance of just returning one of the top brains. Finally, create the EvolutionBot class in . This bot is a subclass of AIBot and performs all the necessary functions to regenerate and report how much damage it caused to the gene pool.

Listing 13.27 EvolutionBot.java

public class EvolutionBot extends AIBot {
 private EvolutionGenePool genePool;
 private long damagedCaused;
 public EvolutionBot(PolygonGroup polygonGroup,
 CollisionDetection collisionDetection,
 EvolutionGenePool genePool, PolygonGroup blastModel)
 {
 super(polygonGroup, collisionDetection,
 genePool.getNewBrain(), blastModel);
 this.genePool = genePool;
 setRegenerating(true);
 }
 public void regenerate() {
 genePool.notifyDead(brain, damagedCaused);
 brain = genePool.getNewBrain();
 damagedCaused = 0;
 super.regenerate();
 }
 public void notifyHitPlayer(long damage) {
 damagedCaused+=damage;
 }
}

The regenerate() method just overrides AIBot's method to perform the extra functionality you need. Well, that's all you need for evolution bots involving reproduction and mutation. The EvolutionBotDemo demos the code, starting with giving each bot a random brain from the gene pool and regenerating bots after they die. Bots regenerate indefinitely in this demo. Furthermore, when the game exits, it prints the attributes of the top five brains to the console so you can get an idea of what the best brains were. The longer you play, the more likely it is that this list will contain really valuable brains. Note that the player has one of the biggest effects on evolution. The player might have a preference to kill certain types of bots first. For example, bots that perform the strafe attack pattern might be so dangerous that the player tries to kill them first, allowing others to get in more damage, thus affecting evolution. Also, some bots might have a worse tactical advantage at their starting location than others, and a player could just hover around the regeneration location to pick off bots quickly, even if they would have been really smart. As we mentioned earlier, the amount of damage a bot causes isn't the only way to choose which brains are the best. Some other ideas include long life, the percentage of shots that hit the target, and the number of bullets dodged. Ideally, the best bots would have a combination of these positive characteristics.

Demo Enhancements

As usual, lots of features can be added to make the demo better. The game demo could use refinements such as health and ammo power-ups, different weapons, and "lock-on" targeting so the player can more easily attack the bots. The bots could use more patterns in general, including a better run away pattern, and the patterns could be smart enough to check the environment to decide on the best possible pattern (for example, a pattern could attempt to avoid a wall collision). Finally, the player could lose all of its health, but it never dies. You could use some sort of death sequence here. Also, a damage indicator on the heads-up display would help show when the player gets hit. This could be as easy as flashing the screen red for a few milliseconds.