Methods for Procedural Generation of Skill Trees for Computer Games

• Název práce v češtině: Metody pro procedurální generovaní dovednostních stromů pro počítačové hry
• Název v anglickém jazyce: Methods for Procedural Generation of Skill Trees for Computer Games
• Klíčová slova: procedurální generovaní, dovednostní stromy, hry na hrdiny, evoluční algoritmy
• Klíčová slova anglicky: Procedural content generation, skill tree, role play games, evolutionary algorithms
• Akademický rok vypsání: 2018/2019
• Typ práce: bakalářská práce
• Jazyk práce: angličtina
• Ústav: Katedra softwaru a výuky informatiky (32-KSVI)
• Vedoucí / školitel: Mgr. Jakub Gemrot, Ph.D.
• Řešitel: Mgr. Petr Jaroschy - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 02.05.2019
• Datum zadání: 02.05.2019
• Datum potvrzení stud. oddělením: 19.07.2019
• Datum a čas obhajoby: 05.09.2019 09:00
• Datum odevzdání elektronické podoby: 17.07.2019
• Datum odevzdání tištěné podoby: 19.07.2019
• Datum proběhlé obhajoby: 05.09.2019
• Oponenti: Mgr. Martin Pilát, Ph.D.

Zásady pro vypracování

Aim of this work is to create multiple algorithms for procedural generation of skill trees for computer games. Part of this work will be dedicated to create a simple game, which will be used as a testbed for the algorithms. Algorithms will be evaluated synthetically then by examining their generative properties according to different axes using multiple artificial players as surrogates for human players.

Seznam odborné literatury

Hendrikx, M., Meijer, S., Van Der Velden, J., & Iosup, A. (2013). Procedural content generation for games: A survey. ACM Transactions on Multimedia Computing, Communications, and Applications (TOMM), 9(1), 1.
Chen, J. (2007). Flow in games (and everything else). Communications of the ACM, 50(4), 31-34.
Csikszentmihalyi, Mihaly (1990). Flow: The Psychology of Optimal Experience. New York: Harper and Row. ISBN 0-06-092043-2
Foong, N. W., On, C. K., Alfred, R., Teo, J., & Ibrahim, A. A. A. (2017, October). Interactive procedural generation for items in role-playing game. In 2017 IEEE 2nd International Conference on Automatic Control and Intelligent Systems (I2CACIS) (pp. 150-154). IEEE.
Heinimaki, T., & Elomaa, T. (2015, September). Augmenting Technology Trees: Automation and Tool Support. In 2015 7th International Conference on Games and Virtual Worlds for Serious Applications (VS-Games) (pp. 1-8). IEEE.
Cook, M., Eladhari, M., Nealen, A., Treanor, M., Boxerman, E., Jaffe, A., ... & Swink, S. (2016). PCG-Based Game Design Patterns. arXiv preprint arXiv:1610.03138.
Yannakakis, G. N., & Togelius, J. (2011). Experience-driven procedural content generation. IEEE Transactions on Affective Computing, 2(3), 147-161.
Lopes, R., & Bidarra, R. (2011). Adaptivity challenges in games and simulations: a survey. IEEE Transactions on Computational Intelligence and AI in Games, 3(2), 85-99.
Horn, B., Dahlskog, S., Shaker, N., Smith, G., & Togelius, J. (2014). A comparative evaluation of procedural level generators in the mario ai framework. In Foundations of Digital Games 2014. Society for the Advancement of the Science of Digital Games.

Předběžná náplň práce

Herní vývojáři často čelí problému vyvážené obtížnosti hry, a to speciálně u her na hrdiny. Dovednostní strom je element hry, který zásadním způsobem přispívá k řešení tohoto problému pomocí posilování hráče ve hře. Hodně herních elementů může být procedurálně generováno, aby se ušetřil čas a peníze, ale mohou být dovednostní stromy také generovány. A jak můžeme ověřit, že generovaný strom je dobře stavěný pro danou hru? To je cílem této práce. Vytvořili jsme jednoduchou turn-based hru. Poté jsme vytvořili několik variant generátorů dovednostních stromů pro tuto hru. Vzali jsme ty nejlepší stromy a ověřili jsme jejich výkon za použití umělých hráčů z dat sesbíraných při jejich hraní. Poté jsme tyto stromy porovnali a došli jsme k tomu, že dovednostní stromy mohou být generovany pomocí námi navrhnuté metody a jejích variant.

Předběžná náplň práce v anglickém jazyce

Game developers often face the issue of having well balanced game in terms of difficulty, especially in role-playing games. Skill tree is a game element which contributes to solve this issue by giving the player more power in-game. Many game elements can be procedurally generated to save time and money to developers, but can skill trees be procedurally generated too? And how do we validate, that generated skill trees are well suited for the game? That is the goal of this work. We have made a simple turn-based game. Then we made several variations of generators of skill trees for the game. We took the best trees and validated their performance using artificial players based on data collected during their gameplay. Then we compared the trees and concluded that skill trees can be generated by our suggested method and their variations.