Concevoir l'Intelligence Artificielle pour les Jeux Vidéo - Tactique et stratégie

Partie 3 : Tactique et stratégie

Donald Kehoe

Les articles précédents de cette série ont abordé les bases du sujet. Vous avez à présent une bonne compréhension de ce qu'est l'intelligence artificielle (IA) pour les jeux vidéo et une bonne connaissance de la façon de l'implémenter dans vos propres jeux. Abordons maintenant la partie la plus difficile, maximiser les performances de votre système.

- Titre : Concevoir l'Intelligence Artificielle pour les Jeux Vidéo - Tactique et stratégie

- Auteur : Donald Kehoe

- Parution : 30 octobre 2015

- Licence : Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright ® 2015 Donald Kehoe. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Sommaire

- I. Tirer le meilleur de votre IA : le threading

- II. Parallélisation des tâches

- III. Trouver un parcours (pathfinding)

- III-A. IA stratégique

- III-B. Parallélisation des données

- III-C. Implémentation

- III-D. Résolution des conflits

- III-E. Maintenir la synchronisation

- III-F. Recommandations pour le threading

- III-G. Quand ne faut-il pas utiliser les threads

- IV. Résumé

- V. Ressources:

- VI. À propos de l'auteur

- VII. Crédits

I - Tirer le meilleur de votre IA : le threading

Quelles que soient les qualités de votre système, il n'aura aucun intérêt s'il ralentit le jeu. Une programmation efficace et des astuces d'optimisation vous aideront à aller plus loin ; lorsque vos aspirations vont au-delà des capacités d'un seul cœur, vous devrez penser à la parallélisation (voir Figure 1).

Figure 1 : Dans Starcraft II* de Blizzard Entertainment, un nombre considérable d'unités sont contrôlées en même temps par l'IA. La meilleure façon de toutes les gérer est le multithreading (ou parallélisation).

Lorsque vous travaillez avec un système qui possède plus d'un processeur ou qui dispose d'un processeur avec plusieurs cœurs, vous pouvez répartir le travail aux différents processeurs. Pour ce faire, il existe deux approches : la parallélisation des données et la parallélisation des tâches.

II - Parallélisation des tâches

La meilleure façon de mettre en place la parallélisation est de commencer par décomposer les processus en tâches spécifiques (voir Figure 2). Les différentes tâches qui constituent le moteur du jeu sont souvent encapsulées de la même façon afin que les autres systèmes puissent communiquer avec eux.

Figure 2 : La parallélisation fonctionnelle permet à chaque sous-système d'avoir son propre thread et son propre cœur. Malheureusement, les systèmes qui disposent de plus de cœurs que de tâches à accomplir seront sous-utilisées.

Prenons le système audio du moteur du jeu comme premier exemple. L'audio n'a pas besoin d'interagir avec d'autres systèmes : il fait exactement ce qu'il a à faire, à savoir jouer et mixer des sons à la demande. Les fonctions de communication sont des appels à démarrer et à s'arrêter des sons, ce qui fait de l'audio une tâche autonome qui est tout à fait adaptée à la parallélisation fonctionnelle. En utilisant des outils d'analyse de threading pour vous aider, le système audio peut être interrompu dans son propre thread, avec un appel avant et après la section de code que vous voulez exécuter dans son propre thread.

Nous allons donc voir comment vos systèmes d'IA bénéficient de cette parallélisation fonctionnelle. En fonction des besoins de votre jeu, vous pouvez avoir de nombreuses tâches distinctes auxquelles vous pouvez attribuer leur propre thread. Nous allons nous intéresser à trois d'entre eux : le parcours, la stratégie de l'IA et le système de l'entité.

III - Trouver un parcours (pathfinding)

Vous pouvez implémenter votre système de pathfinding afin que chaque entité qui cherche son chemin appelle son propre parcours à chaque fois qu'elle en a besoin. Bien que cette méthode fonctionne, elle implique que le moteur attende le pathfinder à chaque fois qu'un parcours est demandé. Si vous réorganisez la structure pour que le pathfinding dispose de son propre système, vous dépasserez ce problème. Le pathfinder fonctionnera comme un gestionnaire de ressources dans lequel la nouvelle ressource sera les parcours.

Toute entité qui cherchera un parcours pourra envoyer une requête, puis obtiendra immédiatement un ticket de la part du pathfinder. Le ticket est simplement un identificateur unique que le système de pathfinding peut utiliser pour trouver un parcours. L'entité peut alors continuer son chemin jusqu'au prochain cadre de la boucle de jeu. L'entité peut vérifier si le ticket est encore valide. Si c'est le cas, l'entité obtiendra le parcours en retour ; sinon, elle peut continuer son activité tout en continuant à attendre.

Dans le système de pathfinding, le ticket est utilisé pour garder une trace des demandes de parcours alors que le système fonctionne sans se soucier de l'effet sur les performances du système. Ce style de système permet également un deuxième effet positif, le suivi automatique des chemins découverts. Lorsqu'une requête de chemin déjà découvert arrive, le pathfinder peut simplement fournir le ticket du parcours existant. Cette méthode est parfaite dans tout système qui comporte beaucoup d'entités qui ont leur propre parcours, tous les chemins trouvés une fois seront probablement utiles à nouveau.

III-A - IA stratégique

Comme mentionné dans l'article précédent, le système d'IA qui gère l'ensemble du jeu mérite bien son propre thread. Il peut analyser l'ensemble du jeu et envoyer différentes commandes aux entités, qui peuvent les analyser lorsqu'ils se déplacent.

Le système d'entité, dans son propre thread, aura du mal à recueillir des informations pour la carte de décisions. Ces résultats peuvent ensuite être envoyés au système stratégique de l'IA au fur et à mesure que les requêtes de mise à jour des cartes de décisions arrivent. Lorsque l'IA stratégique se met à jour, elle peut analyser ces requêtes, mettre à jour les cartes de décision, et faire preuve de jugement. Peu importe que les deux systèmes (AI stratégique et entité) soient synchronisés ou non : le temps de synchronisation n'affectera pas les décisions de l'IA. (Nous parlons ici de 60 millièmes de seconde, le joueur ne remarquera pas le décalage du temps de réaction de l'IA.)

III-B - Parallélisation des données

La parallélisation fonctionnelle est très utile et tire le meilleur parti des systèmes disposant de plusieurs cœurs. Mais elle a également un gros inconvénient : la parallélisation fonctionnelle ne peut pas exploiter pleinement tous les cœurs disponibles. Dès l'instant où vous disposez de plus de cœurs que de tâches à accomplir, votre programme n'utilisera pas toute la puissance de traitement disponible (sauf si la plate-forme sur laquelle fonctionne votre programme le prend en charge, mais je pense qu'il est préférable de ne pas compter sur les fonctionnalités destinées à des applications génériques). Parallélisation des données (voir Figure 3).

Figure 3 : Avec la parallélisation des données, une seule fonction peut utiliser tous les cœurs disponibles.

Avec la parallélisation fonctionnelle, vous avez donné à une unité autonome son propre thread. À présent vous allez diviser une seule tâche et répartir le travail à effectuer entre plusieurs threads. Cette méthode permet d'exploiter tous les cœurs du système. Vous disposez d'un système avec huit cœurs ? Formidable. Vous en avez un avec 64 ? Pourquoi pas ? Bien que la parallélisation fonctionnelle vous permette de désigner des sections de codes comme attribuées à des threads, et les laisser fonctionner librement, la parallélisation des données nécessite un peu de travail supplémentaire pour obtenir un fonctionnement parfait. Pour l'un d'eux, vous pouvez utiliser un thread (un « Master Thread ») qui se souvient de qui fait quoi. Les threads secondaires ou sub-threads devront effectuer des requêtes au thread principal pour s'assurer que personne n'effectue la même tâche deux fois.

L'utilisation d'un thread principal pour gérer la parallélisation des données est en réalité une approche hybride. Le thread principal utilise la parallélisation fonctionnelle, mais le thread répartit les données dans les différents cœurs pour la parallélisation des données.

III-C - Implémentation

Des outils de threading comme OpenMP* (disponible gratuitement sur la plupart des systèmes d'exploitation) permettent de diviser plus facilement le processus de code dans des threads indépendants. Vous avez simplement à marquer les sections de code qui peuvent être décomposées avec une directive de compilation et OpenMP se charge du reste. Pour diviser par bloc de travail, vous pouvez simplement mettre les appels de threading dans la boucle qui passe par ladite ressource.

Dans l'exemple du système pathfinding, le pathfinder conserve une liste des parcours demandés. Il boucle ensuite dans cette liste et exécute les fonctions réelles de pathfinding pour les demandes individuelles en les conservant dans une liste de parcours. Cette boucle peut être attribuée à un thread de sorte que chaque itération de la boucle sera divisée en différents threads. Ces threads seront exécutés dans le premier cœur disponible, permettant une utilisation maximale de la puissance de traitement. Le seul moment où un cœur doit être inactif c'est lorsqu'il n'a rien à faire.

Avec ce genre de systèmes, il est possible que de multiples requêtes soient envoyées pour la même tâche. Si ces demandes sont espacées, le pathfinder vérifie automatiquement si la requête a déjà été traitée. Lorsque vous vous occupez de parallélisation des données, il est possible que plusieurs requêtes pour le même parcours se produisent en même temps, ce qui peut conduire à des redondances, rendant le threading inutile.

Pour résoudre ce problème et ceux causés par des redondances, le système doit garder une trace des tâches en cours d'exécution et les supprimer de la file d'attente après qu'elles soient terminés. Lorsqu'une requête arrive pour un parcours déjà demandé, il doit vérifier, puis renvoyer le parcours existant déjà attribué à ce ticket.

Multiplier les threads n'est pas anodin. Le processus impliquera des appels système au système d'exploitation (OS). Lorsque le système d'exploitation aura le temps, il terminera le code nécessaire et créera le thread. Cela peut prendre beaucoup de temps (selon la vitesse de traitement). Voilà pourquoi nous ne voulons pas créer plus de threads que nécessaire. Si la tâche demandée a déjà été traitée, il ne faut pas l'effectuer à nouveau. De plus, si la tâche est simple (comme trouver un parcours entre deux points très proches), ce ne sera pas la peine de diviser la tâche si finement.

Voici la répartition du thread du pathfinding fonctionnel et la façon dont le travail sera réparti entre les threads de données :

- RequestPath (démarrage, but) Cette fonction est appelée à l'extérieur du pathfinder pour obtenir un thread. Cette fonction :

- passe par la liste des demandes traitées et détermine si le parcours a déjà été trouvé (ou un parcours similaire), puis retourne le ticket correspondant ;

- passe par la liste de demande active (si le parcours n'a pas été trouvé) pour trouver ce parcours ; si le chemin existe, la fonction retourne le ticket correspondant ;

- génère une nouvelle requête et renvoie un nouveau ticket (si tout le reste a échoué).

- CheckPath (« ticket »). Utilise le ticket, cette fonction passe par la liste de requêtes complétées et trouve le parcours pour lequel ce ticket est valide. Retour sur le parcours.

- UpdatePathFinder().C'est la fonction de guide qui gère la surcharge pour les threads de pathfinding. Cette fonction effectue les tâches suivantes :

- Analyser les nouvelles requêtes. Il est possible que plusieurs requêtes pour un même trajet aient été générées en même temps sur différents cœurs. Cette section supprime les redondances et assigne des tickets (à partir des différentes demandes) à la même demande.

- Boucle à travers les requêtes actives. Cette fonction parcourt toutes les requêtes actives et les attribue à des threads. Au début et à la fin de chaque boucle, le code est marqué comme un thread. Chaque thread va (1) trouver le chemin demandé (2) l'enregistrer dans la liste des chemins complétés avec les tickets correspondants, et (3) supprimer la tâche de la liste active.

III-D - Résolution des conflits

Vous avez sans doute remarqué que cette configuration peut être à l'origine de conflits. Différents threads qui doivent tous être mis en file d'attente des requêtes ou dans les threads de données qui doivent tous augmenter la pile de tâches terminées peuvent conduire à des conflits d'écriture. Là où un thread écrit quelque chose dans l'emplacement A alors qu'un autre écrit quelque chose d'autre dans ce même emplacement en même temps. Ce conflit peut conduire au problème bien connu « race condition ».

Pour éviter ces conflits, des sections de code peuvent être marquées comme « critiques ». Lorsqu'une section est marquée comme critique, elle est uniquement accessible à un seul thread à la fois : tous les autres threads qui veulent faire la même chose (accéder à la même partie de la mémoire) devront attendre. Cette méthode peut conduire à d'énormes problèmes, comme des embouteillages, lorsque plusieurs threads se bloquent l'un l'autre l'accès à la mémoire. Avec cette configuration, on évite les problèmes d'embouteillages. Une fois le travail effectué sur les threads, l'accès à la section critique de la mémoire peut se faire lorsqu'elle est disponible sans monopoliser d'autres sections dont d'autres threads pourraient avoir besoin.

III-E - Maintenir la synchronisation

Vous avez donc mis en place différents sous-systèmes autonomes d'IA et pouvez profiter de toutes les ressources de calcul disponibles. Tout fonctionne rapidement, mais vous rencontrez des problèmes de contrôle ?

Un jeu doit être une expérience structurée. Un moteur de jeu doit être capable de maintenir la synchronisation. Vous ne pouvez pas permettre que certains éléments de votre jeu fonctionnent sans prendre en compte les autres. Vous ne voulez pas que des unités restent immobiles, en attente d'un chemin d'accès, alors que des unités semblables sont déjà en mouvement. Les bons parents doivent traiter tous leurs enfants de manière équitable.

La boucle principale du moteur de jeu s'occupe de deux classes d'actions : la mise à jour et le rendu. Maintenir la synchronisation est facile dans la programmation en série. Tout d'abord, les mises à jour sont effectuées, puis le rendu dessine ce qui a été mis à jour. En parallèle, les choses peuvent être un peu complexes.

Les mises à jour de mouvement (souvent basées sur la trajectoire) peuvent finir par provoquer un rendu plus lent que pour d'autres cadres. Il en résultera des animations saccadées, où les images des entités semblent sauter et se déplacer plus vite que la normale. Le pathfinding, qui prend en considération une image des positions des entités du monde, fonctionne peut-être en prenant en compte des données invalides.

La solution à ce problème est de conserver la simplicité de la synchronisation des différents systèmes. En réalité, pour la plupart des moteurs, elle est peut-être déjà en place. Lors des principales mises à jour de la boucle de jeu, le moteur garde une trace d'un indice global de temps. Tous les différents threads s'assureront de gérer uniquement les mises à jour actuelles (et les précédentes, mais pas les suivantes) de l'indice de temps.

Lorsqu'une tâche donnée est terminée pour l'indice de temps, le thread peut passer en sommeil jusqu'au nouvel indice de temps. Non seulement ce comportement permet de veiller à la synchronisation, mais il empêche aussi que les threads n'utilisent les ressources des cœurs alors qu'ils n'en ont pas besoin. Le travail de mouvement, parfaitement capable de résoudre les problèmes de collisions et de trajectoires de mouvement, partagera la puissance de traitement lorsque cela est fait suffisamment tôt. Encore une fois, vous pourrez profiter pleinement de tous les cœurs disponibles.

III-F - Recommandations pour le threading

Voici quelques notions à garder à l'esprit lorsque vous concevez un système multithread :

- Parallélisation fonctionnelle : Utilisez-la lorsque le système peut être autonome. Certaines fonctions sont nécessaires afin que le système puisse résoudre les conflits et les redondances.

- Parallélisation des données :

- Utilisez la parallélisation des données lorsque vous faites des opérations dont les résultats ne sont pas prévisibles.

- Mettez-la en œuvre de telle sorte que les reprises soient minimes et s'exécutent à la fin du processus.

- Si la fiabilité des informations mises à jour (qui peut être édité dans d'autres threads) est minime ou n'est pas pertinente. (Alors que faire si mes informations de stratégie ont un temps de mise à jour de 60 millièmes de seconde ?)

- Assurez-vous que cette tâche n'ait besoin de rien d'autre du système qui bloque le thread : "Request Path," "Check for path" et non "Get Path."

III-G - Quand ne faut-il pas utiliser les threads

Les threads peuvent ne pas fonctionner dans certains cas. Avec des outils comme OpenMP, vous pouvez facilement modifier le nombre de threads dans lesquels votre système répartira les tâches à accomplir. En utilisant des outils comme Intel® VTuneTMPerformance Analyzer avec Intel® Thread Profiler, vous pouvez avoir une bonne vue d'ensemble de l'efficacité de votre système avec différents niveaux de parallélisation. Voici quelques cas dans lesquels vous devriez éviter le threading :

- Systèmes trop complexes. Si votre sous-système est lié à un trop grand nombre d'autres systèmes qui causent constamment des temps d'attente au niveau du sous-système ou d'autres systèmes, le threading n'est pas forcément le bon choix. Il est possible que le système lui-même nécessite une refonte totale.

- Charge de travail indivisible. Si le travail du sous-système ne peut être décomposé, vous n'arriverez peut-être pas à mettre en place la parallélisation. Le mixage audio peut fonctionner en tant que thread, la tâche consiste à mélanger des sons multiples dans des canaux qui sont finalement envoyés vers les haut-parleurs. Si votre système fait des calculs sur des morceaux individuels de l'audio du jeu avant de les mélanger, il est possible de répartir les tâches en threads.

- Charge de travail trop importante. Ces systèmes demandent un peu de travail supplémentaire (pour le cheminement des entités par exemple). Si le temps passé est trop important au regard de l'intérêt du threading, il sera alors plus pertinent de le désactiver. Notamment dans les systèmes avec un petit nombre d'éléments (entités, parcours, etc.).

- Répétition de code. Dans certains cas, plusieurs threads travaillent sur le même code, ce qui implique que certains des calculs ne seront pas utilisés ou ignorés. Ce problème peut être évité avec des contrôles de redondance avant le début des calculs.

Les systèmes avec plusieurs processeurs et/ou équipés de processeurs multi-cœurs (et ceux avec plusieurs processeurs multi-cœurs) rendent le threading de plus en plus utile. L'objectif de tout programmeur est de tirer pleinement parti de la puissance de traitement disponible. L'AI d'un système devrait uniquement être limitée par le matériel, et non par l'utilisation de celui-ci. Avec des outils modernes qui rendent le threading plus facile à mettre en œuvre, vous n'avez aucune excuse pour ne pas concevoir votre code avec des threads.

IV - Résumé

Faire fonctionner un système d'IA dynamique et captivant est aujourd'hui facile. L'efficacité et l'optimisation en sont la première étape. En organisant votre système pour profiter pleinement de la parallélisation des données et des tâches, vous vous assurez que votre système fonctionnera aussi vite que possible et sera en mesure de se développer parallèlement à l'industrie informatique qui propose des processeurs avec de plus en plus de cœurs.

Comme cette série d'articles l'a montré, l'IA pour les jeux est plus artificielle qu'intelligente. En tant que programmeurs, notre métier est de donner des capacités aux agents du système afin d'émuler le comportement de leurs homologues du monde réel. Du pathfinding aux commandes stratégiques et tactiques des IA, il est relativement simple de mettre en œuvre des IA au regard des composants de base.

Pour plus d'informations sur le développement de jeux, rendez-vous sur la  Zone des développeurs Intel. Retrouvez également des astuces, conseils et retours d'expériences sur le forum Intel.

V - Ressources:

- Unity Ressource Center

- Intel GameDev Tools

- Intel GPA

- Intel INDE

VI - À propos de l'auteur

Donald « DJ » Kehoe : Formateur au sein du Programme de Technologie de L'Information du New Jersey Institute, DJ s'est spécialisé dans le développement de jeux vidéo et enseigne dans de nombreux cours du programme sur « Architecture, Programmation et Conception de niveau dans les Jeux Vidéo, ainsi que d'autres cours sur l'Intégration des Graphismes 3D dans les jeux. Il travaille actuellement pour obtenir son doctorat en Génie Biomédical, il utilise le jeu et la réalité virtuelle pour améliorer les méthodes de réadaptation neuromusculaire.

VII - Crédits

*StarCraft II* est une marque déposée et un produit déposé de Blizzard Entertainment, Inc. et est utilisé avec sa permission.