Constellation, le dépôt institutionnel de l'Université du Québec à Chicoutimi

Résumé

Correctly tuning difficulty in video games is a task that may appear arbitrary on the surface, but is actually one of the major foundations of game design, as it directly affects the level of player engagement. Unfortunately, this important step is presently only possible after the game is in a playable state, and this remains true in the era of AI and machine learning (ML) as even these advanced tools rely on human-provided data to function. This master’s thesis attempts to circumvent this requirement by identifying difficulty metrics which are gamecentric rather than player-centric. Video game difficulty consists of various types, including comprehensive difficulty, which stems from the various rules and parameters that make up the game. This includes the behaviour of in-game enemies, which this master’s thesis breaks down into a formal metric for analysis. In order to achieve this, I propose an innovative framework which takes advantage of the common game design practice of modelling non-player characters (NPC) into graphs known as Finite State Machines (FSM) or Behaviour Trees (BT). Our approach leverages graph properties as well as the standardized structure of these two models in order to produce a metric combining the amount of information in the graph, defined by the number of nodes, and the amount of coupling between it, measured by the graph’s cyclomatic complexity. Moreover, our framework presents a method for homogenizing the morphology of structures before their analysis, through a set of algorithms which convert FSMs and BTs into one another. By converting the original FSMs into BTs and the original BTs into FSMs and then back into BTs, we can unify both models into what we refer to as canonical BTs, a model with a predictable topology. This ensures compatibility with the rest of our framework and allows for direct comparison of enemies regardless of which model they are represented in. To validate our method, I performed a case study consisting of various enemies from well known games such as Super Mario Bros. and Mega Man in which I processed each enemy’s behavioural graph with the aforementioned algorithm and then compared them against each other. The master’s thesis concludes by discussing the limitations and the potential of this method as well as pointing out future work which could mitigate the former and capitalize on the latter.

Ajuster correctement la difficulté dans les jeux vidéo est une tâche qui peut sembler arbitraire a première vue, mais qui constitue en réalité l’un des fondements majeurs du game design, car elle influence directement le niveau d’engagement des joueurs. Malheureusement, cette étape essentielle n’est actuellement possible qu’une fois le jeu dans un état jouable, et cela demeure vrai après l’avènement de l’IA et de l’apprentissage machine (ML), puisque même ces outils avances reposent sur l’usage de données fournies par des humains. Cette thèse tente de contourner cette contrainte en identifiant des métriques de difficulté centrées sur le jeu plutôt que sur le joueur. La difficulté dans les jeux vidéo se divise en plusieurs types, dont la difficulté de compréhension, qui découle des différentes règles et paramètres présentes dans le jeu. Cela inclut notamment le comportement des ennemis, que cette thèse décompose en une métrique formelle pour l’analyser. Pour ce faire, je propose un cadre novateur qui s’appuie sur une pratique courante dans le game design: la modélisation des personnages non-joueurs (NPC) sous forme de graphes, soit les Machines à États Finis (FSM) et les Arbres de Comportement (BT). Notre approche exploite les propriétés des graphes ainsi que la structure normalisée de ces deux modèles afin de produire une métrique qui combine la quantité d’information dans le graph, définie par son nombre de nœuds, et le degré de couplage parmi celle-ci, mesure par la complexité cyclomatique du graphe. De plus, notre cadre inclut un méthode pour homogénéiser la morphologie des structures avant leur analyse, grâce à un ensemble d’algorithmes permettant la conversion réciproque des FSMs et des BTs. En convertissant les FSMs en BTs ainsi que les BTs en FSMs puis à nouveau en BTs, nous pouvons unifier les deux modèles en ce que nous appelons des BTs canoniques, un modèle a topologie prévisible idéal pour notre cadre car il permet la comparaison directe des ennemis peu importe utilise pour les représenter. Afin de valider notre méthode, j’ai réalisé une étude de cas sur différents ennemis issus de jeux connus tels que Super Mario Bros. et Mega Man, dans laquelle j’ai traite le graph comportemental de chaque ennemi à l’aide des algorithmes ci-dessus, puis les ai comparés entre eux. La thèse se conclut par une discussion sur les limitations et le potentiel de cette approche, ainsi que sur les perspectives de recherche future dans ces deux optiques.