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.
Avertissement : cet article est uniquement à des fins d'information/de divertissement, et lorsque vous utilisez une solution particulière, nous vous conseillons de vérifier attentivement les conditions d'utilisation d'une ressource particulière et de consulter le personnel juridique !
☝🏻 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 :
À 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.
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 :
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.
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 :
Examinons ce deuxième point un peu plus en détail.
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
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.
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 :
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
Ennemis | Taper | r | R-delta | rotation | largeur | visibilité |
---|---|---|---|---|---|---|
zombie_common_3_5=4, zombie_heavy=1 | Joueur | 10-12 | 1-2 | 0-30 | 30-45 | Visible=9, Invisible=1 |
Voici deux astuces utiles :
Cela a été fait avec chaque cluster, et il y en avait moins de 10, donc cela n'a pas pris longtemps.
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.
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 :
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 :
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 :
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.
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.
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 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 :
Le modèle formé est facilement
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 :
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.
Examinons le processus de génération :
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