際際滷

際際滷Share a Scribd company logo

GECCO 2011

Fabio Zambetta
Fabio Zambetta

The document describes a patch-based approach to procedurally generating terrain for video games using an evolutionary algorithm. Terrain is constructed by extracting patches from sample heightmaps and recombination them using genetic operators. The evolutionary algorithm aims to refine terrain over multiple generations based on fitness functions or user feedback. Key aspects of the approach include extracting uniform patches, recombining patches using a roof-tiling method, interpolating between overlapping patches, and evolving terrain parameters like patch count and overlap size.

1 of 33
Evolving Patch- based Terrains for use in Video Games William Raffe, Fabio Zambetta, Xiaodong Li RMIT University, Melbourne, Australia
Outline Background Procedural Terrain Generation. Using EA in Content Generation. Approach Patch-based Terrain Generation Extracting patches, re-combining patches, and terrain generation parameters. Evolutionary Algorithm Genetic representation and operators. Parent and Gene Selection. Results Sample run. Capabilities in generating terrain for games. Future Work GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
Procedural Terrain Generation The creation of virtual terrain through algorithmic means. Reduces the time and skill to create terrain. Focus on game maps Reduce production costs. Increase replay value. Popular techniques include: Fractals Erosion simulation Noise generators Delaunay and Voronoi diagrams GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
Height-map Terrains GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
Height-map Terrains GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
Why use EA? Iterative evolutionary process allows for maps to be refined over time. Feedback from users or fitness functions direct the terrain generation process. More control Generate-and-test vs Constructive. Evolutionary algorithms successfully used on other types of game content. Euphoria character animation Search-based Procedural Content Generation (SBPCG). EA popular option for SBPCG. Has been used to change game content for each player based on their individual preferences and how they play the game. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
Patch-based Approach Extract patches from sample terrains. Initial population can either be: The sample terrains themselves. OR Constructed of randomly selected patches. Conduct Two-Level interactive evolution. Parent Selection Gene Selection Genetic operators create children by swapping individual patches of the selected parents. Repeat interactive evolution on new generation. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
Extracting Patches Program takes 8 sample terrains. Sample terrains are divided into uniform sized patches. Extra height-map data on all sides of each patch is extracted to allow for overlapping. Each patch is: Stored as a 2D array of height values (i.e. a small height-map). Placed in a global patch database. Given a unique ID that is referenced when constructing new terrains. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
Recombining Patches (Roof-Tiling) Choose a starting patch GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
Recombining Patches (Roof-Tiling) Choose a starting patch Choose the next patch and overlap it with the one before it. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
Recombining Patches (Roof-Tiling) Choose a starting patch Choose the next patch and overlap it with the one before it. Keep adding patches until an entire row is complete. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
Recombining Patches (Roof-Tiling) Choose a starting patch Choose the next patch and overlap it with the one before it. Keep adding patches until an entire row is complete. Repeat this to create a second row. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
Recombining Patches (Roof-Tiling) Choose a starting patch Choose the next patch and overlap it with the one before it. Keep adding patches until an entire row is complete. Repeat this to create a second row. Overlap the second row with the first. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
Recombining Patches (Roof-Tiling) Choose a starting patch Choose the next patch and overlap it with the one before it. Keep adding patches until an entire row is complete. Repeat this to create a second row. Overlap the second row with the first. Repeat the process of creating rows and adding them to the row before until a full terrain is made. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
Stitching Patches Patches are overlapped to ensure a smooth transition from one patch to the next. Height values in the overlap region are interpolated between the two patches. The height of a vertex is weighted towards one patch or the other based on how far through the overlap region it is. Cubic Spline Interpolation is used to smooth the entries into the overlap region. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
Terrain Parameters Number of Patches: Less Patches: Larger patch size. Ensures smooth flow in terrain but does not allow for variety. More Patches: Smaller patch size. Allows for control over finer details but higher chance jagged terrain. Overlap size: Large Overlap: Can blend patches together to make rolling terrain but lose feature details in each patch. Small Overlap: Creates hard edges which are good for cliff faces but makes the boarders of each patch more obvious. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
Patch and Overlap Size Increase Number of Patches = 4 (2x2) number of Overlap Size = 80% patches Number of Patches = 81 (9x9) Reduce Overlap Size Overlap Size = 20% GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
EA - Representation Genotype Representation: Patch Map A 2D array of patch ID numbers (a Patch Map). Each patch ID corresponds to a patch in the current dataset of patches (extracted from sample terrains at start-up). Dimensions of array reflect how many patches are used to construct each terrain. 13 5 45 22 15 9 Terrain made up of 9 patches (3x3) 34 18 40 GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
EA - Crossover Uniform Crossover: One parent chosen as base parent. Each patch given a randomly generated probability to crossover If this value is less than the Crossover Rate parameter, patch is switched for patch in same position on other parent, otherwise the patch is kept where it is. Crossover Rate between 0 and 1: Due to randomly chosen base parent, a rate over 0.5 is equivalent to that under 0.5. We mostly used a crossover rate of 0.5 patches from both parents have equal chance of being present in each child. Crossover rate of 0.2. First parent (white) is base parent. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
Mutation Each patch given probability to mutate and is compared to the Mutation Rate parameter, same as crossover. If the patch is to be mutated, in is replaced with a randomly chosen patch from the dataset of all existing patches. Mutation Rate between 0 and 1: All of our experiments used a mutation rate between 0.1 or 0.3. <0.1 results in not enough variety in children. >0.3 results in too much difference between parent and child and frequent undesirable mutations. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
Interactive Evolution: Parent Selection User picks terrains that exhibit the features they desire. User chooses 0 2 parents. No terrains other than those chosen by the user are considered for breeding. 0 parents: All offspring are randomly generated. 1 parent: All offspring are mutated versions of the parent. 2 parents: All offspring are the result of crossover between parents and individual mutations. Elitist selection: User selected parents each have one child that is an exact copy. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
Interactive Evolution: Parent Selection GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
Interactive Evolution: Gene Selection User specifies which patches are immune to crossover and mutation. All selected patches will not change from the base parent. All unselected patches may experience crossover an mutation as usual. Inverse mutation rate: More patches selected, higher chance of mutation for unselected patches. High chance of mutation when only a few patches unselected. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
Interactive Evolution: Gene Selection GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
Why use Gene Selection? Reduce user fatigue! In short: Protect good patches from mutation. Promote the change of bad patches. Swap out these two patches and keep everything else as is. Difficult when only using Parent Selection. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
Results: Sample Run (1) Generation 1: Randomly generated. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
Results: Sample Run (2) Generation 4: Main feature starts to appear. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
Results: Sample Run (3) Generation 6: Prominent main feature but a few wrong patches. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
Results: Sample Run (4) Four results from four separate runs All with the same user goal 9 generations 7 generations 13 generations 16 generations GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
Results: Game Terrain (1) Original map from the game Halo (left). Terrain generated by our system (right). Generated through multiple runs with different parameter settings The resulting terrain from one run was used as a sample terrain to the next run. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
Results: Game Terrain (2) Variations on the result terrain. Small variations can result in new experiences for the player without needing to learn an entirely new map. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
Future Challenges Move towards automated fitness evaluation. Retain some manner of Gene Selection. Refine type of terrain being generated by focusing on a single game genre. Currently, we generate Virtual Terrain but we want one system to generate complete Game Maps Investigate player profiling to drive the evolutionary process. Allows for possibilities in tailoring game maps to individual players. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
Questions? GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia

More Related Content

GECCO 2011

  • 1. Evolving Patch- based Terrains for use in Video Games William Raffe, Fabio Zambetta, Xiaodong Li RMIT University, Melbourne, Australia
  • 2. Outline Background Procedural Terrain Generation. Using EA in Content Generation. Approach Patch-based Terrain Generation Extracting patches, re-combining patches, and terrain generation parameters. Evolutionary Algorithm Genetic representation and operators. Parent and Gene Selection. Results Sample run. Capabilities in generating terrain for games. Future Work GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
  • 3. Procedural Terrain Generation The creation of virtual terrain through algorithmic means. Reduces the time and skill to create terrain. Focus on game maps Reduce production costs. Increase replay value. Popular techniques include: Fractals Erosion simulation Noise generators Delaunay and Voronoi diagrams GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
  • 4. Height-map Terrains GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
  • 5. Height-map Terrains GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
  • 6. Why use EA? Iterative evolutionary process allows for maps to be refined over time. Feedback from users or fitness functions direct the terrain generation process. More control Generate-and-test vs Constructive. Evolutionary algorithms successfully used on other types of game content. Euphoria character animation Search-based Procedural Content Generation (SBPCG). EA popular option for SBPCG. Has been used to change game content for each player based on their individual preferences and how they play the game. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
  • 7. Patch-based Approach Extract patches from sample terrains. Initial population can either be: The sample terrains themselves. OR Constructed of randomly selected patches. Conduct Two-Level interactive evolution. Parent Selection Gene Selection Genetic operators create children by swapping individual patches of the selected parents. Repeat interactive evolution on new generation. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
  • 8. Extracting Patches Program takes 8 sample terrains. Sample terrains are divided into uniform sized patches. Extra height-map data on all sides of each patch is extracted to allow for overlapping. Each patch is: Stored as a 2D array of height values (i.e. a small height-map). Placed in a global patch database. Given a unique ID that is referenced when constructing new terrains. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
  • 9. Recombining Patches (Roof-Tiling) Choose a starting patch GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
  • 10. Recombining Patches (Roof-Tiling) Choose a starting patch Choose the next patch and overlap it with the one before it. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
  • 11. Recombining Patches (Roof-Tiling) Choose a starting patch Choose the next patch and overlap it with the one before it. Keep adding patches until an entire row is complete. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
  • 12. Recombining Patches (Roof-Tiling) Choose a starting patch Choose the next patch and overlap it with the one before it. Keep adding patches until an entire row is complete. Repeat this to create a second row. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
  • 13. Recombining Patches (Roof-Tiling) Choose a starting patch Choose the next patch and overlap it with the one before it. Keep adding patches until an entire row is complete. Repeat this to create a second row. Overlap the second row with the first. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
  • 14. Recombining Patches (Roof-Tiling) Choose a starting patch Choose the next patch and overlap it with the one before it. Keep adding patches until an entire row is complete. Repeat this to create a second row. Overlap the second row with the first. Repeat the process of creating rows and adding them to the row before until a full terrain is made. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
  • 15. Stitching Patches Patches are overlapped to ensure a smooth transition from one patch to the next. Height values in the overlap region are interpolated between the two patches. The height of a vertex is weighted towards one patch or the other based on how far through the overlap region it is. Cubic Spline Interpolation is used to smooth the entries into the overlap region. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
  • 16. Terrain Parameters Number of Patches: Less Patches: Larger patch size. Ensures smooth flow in terrain but does not allow for variety. More Patches: Smaller patch size. Allows for control over finer details but higher chance jagged terrain. Overlap size: Large Overlap: Can blend patches together to make rolling terrain but lose feature details in each patch. Small Overlap: Creates hard edges which are good for cliff faces but makes the boarders of each patch more obvious. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
  • 17. Patch and Overlap Size Increase Number of Patches = 4 (2x2) number of Overlap Size = 80% patches Number of Patches = 81 (9x9) Reduce Overlap Size Overlap Size = 20% GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
  • 18. EA - Representation Genotype Representation: Patch Map A 2D array of patch ID numbers (a Patch Map). Each patch ID corresponds to a patch in the current dataset of patches (extracted from sample terrains at start-up). Dimensions of array reflect how many patches are used to construct each terrain. 13 5 45 22 15 9 Terrain made up of 9 patches (3x3) 34 18 40 GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
  • 19. EA - Crossover Uniform Crossover: One parent chosen as base parent. Each patch given a randomly generated probability to crossover If this value is less than the Crossover Rate parameter, patch is switched for patch in same position on other parent, otherwise the patch is kept where it is. Crossover Rate between 0 and 1: Due to randomly chosen base parent, a rate over 0.5 is equivalent to that under 0.5. We mostly used a crossover rate of 0.5 patches from both parents have equal chance of being present in each child. Crossover rate of 0.2. First parent (white) is base parent. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
  • 20. Mutation Each patch given probability to mutate and is compared to the Mutation Rate parameter, same as crossover. If the patch is to be mutated, in is replaced with a randomly chosen patch from the dataset of all existing patches. Mutation Rate between 0 and 1: All of our experiments used a mutation rate between 0.1 or 0.3. <0.1 results in not enough variety in children. >0.3 results in too much difference between parent and child and frequent undesirable mutations. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
  • 21. Interactive Evolution: Parent Selection User picks terrains that exhibit the features they desire. User chooses 0 2 parents. No terrains other than those chosen by the user are considered for breeding. 0 parents: All offspring are randomly generated. 1 parent: All offspring are mutated versions of the parent. 2 parents: All offspring are the result of crossover between parents and individual mutations. Elitist selection: User selected parents each have one child that is an exact copy. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
  • 22. Interactive Evolution: Parent Selection GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
  • 23. Interactive Evolution: Gene Selection User specifies which patches are immune to crossover and mutation. All selected patches will not change from the base parent. All unselected patches may experience crossover an mutation as usual. Inverse mutation rate: More patches selected, higher chance of mutation for unselected patches. High chance of mutation when only a few patches unselected. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
  • 24. Interactive Evolution: Gene Selection GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
  • 25. Why use Gene Selection? Reduce user fatigue! In short: Protect good patches from mutation. Promote the change of bad patches. Swap out these two patches and keep everything else as is. Difficult when only using Parent Selection. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
  • 26. Results: Sample Run (1) Generation 1: Randomly generated. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
  • 27. Results: Sample Run (2) Generation 4: Main feature starts to appear. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
  • 28. Results: Sample Run (3) Generation 6: Prominent main feature but a few wrong patches. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
  • 29. Results: Sample Run (4) Four results from four separate runs All with the same user goal 9 generations 7 generations 13 generations 16 generations GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
  • 30. Results: Game Terrain (1) Original map from the game Halo (left). Terrain generated by our system (right). Generated through multiple runs with different parameter settings The resulting terrain from one run was used as a sample terrain to the next run. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
  • 31. Results: Game Terrain (2) Variations on the result terrain. Small variations can result in new experiences for the player without needing to learn an entirely new map. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
  • 32. Future Challenges Move towards automated fitness evaluation. Retain some manner of Gene Selection. Refine type of terrain being generated by focusing on a single game genre. Currently, we generate Virtual Terrain but we want one system to generate complete Game Maps Investigate player profiling to drive the evolutionary process. Allows for possibilities in tailoring game maps to individual players. GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia
  • 33. Questions? GECCO11, July 14th W. Raffe, F. Zambetta, X. Li Dublin, Ireland Evolving Patch-based Terrains RMIT University, Australia