Concevoir l'intelligence artificielle pour les jeux vidéo

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.

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'elles 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.)

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).

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.

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 blocs 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ées. 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.

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.