Procedural Enemy Generation through Parallel Evolutionary Algorithm

• Leonardo T. Pereira USP https://orcid.org/0000-0003-3032-6653
• Breno M. F. Viana USP
• Claudio F. M. Toledo USP https://orcid.org/0000-0003-4776-8052

Resumo

This research presents a Parallel Evolutionary Algorithm (PEA) that generates enemies with diverse characteristics, such as the enemy’s health, weapons, and movement. Our PEA aims to create enemies matching their difficulty degrees with the difficulty goal given as input parameter. We designed our algorithm in this way to be future used in an online adaptive generation system. We experimented with a set of generated enemies with an Action-Adventure game prototype as a testbed. The results show that players evaluated our approach positively, successfully creating enemies considered easy, medium, or hard to face, as defined by their original fitness’ target value. Besides, the players found the game fun to play for all difficulty levels played, and the perceived challenge rose as the PEA fitness was higher. In terms of performance results, our PEA converged into the input solution in less than a second for most cases, denoting its future use in online adaptive applications

Palavras-chave: enemy generation, procedural content generation, video games, parallel evolutionary algorithm

Referências

G. N. Yannakakis and J. Togelius, Artificial Intelligence and Games. Springer, 2018, http://gameaibook.org.

A. Liapis, G. N. Yannakakis, M. J. Nelson, M. Preuss, and R. Bidarra, “Orchestrating game generation,” IEEE Transactions on Games, vol. 11, no. 1, pp. 48–68, 2018.

Z. Tang, K. Shao, Y. Zhu, D. Li, D. Zhao, and T. Huang, “A review of computational intelligence for starcraft ai,” in 2018 IEEE Symposium Series on Computational Intelligence (SSCI). IEEE, 2018, pp. 1167–1173.

OpenAI, C. Berner, G. Brockman, B. Chan, V. Cheung, P. D˛ebiak, ..., and S. Zhang, “Dota 2 with large scale deep reinforcement learning,” 2019

O. Vinyals, I. Babuschkin, J. Chung, M. Mathieu, M. Jaderberg, W. Czarnecki, ..., and D. Silver, “AlphaStar: Mastering the RealTime Strategy Game StarCraft II,” [link], 2019.

A. Baldwin, S. Dahlskog, J. M. Font, and J. Holmberg, “Mixed-initiative procedural generation of dungeons using game design patterns,” in Computational Intelligence and Games (CIG), 2017 IEEE Conference on. IEEE, 2017, pp. 25–32.

A. Baldwin, S. Dahlskog, J. M. Font, and J. Holmberg, “Towards pattern-based mixed-initiative dungeon generation,” in Proceedings of the 12th International Conference on the Foundations of Digital Games. ACM, 2017, p. 74.

M. Sharif, A. Zafar, and U. Muhammad, “Design patterns and general video game level generation,” International Journal of Advanced Computer Science and Applications, vol. 8, no. 9, pp. 393–398, 2017.

A. Liapis, “Multi-segment evolution of dungeon game levels,” in Proceedings of the Genetic and Evolutionary Computation Conference. ACM, 2017, pp. 203–210.

A. Khalifa, S. Lee, A. Nealen, and J. Togelius, “Talakat: Bullet hell generation through constrained map-elites,” in Proceedings of The Genetic and Evolutionary Computation Conference, 2018, pp. 1047–1054.

Maxis™, “Spore,” 2008, accessed in: 2021-02-11. [Online]. Available: http://www.spore.com/.

Hello Games, “No man’s sky,” 2018, accessed in: 2020-09-11. [Online]. Available: https://www.nomanssky.com

Creature Labs, “Creatures,” 1996, accessed in: 2021-02-11. [Online]. Available: https://creatures.fandom.com/wiki/Creatures

Blizzard, “Diablo iii,” 2012, accessed in: 2021-02-11. [Online]. Available: https://us.diablo3.com/en/.

Monolith Productions, “Middle-earth: Shadow of mordor,” 2014, accessed in: 2021-02-11. [Online]. Available: https://store.steampowered.com/app/241930/Middleearth_Shadow_of_Mordor/.

Valve, “Left 4 dead 2,” 2009, accessed in: 2021-02-11. [Online]. Available: https://store.steampowered.com/app/550/Left_4_Dead_2/.

Undead Labs, “State of decay 2,” 2018, accessed in: 2021-02-11. [Online]. Available: https://state-of-decay-2.fandom.com/wiki/State_of_Decay_2_Wiki.

S. Grand and D. Cliff, “Creatures: Entertainment software agents with artificial life,” Autonomous Agents and Multi-Agent Systems, vol. 1, no. 1, pp. 39–57, 1998

T. Nomura, “An analysis on linear crossover for real number chromosomes in an infinite population size,” in Proceedings of 1997 IEEE International Conference on Evolutionary Computation (ICEC’97). IEEE, 1997, pp. 111–114.

R. Kanagal-Shamanna, B. P. Portier, R. R. Singh, M. J. Routbort, K. D. Aldape, B. A. Handal, H. Rahimi, N. G. Reddy, B. A. Barkoh, B. M. Mishra et al., “Next-generation sequencing-based multi-gene mutation profiling of solid tumors using fine needle aspiration samples: promises and challenges for routine clinical diagnostics,” Modern pathology, vol. 27, no. 2, pp. 314–327, 2014.

E. Berekméri, I. Derényi, and A. Zafeiris, “Optimal structure of groups under exposure to fake news,” Applied Network Science, vol. 4, no. 1, p. 101, Nov 2019. [Online]. Available: https://doi.org/10.1007/s41109-019-0227-z

L. T. Pereira, P. V. de Souza Prado, R. M. Lopes, and C. F. M. Toledo, “Procedural generation of dungeons’ maps and locked-door missions through an evolutionary algorithm validated with players,” Expert Systems with Applications, vol. 180, p. 115009, 2021.

E. McMillen and F. Himsl, “The binding of isaac,” 2011, accessed in: 2020-07-25. [Online]. Available: https://bindingofisaac.com/.