Controllable procedural map generation via multiobjective evolution | Genetic Programming and Evolvable Machines Skip to main content
Springer Nature Link
Log in

Controllable procedural map generation via multiobjective evolution

  • Published:
Genetic Programming and Evolvable Machines Aims and scope Submit manuscript

Abstract

This paper shows how multiobjective evolutionary algorithms can be used to procedurally generate complete and playable maps for real-time strategy (RTS) games. We devise heuristic objective functions that measure properties of maps that impact important aspects of gameplay experience. To show the generality of our approach, we design two different evolvable map representations, one for an imaginary generic strategy game based on heightmaps, and one for the classic RTS game StarCraft. The effect of combining tuples or triples of the objective functions are investigated in systematic experiments, in particular which of the objectives are partially conflicting. A selection of generated maps are visually evaluated by a population of skilled StarCraft players, confirming that most of our objectives correspond to perceived gameplay qualities. Our method could be used to completely automate in-game controlled map generation, enabling player-adaptive games, or as a design support tool for human designers.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. This is the case if the set of optimal compromises, also called the Pareto front (please see next paragraph), has a concave shape. Das et al. [17] discuss the problem in more detail, simple examples are e.g. given by Koski [18].

  2. Available at http://www.clanscag.com.

  3. In [28], both parameters have been set to 20, other authors use 20 and 15. However, the difference in algorithm behavior is most likely negligible.

  4. The complete thread can be found at http://www.teamliquid.net/forum/viewmessage.php?topic_id=245185&currentpage=All

  5. The manual is available e.g. here: http://stat.ethz.ch/R-manual/R-patched/library/stats/html/prop.test.html, the test goes back to a paper by Wilson [37]

References

  1. J. Togelius, M. Preuss, G.N. Yannakakis, Towards multiobjective procedural map generation, in Proceedings of the FDG Workshop on Procedural Content Generation (2010)

  2. J. Togelius, M. Preuss, N. Beume, S. Wessing, J. Hagelbäck, G.N. Yannakakis, Multiobjective exploration of the starcraft map space, in Proceedings of the IEEE Conference on Computational Intelligence and Games (CIG) (2010)

  3. T. Adams, Re: optimization-based versus “constructive” pcg (post to the “procedural content generation” google group)

  4. G.S.P. Miller, The definition and rendering of terrain maps, in Proceedings of SIGGRAPH, vol 20 (1986)

  5. J. Olsen, Realtime procedural terrain generation, University of Southern Denmark, Tech. Rep. (2004)

  6. J. Doran, I. Parberry, Controllable procedural terrain generation using software agents, in IEEE Transactions on Computational Intelligence and AI in Games (2010)

  7. R. Smelik, T. Tutenel, K.J. de Kraker, R. Bidarra, Integrating procedural generation and manual editing of virtual worlds, in Proceedings of the FDG Workshop on Procedural Content Generation (2010)

  8. J. Togelius, G.N. Yannakakis, K.O. Stanley, C. Browne, Search-based procedural content generation: a taxonomy and survey, in IEEE Transactions on Computational Intelligence and AI in Games, vol in print (2011)

  9. M. Frade, F.F. de Vega, C. Cotta, Evolution of artificial terrains for video games based on accessibility, in Proceedings of the European Conference on Applications of Evolutionary Computation (EvoApplications), vol 6024 (Springer LNCS, 2010), pp. 90–99

  10. N. Sorenson, P. Pasquier, Towards a generic framework for automated video game level creation, in Proceedings of the European Conference on Applications of Evolutionary Computation (EvoApplications), vol 6024 (Springer LNCS, 2010), pp. 130–139

  11. D. Ashlock, T. Manikas, K. Ashenayi, Evolving a diverse collection of robot path planning problems, in Proceedings of the Congress On Evolutionary Computation (2006), pp. 6728–6735

  12. J. Togelius, R. De Nardi, S.M. Lucas, Towards automatic personalised content creation in racing games, in Proceedings of the IEEE Symposium on Computational Intelligence and Games (2007)

  13. C. Pedersen, J. Togelius, G.N. Yannakakis, Modeling player experience in super mario bros, in Proceedings of the IEEE Symposium on Computational Intelligence and Games (2009)

  14. E. Hastings, R. Guha, K.O. Stanley, Evolving content in the galactic arms race video game, in Proceedings of the IEEE Symposium on Computational Intelligence and Games (2009)

  15. J. Togelius, J. Schmidhuber, An experiment in automatic game design, in Proceedings of the IEEE Symposium on Computational Intelligence and Games (2008)

  16. C. Browne, Automatic generation and evaluation of recombination games, Ph.D. dissertation, Queensland University of Technology (2008)

  17. I. Das, J.E. Dennis, A closer look at drawbacks of minimizing weighted sums of objectives for pareto set generation in multicriteria optimization problems, in Structural and Multidisciplinary Optimization, vol 14 (1997), pp. 63–69

  18. J. Koski, Defectiveness of weighting method in multicriterion optimization of structures, Communications in Applied Numerical Methods, vol 1 (1985), pp. 333–337

  19. A. Agapitos, J. Togelius, S.M. Lucas, J. Schmidhuber, A. Konstantinides, Generating diverse opponents with multiobjective evolution, in Proceedings of the IEEE Symposium on Computational Intelligence and Games (2008)

  20. N. van Hoorn, J. Togelius, D. Wierstra, J. Schmidhuber, Robust player imitation with multiobjective evolution, in Proceedings of the IEEE Symposium on Computational Intelligence and Games (CIG) (2009)

  21. J. Schrum, R. Miikkulainen, Constructing complex npc behavior via multi-objective neuroevolution, in Proceedings of the Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE) (2008)

  22. F.J. Gomez, J. Togelius, J. Scmidhuber, Measuring and optimizing behavioral complexity for evolutionary reinforcement learning, in Proceedings of the International Conference on Artificial Neural Networks (ICANN) (2009)

  23. J. Togelius, G.N. Yannakakis, K.O. Stanley, C. Browne, Search-based procedural content generation, in Proceedings of the European Conference on Applications of Evolutionary Computation (EvoApplications), vol 6024 (Springer LNCS, 2010)

  24. S. Papert, Teaching children thinking. Massachusetts Institute of Technology AI Memos, Tech. Rep. 247 (1971)

  25. T.W. Malone, What makes computer games fun? Byte 6, 258–277 (1981)

    Google Scholar 

  26. M. Csikszentmihalyi, Flow: The Psychology of Optimal Experience (Harper & Row, New York, 1990)

    Google Scholar 

  27. R. Koster, Theory of Fun for Game Design (O'Reilly Media, Scottsdale, AZ, 2004), p. 256

    Google Scholar 

  28. K. Deb, A. Pratap, S. Agarwal, A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE Trans. Evolut. Comput. 6(2), 182–197 (2002)

    Google Scholar 

  29. N. Beume, B. Naujoks, M. Emmerich, SMS-EMOA: multiobjective selection based on dominated hypervolume. European Journal of Operational Research, 181(3), 1653–1669 (2007)

    Article  MATH  Google Scholar 

  30. K. Deb, R.B. Agrawal, Simulated binary crossover for continuous search space. Complex Syst. 9, 115–148 (1995)

    MathSciNet  MATH  Google Scholar 

  31. M. López-Ibáñez, L. Paquete, T. Stützle, EAF graphical tools, 2010 (Online). Available: http://iridia.ulb.ac.be/manuel/eaftools

  32. V.G. da Fonseca, C.M. Fonseca, A.O. Hall, Inferential performance assessment of stochastic optimisers and the attainment function, in EMO ’01: Proceedings of the First International Conference on Evolutionary Multi-Criterion Optimization (Springer, London, 2001), pp. 213–225

  33. M. Preuss, C. Kausch, C. Bouvy, F. Henrich, Decision space diversity can be essential for solving multiobjective real-world problems, in MCDM for Sustainable Energy and Transportation Systems, EMO Track, ed. by M. Ehrgott et al. (Springer, Berlin, 2008), pp. 367–377

  34. G. Rudolph, B. Naujoks, M. Preuss, Capabilities of emoa to detect and preserve equivalent pareto subsets, in Evolutionary Multi-Criterion Optimization, 4th International Conference, EMO 2007, Proceedings, ser. Lecture Notes in Computer Science, vol 4403, ed. by S. Obayashi, K. Deb, C. Poloni, T. Hiroyasu, T. Murata (Springer, 2007), pp. 36–50

  35. J. Hagelbäck, M. Preuss, B. Weber, CIG 2010 StarCraft RTS AI Competition (2010), http://ls11-www.cs.tu-dortmund.de/rts-competition/starcraft-cig2010/

  36. G.N. Yannakakis, How to model and augment player satisfaction: a review, in Proceedings of the 1st Workshop on Child, Computer and Interaction (ACM Press, Chania, Crete, 2008)

  37. E. Wilson, Probable inference, the law of succession, and statistical inference. J. Am. Stat. Assoc. 22, 209–212 (1927)

    Article  Google Scholar 

  38. G. Smith, J. Whitehead, M. Mateas, Tanagra: reactive planning and constraint solving for mixed-initiative level design. IEEE Trans. Comput. Intell. AI Games 3(3), 201–215 (2011). doi:10.1109/TCIAIG.2011.2159716

    Article  Google Scholar 

Download references

Acknowledgments

This research was supported in part by the Danish Research Agency project AGameComIn (number 274-09-0083) and in part by the EU FP7 ICT project SIREN (number 258453). As stated in the introduction, this paper is based on two previously published papers [1, 2]; the differences and additions with regard to those papers are detailed in the introduction.

Author information

Authors and Affiliations

  1. IT University of Copenhagen, 2300, Copenhagen S, Denmark

    Julian Togelius, Georgios N. Yannakakis & Corrado Grappiolo

  2. TU Dortmund, Otto-Hahn-Str. 14, Dortmund, Germany

    Mike Preuss, Nicola Beume & Simon Wessing

  3. Blekinge Institute of Technology, Karlskrona, Sweden

    Johan Hagelbäck

Authors
  1. Julian Togelius
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Mike Preuss
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Nicola Beume
    View author publications

    You can also search for this author inPubMed Google Scholar

  4. Simon Wessing
    View author publications

    You can also search for this author inPubMed Google Scholar

  5. Johan Hagelbäck
    View author publications

    You can also search for this author inPubMed Google Scholar

  6. Georgios N. Yannakakis
    View author publications

    You can also search for this author inPubMed Google Scholar

  7. Corrado Grappiolo
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Mike Preuss.

Additional information

Area Editor for Games: Moshe Sipper.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Togelius, J., Preuss, M., Beume, N. et al. Controllable procedural map generation via multiobjective evolution. Genet Program Evolvable Mach 14, 245–277 (2013). https://doi.org/10.1007/s10710-012-9174-5

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10710-012-9174-5

Keywords