< Day Day Up > |
15.3 Genetics in Game DevelopmentIn games, genetic algorithms are simply a method of finding an optimum solution to a problem. Of course, there are lots of problems to be solved in game AI, and not all of them are good candidates for a genetic algorithm. Pathfinding, for example, can be solved with a genetic algorithm, however it's usually a problem better suited to something such as the A* algorithm. Genetic algorithms work best when the elements of the problem are somewhat unpredictable. This allows the game AI to adapt to a situation the game designer might not have been able to predict. In game design, the most unpredictable element of the game environment is the player. To some degree, the game designer must be able to predict the player's behavior to create a challenging adversary. Unfortunately, it can be difficult to predict and account for every possible player behavior. Genetic algorithms basically involve a trial-and-error approach. You essentially populate the game world with many possible solutions and then determine which solutions work the best. Of course, the solutions won't always be the same for every player. That's the beauty of genetic algorithms. The game AI will adapt to individual players. 15.2.9 Role-Playing ExampleGenetic algorithms are useful in any scenario in which a computer-controlled adversary must respond and change due to player behavior. For example, consider a hypothetical multiplayer role-playing game. In this game the players would be able to choose from many different types of character classes and abilities. This means the computer-controlled characters would have to be able to present a challenge to many types of player-controlled characters. A player could choose to play a warrior character that would fight mainly with brute force. Of course, with this class the player would be able to choose from a multitude of weapons. The player could attack with a sword, axe, or any number of other weapons. The fighter class also would be able to wear an assortment of armor. On the other hand, the player might choose a totally different class. A magical class would produce a totally different player behavior. The various combinations of class and weapon types would make it difficult for a game designer to create a single type of computer-controlled individual that would be a challenge to every type of player-controlled character. It could be even more complicated in a multiplayer game. In this type of game the computer will have to be a challenge to a group of diverse players working in combination. The number of possible combinations quickly would become more than a game designer could account for. 15.2.10 Encoding the DataWe are searching for a type of computer-controlled character that will be a challenge to a player or group of players. This isn't a search that you can precalculate. Each player or group of players would behave differently. We need to determine the situations and responses that will either increase or decrease the level of fitness in the population. For example, one possible situation could be when the player attacks a computer-controlled character with a magic weapon. We can create several possible responses to this player action. The computer-controlled character could attack the player in response, attempt to flee, or attempt to hide. We could assign this situation and response to a chromosome. If this chromosome is set to create an attack response in this situation, the player will be attacked when using a magic weapon. However, what if this scenario always leads to the defeat of the computer-controlled character? In that case, the computer-controlled character would be deemed less fit, and therefore, less likely to pass on that trait. In successive generations this scenario would lead to a different behavior, such as a retreat whenever the player wields a magic weapon. Example 15-6 lists some of the possible scenarios we address in our hypothetical example. Example 15-6. Possible scenarios
Figure 15-5 shows the possible situations in which members of the population will behave differently. We use a different chromosome to store the response to each situation. We begin with the kAttackedbyFighter constant. This chromosome will store the response whenever the computer-controlled character is attacked by a player-controlled fighter character. Some creature types might be more or less effective when doing battle against fighter characters. Similarly, the kAttackedbyWizard chromosome will store the response to being attacked by a player-controlled wizard character. The kAttackedbyGroup chromosome will indicate the behavioral response to being attacked by a group of player characters. The kHealerPresent chromosome indicates which behavior should be used when a player healer is present. If the players can be healed repeatedly, it might be a futile situation in which retreat would be most appropriate. The next four chromosomes, kAttackedByBlade, kAttackedByBlunt, kAttackedByProjectile, and kAttackedByMagic, determine which response to give for each type of weapon the player can wield. The next three, kAttackerWearingMetalArmor, kAttackerWearingLeatherArmor, and kAttackerWearingMagicArmor, determine the best response to the various types of protective armor the player can wear. Some computer-controlled characters can choose from a selection of weapons. For example, a blade weapon might be more effective against leather armor. The final chromosome, kImInGroup, is used to determine the best response when the computer-controlled character is fighting in a group. Some types of creatures, such as wolves, can be more effective when fighting in a pack. A real game probably would have a much more thorough list of possible scenarios, but for this example our list should suffice. Example 15-7 shows the possible responses to each scenario. Example 15-7. Possible behaviors
Each constant shown in Example 15-7 defines a possible character behavior; they each assign a behavior to one scenario shown in Example 15-6, and we start with the kRetreat constant. As the name implies, this behavior causes the computer-controlled character to run from player characters. The second constant, kHide, makes the computer-controlled character enter a state in which it will attempt to elude detection. The next three constants, kWearMetalArmor, kWearMagicArmor, and kWearLeatherArmor, make the computer-controlled character switch to each respective type of armor. The final three constants, kAttackWithBlade, kAttackWithBlunt, and kAttackWithMagic, define the type of attack the computer-controlled character should use against the player. Now we create an array that contains a behavioral response for each possible scenario shown in Example 15-6. We will use one array element for each possible scenario. We accomplish this with a simple C++ class structure, as shown in Example 15-8. Example 15-8. Encoding structure
As Example 15-8 shows, we create an ai_Creature class that contains an array of chromosomes. Each element of the array represents a trait, or behavior, for the computer-controlled character. We define each possible behavior and then we link each chromosome to each behavior. We use an array size of 12 because Example 15-6 shows 12 possible situations. 15.2.1 The First GenerationSo far we have defined the possible scenarios that we use for the genetic tests, defined the possible behaviors associated with each scenario, and created a structure to store the genetic data. The next step is to create the population. We start by expanding on the code shown in Example 15-8. Example 15-9 shows the modifications. Example 15-9. Defining the population
As Example 15-9 shows, we added the constant kPopulationSize to define the size of the creature population. We also added an array of ai_Creature whose bounds are set to the values assigned to kPopulationSize. The next step is to begin linking individual behaviors to each possible situation shown in Example 15-6. We start by adding a new function to the ai_Creature class. Example 15-10 shows the modified ai_Creature class. Example 15-10. Defining createIndividual
The new function, ai_createIndividual, initializes a new member of the population. However, we don't want to initialize each individual using a set of predefined constants. We want the population to be as diverse as possible. A population that isn't diverse won't be as effective at finding the best solution. The best way to create a diverse population is to assign the behaviors in a random fashion. However, we can't simply randomly assign the behaviors shown in Example 15-7 to the situations shown in Example 15-6. Some of the behaviors don't apply to the listed situations. We solve this problem by using a block of conditional statements, as shown in Example 15-11. Example 15-11. Randomly assigning chromosomes
The first case statement assigns a random behavior to the kAttackedbyGroup chromosome. For this chromosome we choose from five possible behaviors (kRetreat, kHide, kAttackWithBlade, kAttackWithBlunt, and kAttackWithMagic). The idea is to try to determine if any of these actions provide a noticeable advantage or disadvantage when a group of player characters attacks the computer-controlled character. For example, the process of evolution might show that retreating is the best course of action when attacked by a group of players. The second case statement sets the value in the kHealerPresent chromosome. Again, we want to determine if creating a diverse population, in which the response to this situation varies among the members, will give some individuals an advantage or disadvantage. As in the case of the kAttackedbyGroup chromosome, we use the following five responses: kRetreat, kHide, kAttackWithBlade, kAttackWithBlunt, and kAttackWithMagic. Now we consider the possible behaviors to link to the various types of attacks the player could use. Again, we randomly assign appropriate behaviors to each possible attack method. This is shown in Example 15-12. Example 15-12. Attack responses
As Example 15-12 shows, we consider four possible attack methods by the player (kAttackedByBlade, kAttackedByBlunt, kAttackedByProjectile, and kAttackedByMagic). Each possible attack is linked to its own chromosome and is assigned in a separate case statement. Each will be randomly assigned one of five possible responses: kRetreat, kHide, kWearMetalArmor, kWearMagicArmor, and kWearLeatherArmor. These chromosomes will help us determine which types of armor are better suited for each possible player attack. They also will tell us if retreating or hiding is the best response to some attacks. For example, if members of the population are repeatedly defeated when attacked by magic, retreat might end up being the best response. Now we consider the possible effects resulting from the various types of armor the player might be wearing. We follow a similar case statement structure, as shown in Example 15-13. Example 15-13. Armor responses
Example 15-13 uses three case statements to assign responses randomly to the various types of armor the player can wear. Hopefully, this will help us determine the best type of attack to use against the various types of armor. The type of armor we consider includes kAttackerWearingMetalArmor, kAttackerWearingLeatherArmor, and kAttackerWearingMagicArmor. Each will be randomly assigned one of five possible responses, including kRetreat, kHide, kAttackWithBlade, kAttackWithBlunt, and kAttackWithMagic. 15.2.2 Ranking FitnessAt some point we need to try to determine which members of the population are the fittest. Remember, we are searching for members of the population that are the greatest challenge to the players. We need some way to quantify and measure the level of challenge. We can consider several different approaches. Role-playing games typically assign hit points to each character. These hit points are reduced as the character is injured during battle. The character dies once the hit points reach zero. So, one way to quantify the level of challenge is to keep a cumulative total of the amount of hit-point damage done to the players. Each member of the population would track its total damage inflicted. Conversely, we also could track the amount of damage done by the players to the members of the population. Example 15-14 shows how we would expand the ai_Creature class to include variables to track the damage done and damage received. Example 15-14. Tracking hit-point damage
As Example 15-14 shows, we added two new variables to the ai_CreatureClass. The first, totalDamageDone, will be increased each time the computer-controlled character inflicts damage to a player; it will be increased by the amount of the hit-point damage done. Conversely, the totalDamageReceived variable would be increased whenever the player injured the computer-controlled character. As in the case of totalDamageDone, the amount of the increase would be equal to the hit-point damage done. Of course, you should consider other game elements when determining the fitness of the individuals in the population. For example, the total player kills would be another good indicator. 15.2.3 SelectionThe next step in the evolutionary process is to search for the fittest members of the population. These individuals will exhibit traits we want to pass on to the next generation. Once again we expand on the ai_Creature class. We calculate the ratio of damage done to damage received. We keep a running total of damage done and damage received in the totalDamageDone and totalDamageReceived variables. The fitness variable will contain the ratio of damage done to damage received. Example 15-15 shows the updated class. Example 15-15. Adding fitness tracking
As Example 15-15 shows, now we have a variable to quantify the actual fitness of each individual. We use the fitness variable to calculate the fitness of each individual and then sort the population from most successful to least successful. We also added the sortFitness function to the ai_Creature class. This calculation and sorting are shown in Example 15-16. Example 15-16. Sorting fitness
The sortFitness function begins by calculating the damage done to damage received ratio for each individual in the population. This is accomplished in the first for loop. The actual ratio is stored in the fitness variable. Once we have calculated the fitness ratio for each individual, we can sort the entire population array. The sort is handled by the nested for loops. This is just a standard bubble sort algorithm. The end result is that we sort the entire population array by the fitness variable, from most fit to least fit. 15.2.4 EvolutionNow we have an easy way to identify the most successful individuals in the population. Calling the sortFitness function will ensure that the lower positions in the ai_Creature array will be the fittest individuals. We then can use the traits of the individuals in the lower array elements to create the next generation. Figure 15-10 shows how the chromosomes in each array will be combined to create a new individual. Figure 15-10. CrossoverAs Figure 15-10 shows, we use the crossover process when creating the new individual. Now we update the ai_Creature class to include a new crossover function. Example 15-17 shows the updated ai_Creature class. Example 15-17. Adding the crossover function
The new crossover function will take the traits of two individuals and combine them to create a third. Example 15-18 shows this function. Example 15-18. Crossover
As Example 15-18 shows, three variables are passed into the crossover function. There are three array indexes. The first two are the parents whose chromosomes will be combined to create a new individual. The third variable is the array index of the new individual. On each line we alternate between the j and k array indexes. This essentially mixes the chromosome of the parents when creating the offspring. Although mixing the chromosomes of two fit parents should create a new fit individual, we also want to try to improve on the previous generation. We do this by introducing random mutations. We start by updating the ai_Creature class to include a random mutation function. This is shown in Example 15-19. Example 15-19. Adding the random mutation function
As the updated ai_Creature class in Example 15-19 shows, now we need to add a random mutation function. A random mutation enables us to build a fit individual with what is essentially a guess at what might make it a little bit better. Example 15-20 shows the random mutation function. Example 15-20. Random mutations
Example 15-20 will reassign chromosomes randomly. Each trait has a 5% chance of randomly mutating. This is accomplished with each conditional line if (Rnd(1,20)==1). Like the createIndividual function, there are limits to the values we can assign to each trait. We use the switch statements to ensure that only legitimate values are assigned to each trait. You can incorporate genetic algorithms into a multiplayer role-playing game in other ways as well. The previous example focused mainly on changing behavior in response to player actions; however, other areas of game design can benefit from genetic algorithms. For example, role-playing games typically categorize character abilities and assign a point level to each. A troll might have 100 opportunity points to divide over several attributes, such as strength, magical ability, dexterity, and a magic resistance. Instead of assigning the same values to each troll in the population, it might be better to use some diversity. For example, some would be physically stronger while others would have a greater resistance to magic. Varying the point distribution and then ranking the fitness of the population would help determine the best balance of point distribution. Successive generations of trolls then could evolve into more challenging adversaries for the players. |
< Day Day Up > |
No comments:
Post a Comment