Clustering and reproduction of players' exploration paths in video games

Collecting data from players is a common practice in the video game field. Software houses can exploit those data to identify problems and improve their products. During development data are usually collected via playtests. During a playtest the development team gathers players to collect information about how they react to the game and which are the critical points. Playtests are time consuming and cannot be performed too often. One piece of information collected during these playtests is the path each player follows while exploring the virtual environment. Being able to cluster together similar paths, and then reproduce the paths in a cluster in an automated fashion, would not only benefit the game development process, but also constitutes an interesting scientific challenge. In this thesis, we leverage an already existing framework capable of collecting data from human players and moving an autonomous agent in a virtual environment; we improve it to fit our needs and we perform a data collection process in order to gather enough human trajectories for our tests. We investigate which clustering procedure is the most suited for our needs, taking into account that we ideally want clusters based on the abilities of players. We also have to evaluate which metric should be used by the clustering procedure. We consider geometry-based metrics, like Euclidean, longest common subsequence, and dynamic time warping. Then we consider hidden Markov models and the answers to a survey we submitted to our players during data collection. Lastly, we assemble a list of measures capable of capturing the behaviour of the players without being geometrically bound. After clustering player's exploration trajectories we look for ways for reproducing trajectories belonging to a cluster using an autonomous agent. We discover that the behaviour of the agent is not as deterministic as we expect, so we split our efforts: on one side we adapt our approach to deal with this issue, on the other side we analyse the autonomous agent in order to better understand the nature of this non-determinism. We find three feasible ways for reproducing trajectories in a cluster and we detail them highlighting their pros and cons.

Raccogliere dati dai giocatori è una pratica comune nell'ambito videoludico. I team di sviluppo possono sfruttare questi dati per individuare problemi e migliorare i loro prodotti. Durante lo sviluppo i dati sono raccolti nelle sessioni di playtest. In un playtest il team di sviluppo raduna dei giocatori al fine di raccogliere informazioni su come questi reagiscono al gioco e su quali sono i punti critici. Organizzare un playtest richiede tempo, perciò sono rari. Una delle informazioni raccolte in un playtest sono i percorsi seguiti dai giocatori mentre esplorano l'ambiente virtuale. Essere in grado di raggruppare percorsi simili tra loro, e poi riprodurre automaticamente i percorsi appartenenti ad un gruppo, non solo sarebbe utile per il processo di sviluppo, ma rappresenta anche una interessante sfida scientifica. In questa tesi, sfruttiamo un framework pre-esistente in grado di raccogliere dati da giocatori umani e muovere un agente autonomo in un ambiente virtuale; lo miglioriamo per adattarlo alle nostre esigenze e avviamo una raccolta dati in modo da avere abbastanza percorsi seguiti da giocatori umani per i nostri test. Contemporaneamente consideriamo quale procedura per il clustering è la più adatta alle nostre necessità, tenendo in considerazione che vorremmo avere dei cluster basati sulle abilità di ciascun giocatore. Inoltre dobbiamo valutare quale metrica sia la più adatta per il clustering. Consideriamo metriche basate sulla geometria, come quella euclidea, longest common subsequence e dynamic time warping. Poi consideriamo gli hidden Markov model e le risposte a un questionario che abbiamo sottoposto ai giocatori. Infine, componiamo una lista di misure in grado di catturare il comportamento dei giocatori senza basarsi sulla geometria. Dopo aver raggruppato i vari percorsi dei giocatori cerchiamo dei modi per riprodurre quelli appartenenti ad un cluster usando le abilità di un agente autonomo. Scopriamo che il comportamento dell'agente non è deterministico, quindi dividiamo i nostri sforzi: da un lato adattiamo il nostro approccio per far fronte a questo problema, dall'altro analizziamo l'agente in modo da comprendere meglio la natura del non-determinismo. Troviamo tre possibili modi per riprodurre un cluster e per ciascuno evidenziamo pregi e difetti.