Génération de mission à l'aide de l'apprentissage automatique classique et des réseaux de neurones récurrents dans un état zombie

Peut-être êtes-vous familier avec la génération de niveau procédural ; eh bien, dans cet article, tout tourne autour de la génération procédurale de missions. Nous présenterons une vue d'ensemble de la génération de missions à l'aide de l'apprentissage automatique classique et des réseaux de neurones récurrents pour les jeux roguelike.

Salut tout le monde! Je m'appelle Lev Kobelev et je suis Game Designer chez MY.GAMES. Dans cet article, j'aimerais partager mon expérience de l'utilisation du ML classique et des réseaux de neurones simples en expliquant comment et pourquoi nous avons opté pour la génération de missions procédurales, et nous approfondirons également la mise en œuvre du processus dans Zombie. État.

Les bases de la mission « box » : vagues, spawns, et plus encore

☝🏻 Tout d'abord, quelques terminologies : « arènes », « niveaux » et « emplacements » sont synonymes dans ce contexte, ainsi que « zone », « zone » et « zone d'apparition ».

Maintenant, définissons la « mission ». Une mission est un ordre prédéterminé dans lequel les ennemis apparaissent à un endroit selon certaines règles . Comme mentionné, dans Zombie State, des emplacements sont générés, nous ne créons donc pas une expérience « mise en scène ». Autrement dit, nous ne plaçons pas les ennemis à des points prédéterminés – en fait, de tels points n'existent pas. Dans notre cas, un ennemi apparaît quelque part à proximité d'un joueur ou d'un mur spécifique. De plus, toutes les arènes du jeu sont rectangulaires, donc n'importe quelle mission peut être jouée sur n'importe laquelle d'entre elles.

Introduisons le terme « spawn ». L'apparition est l'apparition de plusieurs ennemis du même type selon des paramètres prédéterminés à des points d'une zone désignée . Un point – un ennemi. S'il n'y a pas assez de points dans une zone, celle-ci est agrandie selon des règles spéciales. Il est également important de comprendre que la zone n'est déterminée que lorsqu'un spawn est déclenché. La zone est déterminée par les paramètres d'apparition, et nous considérerons deux exemples ci-dessous : un spawn près du joueur et un près d'un mur.

Le premier type d'apparition se trouve à proximité du joueur . L'apparence à proximité du joueur est précisée par un secteur, qui est décrit par deux rayons : externe et interne (R et r), la largeur du secteur (β), l'angle de rotation (α) par rapport au joueur et le visibilité (ou invisibilité) souhaitée de l'apparence de l'ennemi. À l'intérieur d'un secteur se trouve le nombre de points nécessaire pour les ennemis – et c'est de là qu'ils viennent !

Le deuxième type de ponte se trouve près du mur . Lorsqu'un niveau est généré, chaque côté est marqué d'une balise – une direction cardinale. Le mur avec la sortie est toujours au nord. L'apparence d'un ennemi près d'un mur est précisée par le tag, la distance à celui-ci (o), la longueur (a), la largeur d'une zone (b) et la visibilité (ou invisibilité) souhaitée de l'apparence de l'ennemi. Le centre d'une zone est déterminé par rapport à la position actuelle du joueur.

Les apparitions arrivent par vagues . Une vague est la manière dont les apparitions apparaissent, à savoir le délai entre elles – nous ne voulons pas frapper les joueurs avec tous les ennemis en même temps. Les vagues sont regroupées en missions et sont lancées les unes après les autres, selon une certaine logique. Par exemple, une deuxième vague peut être lancée 20 secondes après la première (ou si plus de 90 % des zombies qui s'y trouvent sont tués). Ainsi, une mission entière peut être considérée comme une grande boîte, et à l'intérieur de cette boîte, il y a des boîtes de taille moyenne (vagues), et à l'intérieur des vagues, il y a des boîtes encore plus petites (spawns).

Alors, avant même de travailler sur les missions proprement dites, nous avons déjà défini quelques règles :

1. Pour maintenir un sentiment d'action constant, assurez-vous de faire apparaître fréquemment des zombies réguliers à proximité du joueur à des points visibles.
2. Afin de mettre en évidence la sortie ou de pousser le joueur d'un certain côté, efforcez-vous principalement de faire apparaître des ennemis de combat à longue portée près des murs.
3. À l'occasion, faites apparaître des ennemis spéciaux devant le joueur, mais à des points invisibles.
4. Ne faites jamais apparaître d'ennemis à moins de X mètres du joueur
5. Ne faites jamais apparaître plus de X ennemis en même temps

À un moment donné, nous avions une centaine de missions prêtes, mais au bout d’un moment, il nous en fallait encore plus. Les autres concepteurs et moi-même ne voulions pas consacrer beaucoup de temps et d'efforts à la création d'une centaine de missions supplémentaires, nous avons donc commencé à chercher une méthode rapide et bon marché pour générer des missions.

Génération de mission

Décomposition de la mission

Tous les générateurs fonctionnent selon un certain ensemble de règles, et nos missions créées manuellement ont également été réalisées selon certaines recommandations. Nous avons donc émis une hypothèse sur les modèles au sein des missions, et ces modèles serviraient de règles pour le générateur.

✍🏻 Quelques termes que vous retrouverez dans le texte :

• Le clustering consiste à diviser une collection donnée en sous-ensembles (clusters) qui ne se chevauchent pas, de sorte que les objets similaires appartiennent au même cluster et que les objets de différents clusters soient significativement différents.

• Les caractéristiques catégorielles sont des données qui prennent une valeur dans un ensemble fini et n'ont pas de représentation numérique. Par exemple, la balise du mur d'apparition : Nord, Sud, etc.

• Le codage des caractéristiques catégorielles est une procédure permettant de convertir des caractéristiques catégorielles en une représentation numérique selon certaines règles préalablement spécifiées. Par exemple, Nord → 0, Sud → 1, etc.

• La normalisation est une méthode de prétraitement des caractéristiques numériques afin de les amener à une échelle commune sans perdre d'informations sur la différence de plages. Ils peuvent être utilisés, par exemple, pour calculer la similitude d’objets. Comme mentionné précédemment, la similarité des objets joue un rôle clé dans les problèmes de clustering.

  
  

La recherche manuelle de tous ces modèles prendrait extrêmement de temps, nous avons donc décidé d'utiliser le clustering. C’est là que l’apprentissage automatique s’avère utile, car il gère bien cette tâche.

Le clustering fonctionne dans un espace à N dimensions et le ML fonctionne spécifiquement avec des nombres. Par conséquent, tous les spawns deviendraient des vecteurs :

• Les variables catégorielles ont été codées
• Toutes les données ont été normalisées

Ainsi, par exemple, l'apparition décrite comme « engendrer 10 tireurs zombies sur le mur nord dans une zone avec une empreinte de 2 mètres, une largeur de 10 et une longueur de 5 » est devenue le vecteur [0,5, 0,25, 0,2 , 0,8, …, 0,5] (←ces nombres sont abstraits).

De plus, la puissance de l'ensemble des ennemis a été réduite en mappant des ennemis spécifiques à des types abstraits. Pour commencer, ce type de cartographie permettait d’attribuer facilement un nouvel ennemi à un certain groupe. Cela a également permis de réduire le nombre optimal de modèles et, par conséquent, d’augmenter la précision de la génération – mais nous y reviendrons plus tard.

L'algorithme de clustering

Il existe de nombreux algorithmes de clustering : K-Means, DBSCAN, spectral, hiérarchique, etc. Ils reposent tous sur des idées différentes mais ont le même objectif : trouver des clusters dans les données. Ci-dessous, vous voyez différentes manières de rechercher des clusters pour les mêmes données, en fonction de l'algorithme choisi.

L'algorithme K-Means a donné de meilleurs résultats dans le cas des apparitions.

Maintenant, une petite parenthèse pour ceux qui ne connaissent rien à cet algorithme (il n'y aura pas de raisonnement mathématique strict puisque cet article porte sur le développement de jeux et non sur les bases du ML). K-Means divise de manière itérative les données en K clusters en minimisant la somme des carrés des distances de chaque entité à la valeur moyenne de son cluster attribué. La moyenne est exprimée par la somme intra-cluster des carrés des distances.

Il est important de comprendre les points suivants à propos de cette méthode :

• Cela ne garantit pas la même taille de clusters – pour nous, cela ne pose pas de problème puisque la répartition des clusters au sein d’une mission peut être inégale.
• Il ne détermine pas le nombre de clusters à l'intérieur des données, mais nécessite un certain nombre K comme entrée, c'est-à-dire le nombre souhaité de clusters. Parfois, ce nombre est déterminé à l’avance, et parfois, il ne l’est pas. De plus, il n’existe pas de méthode généralement acceptée pour trouver le « meilleur » nombre de clusters.

Examinons ce deuxième point un peu plus en détail.

Le nombre de clusters

La méthode du coude est souvent utilisée pour sélectionner le nombre optimal de clusters. L’idée est très simple : nous exécutons l’algorithme et essayons tous les K de 1 à N, où N est un nombre raisonnable. Dans notre cas, c’était 10 – il était impossible de trouver plus de clusters. Trouvons maintenant la somme des carrés des distances au sein de chaque cluster (un score appelé WSS ou SS). Nous allons afficher tout cela sur un graphique et sélectionner un point après lequel la valeur sur l'axe y cesse de changer de manière significative.

Pour illustrer, nous utiliserons un ensemble de données bien connu, le Ensemble de données sur les fleurs d'iris . Exécutons l'algorithme avec K de 1 à 10 et voyons comment l'estimation ci-dessus change en fonction de K. À environ K = 3, l'estimation cesse de changer beaucoup - et c'est exactement le nombre de classes qu'il y avait dans l'ensemble de données d'origine.

Si vous ne voyez pas le coude, vous pouvez utiliser la méthode Silhouette, mais cela dépasse le cadre de l'article.

Tous les calculs ci-dessus et ci-dessous ont été effectués en Python à l'aide de bibliothèques standard pour le ML et l'analyse de données : pandas, numpy, seaborn et sklearn. Je ne partage pas le code puisque le but principal de l'article est d'illustrer les capacités plutôt que d'entrer dans les détails techniques.

Analyser chaque cluster

Après avoir obtenu le nombre optimal de clusters, chacun d’eux doit être étudié en détail. Nous devons voir quels sont les spawns qui y sont inclus et les valeurs qu'ils prennent. Créons nos propres paramètres pour chaque cluster pour une utilisation ultérieure par génération. Les paramètres incluent :

• Poids ennemis pour calculer la probabilité. Par exemple, un zombie normal = 5 et un zombie avec un casque = 1. Par conséquent, la probabilité qu'il y en ait un normal est de 5/6 et un zombie avec un casque est de 1/6. Les poids sont plus pratiques à utiliser.
• Valeur limite, par exemple, l'angle de rotation minimum et maximum de la zone ou sa largeur. Chaque paramètre est décrit par son propre segment, dont toute valeur est également probable.
• Les valeurs catégorielles, par exemple une balise murale ou une visibilité de point, sont décrites comme des paramètres ennemis, et ce via des poids.

Considérons les paramètres du cluster, qui peuvent être décrits verbalement comme « l'apparition d'ennemis simples quelque part à proximité du joueur, à une courte distance et, très probablement, dans des points visibles ».

Tableau du groupe 1

Voici deux astuces utiles :

• Ce n'est pas un nombre fixe d'ennemi qui est précisé, mais un segment dans lequel son numéro sera sélectionné. Cela permet d'opérer avec le même ennemi dans des groupes différents mais en quantités différentes.
• Ce n'est pas le rayon extérieur (R) qui est précisé, mais le delta (R-delta) par rapport au rayon intérieur (r), afin que la règle R > r soit respectée. Ainsi, R-delta est ajouté au r aléatoire, r+R-delta > r pour tout R-delta > 0, ce qui signifie que tout va bien.

Cela a été fait avec chaque cluster, et il y en avait moins de 10, donc cela n'a pas pris longtemps.

Quelques choses intéressantes sur le clustering

Nous n’avons qu’effleuré ce sujet, mais il reste encore beaucoup de choses intéressantes à étudier. Voici quelques articles pour référence ; ils fournissent une bonne description des processus de travail avec les données, de regroupement et d'analyse des résultats.

• Pokmean — Regroupement KMean dans Pokedex
• Regroupement des jeux League of Legends
• Regroupement des joueurs de terrain FIFA20

Le temps d'une mission

En plus des modèles d'apparition, nous avons décidé d'étudier la dépendance de la santé totale des ennemis au sein d'une mission sur le moment prévu de son achèvement afin d'utiliser ce paramètre lors de la génération.

Dans le processus de création de missions manuelles, la tâche consistait à établir un rythme coordonné pour le chapitre — une séquence de missions : courte, longue, courte, encore courte, et ainsi de suite. Comment pouvez-vous obtenir la santé totale des ennemis au cours d'une mission si vous connaissez le DPS attendu du joueur et son temps ?

💡 La régression linéaire est une méthode de reconstruction de la dépendance d'une variable par rapport à une ou plusieurs autres variables avec une fonction de dépendance linéaire. Les exemples ci-dessous considéreront exclusivement la régression linéaire à partir d'une variable : f(x) = wx + b.

Introduisons les termes suivants :

• HP est la santé totale des ennemis dans la mission
• Le DPS est les dégâts attendus du joueur par seconde
• Le temps d'action est le nombre de secondes que le joueur passe à détruire les ennemis au cours de la mission.
• Le temps libre est le temps supplémentaire pendant lequel le joueur peut, par exemple, changer de cible.
• Le temps de mission prévu est la somme de l'action et du temps libre

Donc, HP = DPS * temps d'action + temps libre. Lors de la création d'un chapitre de manuel, nous avons enregistré la durée prévue de chaque mission ; maintenant, nous devons trouver du temps pour agir.

Si vous connaissez le temps de mission prévu , vous pouvez calculer le temps d'action et le soustraire du temps prévu pour obtenir du temps libre : temps libre = temps de mission - temps d'action = temps de mission - HP * DPS. Ce nombre peut ensuite être divisé par le nombre moyen d'ennemis dans la mission, et vous obtenez du temps libre par ennemi. Il ne reste donc plus qu'à construire une régression linéaire du temps de mission attendu au temps libre par ennemi.

De plus, nous construirons une régression de la part du temps d’action par rapport au temps de mission.

Regardons un exemple de calculs et voyons pourquoi ces régressions sont utilisées :

1. Entrez deux nombres : le temps de mission et le DPS sont 30 et 70.
2. Voyez la régression de la part du temps d'action par rapport au temps de mission et obtenez la réponse, 0,8
3. Calculez le temps d'action comme 30*0,8=6 secondes
4. Calculez HP comme 6*70=420
5. Voyez la régression du temps libre par ennemi par rapport au temps de mission et obtenez la réponse, qui est de 0,25 seconde.

Voici une question : pourquoi avons-nous besoin de connaître le temps libre de l'ennemi ? Comme mentionné précédemment, les apparitions sont organisées par temps. Par conséquent, le temps de la ième apparition peut être calculé comme la somme du temps d'action de la (i-1)ième apparition et du temps libre qu'elle contient.

Et voici une autre question : pourquoi la part du temps d’action et du temps libre n’est-elle pas constante ?

Dans notre jeu, la difficulté d'une mission est liée à sa durée. Autrement dit, les missions courtes sont plus faciles et les missions longues sont plus difficiles. L'un des paramètres de difficulté est le temps libre par ennemi. Il y a plusieurs lignes droites dans le graphique ci-dessus et elles ont le même coefficient de pente (w), mais un décalage (b) différent. Ainsi, pour changer la difficulté, il suffit de changer le décalage : augmenter b rend le jeu plus facile, le diminuer le rend plus difficile, et les nombres négatifs sont autorisés. Ces options vous aident à changer la difficulté d'un chapitre à l'autre.

Je pense que tous les concepteurs devraient se pencher sur le problème de la régression, car cela aide souvent à déconstruire d'autres projets :

• Tutoriel de régression linéaire
• Projet d'apprentissage automatique de base - Régression linéaire
• Régression linéaire Scikit-learn pour débutant

Générer de nouvelles missions

Nous avons donc réussi à trouver les règles du générateur, et nous pouvons maintenant passer au processus de génération.

Si vous pensez de manière abstraite, alors n'importe quelle mission peut être représentée comme une séquence de nombres, où chaque nombre reflète un groupe d'apparition spécifique. Par exemple, mission : 1, 2, 1, 1, 2, 3, 3, 2, 1, 3. Cela signifie que la tâche de générer de nouvelles missions revient à générer de nouvelles séquences numériques. Après génération, il vous suffit de « développer » chaque numéro individuellement conformément aux paramètres du cluster.

Approche de base

Si nous considérons une méthode triviale de génération d’une séquence, nous pouvons calculer la probabilité statistique d’une apparition particulière après une autre apparition. Par exemple, nous obtenons le schéma suivant :

Le haut du diagramme est un cluster auquel il mène, un sommet, et le poids du bord est la probabilité que le cluster soit le prochain.

En parcourant un tel graphique, nous pourrions générer une séquence. Cependant, cette approche présente un certain nombre d'inconvénients. Ceux-ci incluent, par exemple, le manque de mémoire (il ne connaît que l'état actuel) et le risque de « rester coincé » dans un état s'il a une forte probabilité statistique de se transformer en lui-même.

✍🏻 Si l'on considère ce graphique comme un processus, on obtient une simple chaîne de Markov.

Réseaux de neurones récurrents

Tournons-nous vers les réseaux de neurones, notamment récurrents puisqu'ils ne présentent pas les inconvénients de l'approche de base. Ces réseaux sont efficaces pour modéliser des séquences telles que des caractères ou des mots dans des tâches de traitement du langage naturel. Pour faire simple, le réseau est entraîné à prédire le prochain élément de la séquence en fonction des précédents.

Une description du fonctionnement de ces réseaux dépasse le cadre de cet article, car il s’agit d’un sujet vaste. Voyons plutôt ce qui est nécessaire pour la formation :

• Un ensemble de N séquences de longueur L
• La réponse à chacune des N séquences est un un chaud vecteur, c'est-à-dire un vecteur de longueur C composé de C-1 zéros et d'un 1, indiquant la réponse.
• C est la puissance de l’ensemble des réponses.

Un exemple simple avec N=2, L=3, C=5. Prenons la séquence 1, 2, 3, 4, 1 et recherchons des sous-séquences de longueur L+1 à l'intérieur : [1, 2, 3, 4], [2, 3, 4, 1]. Divisons la séquence en une entrée de L caractères et une réponse (cible) - le (L+1)ème caractère*.* Par exemple, [1, 2, 3, 4] → [1, 2, 3] et [ 4]. Nous codons les réponses dans des vecteurs uniques, [4] → [0, 0, 0, 0, 1].

Ensuite, vous pouvez esquisser un réseau neuronal simple en Python à l'aide de tensorflow ou de pytorch. Vous pouvez voir comment cela se fait en utilisant les liens ci-dessous. Il ne reste plus qu'à démarrer le processus de formation sur les données décrites ci-dessus, attendre, et... vous pourrez ensuite passer en production !

Les modèles d'apprentissage automatique comportent certaines mesures, telles que la précision. La précision montre la proportion de réponses correctement données. Cependant, il faut l’examiner avec prudence car il peut y avoir des déséquilibres de classe dans les données. S’il n’y en a pas (ou presque), alors on peut dire que le modèle fonctionne bien s’il prédit mieux les réponses qu’au hasard, c’est-à-dire avec une précision > 1/C ; si proche de 1, cela fonctionne très bien.

Dans notre cas, le modèle a montré une bonne précision. L'une des raisons de ces résultats est le petit nombre de clusters obtenus grâce à la cartographie des ennemis selon leurs types et leur équilibre.

Voici plus de documents sur RNN pour les personnes intéressées :

• Guide du débutant sur la génération de texte à l'aide des LSTM
• Lutter contre les substances toxiques à l'aide de Keras
• Explorer les jeux avancés Gameboy

Processus de génération

Configuration du générateur

Le modèle formé est facilement sérialisé , vous pouvez donc l'utiliser comme un atout dans le moteur, dans notre cas, Unity. En conséquence, le générateur accède au modèle via une API et crée une séquence de manière itérative. Le résultat est développé et enregistré dans un fichier CSV distinct.

Pour interagir avec le modèle, une fenêtre personnalisée est créée dans Unity où les concepteurs du jeu peuvent définir tous les paramètres de mission nécessaires :

• Nom
• Durée
• Ennemis disponibles, au fur et à mesure que les ennemis apparaissent progressivement
• Nombre de vagues dans la mission et répartition de la santé à travers elles
• Modificateurs de poids spécifiques aux ennemis, qui aident à sélectionner certains ennemis plus souvent, par exemple de nouveaux
• Et ainsi de suite

Après avoir entré les paramètres, il ne reste plus qu'à appuyer sur un bouton et obtenir un fichier qui peut être modifié si nécessaire. Oui, je voulais générer des missions à l'avance, et non pendant le jeu, afin de pouvoir les peaufiner.

Les étapes de génération

Examinons le processus de génération :

1. Le modèle reçoit une séquence en entrée et produit une réponse – un vecteur de probabilités que le i-ème cluster soit le prochain. L'algorithme lance les dés, si le nombre est supérieur au risque d'erreur , alors nous prenons le plus probable, sinon aléatoire. Cette astuce ajoute un peu de créativité et de variété.
2. Le processus se poursuit jusqu'à un nombre donné d'itérations. C'est supérieur au nombre d'apparitions dans n'importe laquelle des missions créées manuellement.
3. La séquence continue ; c'est-à-dire que chaque numéro accède aux données enregistrées du cluster et en reçoit des valeurs aléatoires.
4. La santé à l'intérieur des données est résumée et tout ce qui est supérieur à la santé attendue est exclu de la séquence (son calcul a été discuté ci-dessus)
5. Les apparitions sont divisées en vagues en fonction de la répartition de la santé spécifiée, puis divisées en groupes (de sorte que plusieurs ennemis apparaissent en même temps), et leur temps d'apparition est donné comme la somme de l'action et du temps libre du groupe d'apparitions précédent.
6. La mission est prête !

Conclusions

C’est donc un bon outil qui nous a aidé à accélérer plusieurs fois la création de missions. De plus, cela a aidé certains concepteurs à surmonter la peur du « blocage de l'écrivain », pour ainsi dire, puisque vous pouvez désormais obtenir une solution toute faite en quelques secondes.

Dans l'article, en utilisant l'exemple de la génération de missions, j'ai essayé de démontrer comment les méthodes classiques d'apprentissage automatique et les réseaux de neurones peuvent aider au développement de jeux. Il existe aujourd’hui une énorme tendance vers l’IA générative – mais n’oubliez pas les autres branches de l’apprentissage automatique, car elles sont également capables de beaucoup de choses.

Merci d'avoir pris le temps de lire cet article ! J'espère que vous avez une idée à la fois de l'approche des missions dans les lieux générés et de la génération des missions. N'ayez pas peur d'apprendre de nouvelles choses, de vous développer et de créer de bons jeux !

Illustrations de shabbyrtist