L’apprentissage par renforcement profond pour la navigation dans les jeux vidéo AAA

Dans cet article, nous présentons notre approche proposant l’utilisation de l’apprentissage par renforcement profond (Deep RL, de l’anglais “Deep Reinforcement Learning”) comme alternative aux solutions existantes pour la navigation dans les jeux vidéo AAA.

La navigation est un élément crucial dans la conception des Personnages Non Joueurs (PNJ) d’un jeu, car elle permet au PNJ de se déplacer d’un point à un autre dans le monde. Dans l’industrie du jeu vidéo, l’approche la plus populaire pour la navigation des PNJ consiste à utiliser un Mesh de Navigation (NavMesh). Un NavMesh est une représentation de la carte sous forme de graphe, dont les nœuds et les arêtes indiquent les zones traversables. Malheureusement, certaines capacités de navigation complexes (par exemple les grappins, les jetpacks, la téléportation, les trampolines ou les doubles sauts) font augmenter la complexité du NavMesh, le rendant inutilisable dans de nombreux scénarios pratiques.

Comme alternative, nous proposons d’utiliser le Deep RL pour apprendre à naviguer sur des cartes en 3D en utilisant toutes les capacités de navigation disponibles. Nous avons testé notre approche dans des environnements 3D de différentes complexités. Il est intéressant de noter que la superficie maximale de ces environnements est typiquement un ordre de grandeur supérieure à celles généralement rencontrées dans la littérature de Deep RL. Enfin, nous profitons de cet article pour partager nos derniers résultats, non décrits dans la publication pour le workshop de NeurIPS 2020, où nous testons notre approche directement dans le moteur de Hyper Scape, un jeu AAA d’Ubisoft sorti cette année. Nous avons constaté que notre méthode fonctionne étonnamment bien sur tous les scénarios testés, atteignant un taux de réussite d’au moins 90 % en navigation point à point.

N’oubliez pas de consulter notre article et l’annexe vidéo sur YouTube pour plus de détails. Si vous avez des questions, n’hésitez pas à nous contacter par mail directement.

Article (PDF)

Légende

Commençons par introduire une courte légende qui, espérons-le, rendra le tout plus facile à suivre. L’agent, représenté par un cube bleu, est chargé de naviguer jusqu’à son objectif, représenté par un palet orange.

L’agent a accès aux capacités de navigation suivantes :

Pour ceux qui ne seraient pas familiers, un double saut permet à l’agent d’interrompre son premier saut en plein air, en amorçant un second saut, possiblement dans une direction différente. En ce qui concerne les trampolines, ils propulsent simplement l’agent vers le haut lorsqu’il marche dessus.

La construction d’un NavMesh en pratique

La figure 1 introduit les bases de la navigation classique, sur une carte schématique :

• Le NavMesh est généré à partir de la géométrie du monde et le représente sous forme d’un graphe de zones indépendamment traversables.
• Une fois le graphe formé, on peut trouver un chemin entre deux points quelconques du monde à l’aide d’algorithmes classiques de recherche de chemin, tels que l’algorithme de Dijkstra ou A*.
• Le chemin est ensuite lissé et donné à l’agent

Figure 1: Bases de la navigation classique sur une carte schématique

Nous avons construit une carte simple afin d’illustrer certaines limites de l’approche classique basée sur un NavMesh (Figure 3).

Cette carte est composée de bâtiments de plusieurs étages et de deux trampolines. Les toits des bâtiments sont conçus pour être accessibles uniquement par un trampoline ou par un double saut depuis le dernier étage.

Figure 2: Carte simple

Le NavMesh correspondant est en bleu dans la figure 3 ci-dessous. Cette figure illustre également certains problèmes que ce NavMesh présente lorsque l’on veut trouver un chemin entre les deux toits sur lesquels sont l’agent et son objectif. Premièrement, les trampolines ne sont pas pris en compte dans ce NavMesh. En effet, géométriquement parlant, ils ne sont pas reliés aux zones en hauteur qu’ils permettent à l’agent d’atteindre, comme le toit par exemple. Ensuite, les étages étants géométriquement séparés, ils sont donc déconnectés les uns des autres dans le NavMesh. Par conséquent, pour pouvoir intégrer les trampolines et doubles sauts nécessaires dans notre recherche de chemin, nous devons ajouter des liens supplémentaires dans le NavMesh afin de les connecter aux toits et étages environnants.

Figure 3: Carte avec NavMesh (en bleu)

Les liens supplémentaires ne passent pas bien à l’échelle

Il est parfois possible d’automatiser l’ajout de ces liens, mais cela reste un travail manuel dans beaucoup de situations. Le clip ci-dessous donne une idée du caractère laborieux de cette tâche, pour les liens partant d’un des deux trampolines, sur notre carte simple.

Figure 4: Ajout manuel de liens

Ajouter des liens supplémentaires représente donc un travail laborieux, mais le véritable problème réside dans leur impact sur la taille du NavMesh. Dans certains cas en effet, ajouter des liens supplémentaires augmente dramatiquement la taille du graphe, au point de devenir problématique non seulement de par la quantité de mémoire nécessaire mais également sur le plan du temps de calcul requis pour identifier le plus court chemin. Construire et utiliser un NavMesh complet est donc impossible dans de nombreuses situations réelles, ce qui amène à devoir faire un compromis entre le coût et la qualité de la navigation. En pratique, ce compromis est obtenu soit en supprimant certaines des capacités de navigation dès la conception, soit en supprimant la plupart des liens afin de simplifier le graphe.

Message clé

La navigation basée sur un NavMesh peut être réalisée à l’aide de liens supplémentaires, mais devient rapidement inutilisable quand le monde est grand et que le système de jeu offre des capacités de navigation complexes comme les doubles sauts, les trampolines, les jetpacks ou la téléportation.

Une solution alternative pour la navigation, basée sur l’apprentissage par renforcement

Nous allons à présent décrire notre méthode basée sur de l’apprentissage, qui présente une alternative à la navigation classique basée sur un NavMesh.

En résumé, la navigation de l’agent est régie par un réseau de neurones profond, qui agit directement sur les différentes capacités de mouvement disponibles. Ce réseau est entrainé à l’aide d’un algorithme d’apprentissage par renforcement, et son objectif est de faire naviguer l’agent de point en point sur la carte, fixe pendant tout l’entrainement.

L’architecture de notre réseau de neurones est la suivante. En entrée, il reçoit les positions de l’agent et de son objectif, une vue locale du monde environnant, représentée par une carte de profondeur en 2D et une carte d’occupation en 3D, ainsi que quelques autres informations comme sa vitesse et son accélération actuelles. Ces entrées sont ensuite consommées par des couches de convolution et des couches entièrement connectées, puis par un LSTM afin de tenir compte de l’observabilité partielle potentielle. La représentation ainsi obtenue est ensuite partagée entre les deux réseaux apprenant

respectivement la politique et la fonction de valeur. L’ensemble est entrainé à l’aide de l’algorithme Soft-Actor Critic.

Figure 5: Architecture du réseau de neurones

Nous avons étudié en détails plusieurs ablations à notre approche. En particulier, nous avons pu évaluer l’importance des différentes parties de l’entrée du réseau ainsi que des différents composants algorithmiques tels que le LSTM. Les détails complets de ces expériences sont disponibles dans notre article.

Carte simple

La vidéo suivante montre notre système de navigation à l’œuvre une fois l’entrainement terminé, sur la carte simple de 100 mètres par 100 mètres, introduite plus haut. Sur cette carte, une fois entrainé, notre agent obtient un taux de réussite de 100 % en navigation point à point.

Contrairement à une approche basée sur un NavMesh, notre méthode ne s’appuie pas sur un algorithme de recherche de chemin. À chaque instant, un réseau de neurones produit les actions de navigation pertinentes à partir de certaines informations du monde.

Agrandissement de la carte

Nous avons aussi testé notre approche dans des environnements plus représentatifs de la complexité typiquement rencontrée dans les jeux AAA. La figure ci-dessous fournit une vue aérienne de notre carte réaliste de 300 mètres de côté, qui compte de nombreux trampolines et obstacles en tout genre.

Figure 6: Carte réaliste

Le même système permet d’obtenir un taux de réussite de 93% pour la navigation point à point. Notons que l’agent n’échoue pas nécessairement les 7 % restants, car il peut ne pas exister de trajectoire faisable entre les deux points demandés.

Carte d’Hyper Scape

Enfin, nous poussons notre système de Deep RL un cran plus loin, en le testant dans Hyper Scape, un jeu AAA récemment produit par Ubisoft. L’agent est chargé de résoudre plusieurs cartes allant jusqu’à 1 kilomètre de côté. La vidéo ci-dessous présente notre solution de navigation implémentée directement dans l’engin d’Hyper Scape. À noter que ces résultats étant très récents, ils ne sont pas présentés dans notre article original.

Dans ce travail, nous avons montré que l’apprentissage par renforcement et les réseaux de neurones profonds peuvent être une alternative au NavMesh pour la navigation dans des environnements 3D complexes, comme les cartes rencontrées dans les jeux vidéo AAA. Contrairement à un NavMesh, notre approche basée sur l’apprentissage tient naturellement compte des capacités de navigations disponibles, sans avoir besoin de spécifier manuellement des liens supplémentaires. Nous constatons que notre approche fonctionne étonnamment bien dans tous les scénarios testés. Dans le cadre de nos futurs travaux, nous prévoyons de tester dans quelle mesure cette approche peut être généralisée à de nouvelles cartes qui n’ont pas été vues pendant l’entrainement.

Auteurs

ELOI ALONSO, Ubisoft La Forge, Canada
MAXIM PETER, Ubisoft La Forge, Canada
DAVID GOUMARD, Ubisoft La Forge, Canada
JOSHUA ROMOFF, Ubisoft La Forge, Canada