Concevoir l'intelligence artificielle pour les jeux vidéo

Partie 2 : Perceptions et Pathfinding

Donald Kehoe

Dans l'article précédent, je vous parlais des méthodes de prise de décisions de base d'un agent intelligent contrôlé par une intelligence artificielle (IA). Dans cet article, je place notre héros (ou monstre ou tout type d'entité dans le jeu) dans un environnement pour qu'il y puisse prendre les décisions adaptées. Les agents intelligents doivent identifier les points d'intérêt dans l'environnement du jeu, puis comprendre comment y accéder. En fin d'article, j'aborderai l'optimisation de ces méthodes et vous expliquerai les moyens de les organiser en tenant compte des techniques de parallélisation (multithreading).

Dans cet article, les IA évoquées s‘approchent terriblement de l'intelligence artificielle réelle. Tous les agents intelligents doivent pouvoir percevoir leur environnement et parvenir à s'y déplacer. Vos entités devront faire la même chose, mais avec une approche très différente. Vous pouvez également tricher pour vous assurer que tout fonctionne de façon fluide et rapide.

N'hésitez pas à donner votre avis sur cet article sur le forum : Commentez

- Titre : Concevoir l'intelligence artificielle pour les jeux vidéo

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

Voir également :

- Concevoir l'intelligence artificielle pour les jeux vidéo - Partie 1 : Conception et implémentation

Sommaire

- I. Perception de l'IA

- I-A. La vue

- I-B. L'ouïe

- I-C. Les autres sens

- I-D. Entités temporaires

- I-E. La couverture

- II. Parcours de l'IA

- II-A. Crash and Turn

- II-B. Trouver son chemin

- III. Exemple de code

- IV. Résumé

- V. À propos de l'auteur

- VI. Ressources

I - Perception de l'IA

La prise de décisions arbitraires de vos agents convient très bien à certains jeux, mais que faire si vous voulez aller plus loin ? Pour que votre agent prenne des décisions correctes, il devra savoir ce qui se passe autour de lui. Dans les applications robotiques de l'IA, de nombreuses recherches sur la vision par ordinateur sont en cours. Elles permettent aux robots d'avoir la capacité de percevoir le monde qui les entoure dans un environnement réel, en vision stéréoscopique et en trois dimensions (3D), tout comme le font les humains. Ce niveau de sophistication dépasse totalement nos besoins.

Les mondes virtuels dans lesquels se déroulent la plupart des jeux ont un énorme avantage sur les robots disposant d'une IA dans le monde réel. Tout dans ce monde correspond à une quantité connue : vous disposez d'une liste de tout ce qui existe dans le jeu. Vous pouvez simplement consulter cette liste pour connaître n'importe quel critère, et avoir immédiatement accès aux informations que votre agent pourra utiliser pour prendre une décision éclairée.

I-A - La vue

Reproduire la vue d'une entité correspond au niveau le plus fondamental des capacités perceptives de l'agent. Vous pouvez le faire en demandant à vos entités de détecter tout ce qui se trouve dans leur champ de vison. Vous pouvez choisir que votre entité s'intéresse à la première chose qui passe dans son champ de vision ou lui donner une liste de choses auxquelles réagir de sorte que votre agent puisse prendre la bonne décision en fonction de son environnement immédiat.

Cette configuration fonctionne parfaitement pour les jeux simples, mais lorsque votre jeu est plus complexe, comme un jeu d'infiltration ou un FPS tactique, vos agents devront être plus sélectifs en fonction de ce qu'ils « voient ». Si vous ne voulez pas que vos agents aient des yeux derrière la tête, vous pouvez réduire la liste des potentiels et supprimer tout ce qui passe à l'extérieur du champ de vision de l'entité. Vous pouvez accomplir rapidement cette tâche en faisant quelques calculs :

1. Calculez le vecteur entre l'agent et l'entité en question en soustrayant la position de la cible à la position de l'agent ;

2. Calculez l'angle entre ce vecteur et la direction dans laquelle votre agent regarde. (Si ce n'est pas déjà un vecteur, vous pouvez également calculer cette valeur.) ;

3. Si la valeur absolue de l'angle est supérieure au préréglage de l'angle de vue de l'agent, votre agent ne verra pas l'entité.

Dans des jeux plus complexes, vous devrez peut-être tenir compte du fait que le joueur ou que d'autres entités sont cachés par différents obstacles. Pour ce type de jeu, vous devrez effectuer un tracé de rayon (parfois appelé ray cast) pour voir si quelque chose bloque la cible potentielle. Un tracé de rayon est un moyen mathématique de vérifier si un rayon coupe quoi que ce soit, à partir d'un seul point et dans une direction déterminée. Le moteur du jeu propose une fonctionnalité de tracé de rayon, mais si vous voulez savoir comment faire, consultez l'article Deux cerveaux valent mieux qu'un.

La méthode précédente vous indique si quelque chose a occulté le centre de la cible, mais cela peut se révéler insuffisant pour dissuader votre agent. Il est possible que le centre de l'agent soit occulté, mais que sa tête dépasse au-dessus de l'obstacle. L'utilisation de plusieurs tracés de rayon à des points d'intérêt spécifiques sur la cible peut vous aider à déterminer non seulement si la cible peut être touchée, mais l'endroit où la cible peut être touchée.

I-B - L'ouïe

De  prime abord, on peut se dire qu'en matière d'IA l'ouïe est identique à la vue. Si vous pouvez voir une entité, vous pouvez certainement l'entendre. Effectivement, si votre agent a repéré une entité, l'agent peut activement détecter tout ce que fait cette entité jusqu'à ce qu'il ne soit plus dans son champ de vision. Cependant, ajouter un niveau supplémentaire en dotant vos agents de l'audition vous permet d'améliorer le fonctionnement de la vision. Suivre le bruit que font les entités en tant que niveau de perception est la clé de tout jeu basé sur la discrétion et l'infiltration.

Tout comme pour la vue, vous devez obtenir une liste des entités proches afin de réagir en fonction. Pour ce faire, vous pouvez vous contenter de configurer une distance précise, mais pour une meilleure audition de votre entité vous devez modifier cette distance en fonction des éléments de la liste.

Chaque action que peut effectuer l'entité doit avoir un niveau sonore propre. Vous pouvez préconfigurer les niveaux sonores (pour optimiser l'équilibre du jeu) ou les définir en fonction des niveaux sonores réels des effets sonores pendant l'action (agréable en termes de réalisme, mais inutile). Si le son est généré dépasse un certain seuil, votre agent percevra cette entité.

Si vous voulez tenir compte des obstacles, vous pouvez à nouveau limiter cette liste en effectuant des tracés de rayon dans votre environnement de jeu pour voir si quoi que ce soit pourrait arrêter le son. Étant donné que peu de matériaux arrêtent entièrement les sons, vous devez être plus créatif lorsque vous choisissez les entités de votre liste.

I-C - Les autres sens

Les fonctionnalités de base utilisées pour la vue et l'ouïe de vos agents suffisent pour simuler d'autres sens. Voici une liste des autres sens que vous pouvez ajouter aux entités d'un jeu si les graphismes le permettent :

- L'odorat : l'idée d'avoir des agents intelligents qui peuvent repérer et suivre les joueurs grâce à leur odeur a été ajoutée dans des jeux récents comme Call of Duty 4*. Ajouter le sens de l'odorat dans un jeu est relativement simple : donnez à chaque entité dans le jeu une certaine capacité olfactive. L'intensité de l'odeur détermine deux facteurs : le rayon dans lequel l'odeur est repérable et de la longueur de la piste laissée derrière l'entité. Les joueurs actifs laissent souvent des traces de leur passage derrière eux pour de multiples raisons (nous parlerons des pistes plus loin dans cet article). L'une de ces raisons peut être d'aider les entités à les repérer grâce à leur odeur. À mesure que le joueur avance, l'intensité de l'odeur laissée diminue, la piste refroidit. Lorsqu'un agent doit « sentir » la piste à nouveau, il doit vérifier les odeurs alentour comme il le ferait avec le son : inspecter son rayon. Avec l'odeur, le facteur de succès est donc basé sur la puissance de l'odorat de l'entité et de l'intensité de l'odeur à détecter sur la piste ;

- Le radar : certains jeux permettent aux joueurs de disposer d'un radar individuel, ce qui rend la détection encore plus facile. Il suffit de faire une simple vérification de rayon. L'IA peut alors vérifier les résultats. Pour les jeux en équipe, le radar lui-même peut devenir plus intéressant. Pour développer une IA dans un jeu en équipe, chaque équipe doit disposer d'une liste de radars affichant les entités trouvées par le radar. Chaque membre de l'équipe peut alors contrôler son rayon qui révélera la liste des entités repérées afin de coordonner l'action de l'équipe. L'équipe peut ajouter des éléments à la liste en utilisant un équipement radar (dans des jeux comme Enemy Territory : Quake Wars*) ainsi que chaque membre de l'équipe en ajoutant tout ce qui est « vu ». Ce comportement permet aux entités de fonctionner comme une seule entité, car chacun d'eux alerte les autres de ce qu'il voit ;

- Le toucher : e sens est une sorte de « contact » où le système de collision du moteur de jeu réagit automatiquement. Vous devez simplement vous assurer que vos agents intelligents réagissent aux dommages et événements de collision ;

- Le goût : je ne suis pas sûr de savoir comment ce sens pourrait être mis en œuvre dans un jeu. Ce serait sans doute un sens qui se rapprocherait des propriétés de l'odorat, mais exigerait que les agents soient actifs et « goûtent » ce qu'ils trouvent.

Être capable de ressentir le monde qui nous entoure est une bonne chose, mais qu'est-ce que les agents sont supposés ressentir ? Vous devez préciser et être en mesure d'identifier les choses qui peuvent être observées dans les paramètres de vos agents. Lorsque vous reconnaissez ce que vous voyez, vos agents peuvent réagir sur la base de règles qui régissent l'entité.

I-D - Entités temporaires

Les entités temporaires sont en réalité des effets visuels dans l'environnement de jeu. Elles sont semblables à des entités, elles ont une structure de classe globale qui définit une entité temporaire, mais elles se distinguent des entités, car elles ne « pensent » pas, ne réagissent pas, et n'interagissent pas avec les entités de l'environnement du jeu ou avec les joueurs. Leur seul but est d'agrémenter le jeu, en ajoutant des détails supplémentaires au jeu pendant un laps de temps déterminé et disparaissent ensuite. Les entités temporaires sont utilisées pour des éléments comme les trajectoires de projectiles, la fumée, les étincelles, les giclées de sang, et même les empreintes.

La nature des entités temporaires implique qu'elles sont simples à mettre en œuvre et n'ont pas vraiment besoin de détecter des obstacles ou de prendre en compte les collisions (au-delà des collisions simples). Le problème est que certaines entités temporaires donnent aux joueurs un indice visuel sur des événements passés (les impacts de balles, traces de brûlé indiquent une récente bataille, des empreintes de pas dans la neige peuvent conduire à une cible potentielle), alors pourquoi vos agents intelligents ne pourraient-ils pas utiliser ces indices à leur tour ?

Il existe deux façons de résoudre ce problème : vous pouvez améliorer votre système d'entité temporaire pour permettre le tracé de rayon (ce qui irait à l'encontre du principe d'entité temporaire), ou vous pouvez ajouter une entité vide à proximité de vos entités temporaires. Cette entité vierge ne pensera pas et n'aura pas d'existence graphique, mais vos agents seront capables de la détecter, et seront associés à l'entité temporaire pour fournir des renseignements à votre agent. Donc, lorsque vous ajoutez une traînée de sang sur le sol, vous pouvez également ajouter une entité invisible au même endroit qui informera vos agents de ce qui se passe. Pour les empreintes, c'est la piste qui compte.

I-E - La couverture

Dans de nombreux jeux de tir, il est préférable que vos agents soient assez intelligents pour se dissimuler derrière des obstacles lorsque cela est possible plutôt que de rester à découvert en situation de combat. Ce problème est un peu plus spécialisé que d'autres sujets abordés jusqu'ici. Alors, comment vos agents déterminent-ils s'il y a une zone où ils pourront se mettre à couvert ?

Figure 1 : Penny Arcade* ironise sur le problème des ennemis contrôlés par l'IA qui se mettent à couvert.

Ce dilemme réside dans deux problèmes : comment déterminer la zone où l'entité peut se mettre à couvert dans la géométrie de l'environnement du jeu, et la façon dont les entités prennent la décision de se mettre à couvert (comme la bande dessinée ci-dessus le suggère). Pour déterminer si une entité est capable de bloquer les attaques en se mettant à couvert, vous pouvez faire une vérification simple en prenant en compte la taille de la zone de couverture potentielle. Vous devez ensuite vérifier si votre entité peut se dissimuler derrière elle. Pour ce faire, créez un rayon qui évalue les positions de tir et la zone à couvert. Utilisez ce rayon pour déterminer si la zone est totalement à couvert (à partir de votre point de tir), et marquez cet espace comme prochaine cible pour votre agent.

Figure 2 : Ici, votre agent a déterminé que l'étoile verte est un endroit sûr pour se mettre à couvert.

II - Parcours de l'IA

Jusqu'à présent, j'ai beaucoup parlé de la façon dont l'IA prend des décisions et de la façon dont elle s'informe de ce qui se passe (afin de prendre de meilleures décisions). À présent, intéressons-nous à l'exécution des décisions prises par l'IA. La prochaine étape est de comprendre comment se rendre du point A au point B. En fonction de la nature du jeu et du niveau de performance exigé, vous pouvez utiliser plusieurs approches différentes.

II-A - Crash and Turn

Le crash and turn, est l'un des moyens les plus élémentaires de générer les mouvements d'une entité. Voici comment cela fonctionne :

1. Déplacez-vous en direction de votre cible ;

2. Si vous rencontrez un mur, tournez dans la direction qui vous rapprochera le plus rapidement de la cible. Si aucun choix n'est préférable à un autre, optez pour un choix aléatoire.

Cette approche fonctionne assez bien pour les jeux simples. D'innombrables jeux ont utilisé cette méthode pour déterminer la façon dont les monstres poursuivent le joueur. La méthode crash and turn amène souvent les entités à rester coincées derrière des murs ou dans des coins concaves en essayant de poursuivre le joueur, cette méthode est idéale pour les jeux avec des zombies.

Si le jeu nécessite un peu plus de finesse dans les mouvements de ses agents, vous pouvez élargir la méthode crash and turn et donner une capacité de mémoire à vos agents. Si les agents peuvent garder une trace de l'endroit où ils sont déjà passés, ils peuvent commencer à prendre des décisions plus pertinentes sur le chemin à suivre. Lorsque toutes les possibilités directionnelles ont été essayées, vos agents peuvent revenir en arrière et faire des choix différents. Ainsi, votre agent fera une recherche systématique du chemin vers une cible. Voici comment cela fonctionne :

1. Déplacement vers la cible ;

2. Choix parmi ceux disponibles ;

3. Lorsque l'entité arrive dans une impasse, elle reviendra en arrière, au niveau du dernier choix et en fera un autre ;

4. Si tous les chemins possibles sont explorés, l'entité abandonnera.

Cette méthode a l'avantage d'être facile à mettre en œuvre, vous pouvez donc avoir un grand nombre d'entités sans ralentir le jeu. Cette méthode est également optimale pour le multithreading. L'inconvénient de cette méthode c'est un immense gaspillage d'espace, chaque agent pouvant potentiellement couvrir toute la carte.

Heureusement, vous pouvez éviter cela en permettant à vos agents de se souvenir des chemins déjà empruntés dans une mémoire partagée. Un problème de conflits de parcours peut alors se poser, vous devez donc conserver les chemins de vos entités dans un module distinct que tous les agents peuvent ensuite consulter au fur et à mesure qu'ils se déplacent et envoyer des mises à jour lorsqu'ils découvrent de nouvelles voies. Le module de la carte de parcours (Path Map Module) peut ensuite analyser les résultats pour éviter les conflits.

II-B - Trouver son chemin

Les parcours générés par la méthode crash and turn sont parfaits pour s'adapter à des cartes évolutives. Dans les jeux de stratégie, les joueurs ne peuvent pas attendre que leurs unités trouvent leurs repères. De plus, ces cartes peuvent être gigantesques, et l'orientation se fait comme dans un goulot d'étranglement.

Trouver son chemin est essentiellement un problème de développement du jeu. Dans des jeux du même âge que le premier Starcraft* (Blizzard Entertainment*), un grand nombre d'entités étaient toutes capables de trouver leur chemin dans de vastes cartes complexes.

L'algorithme de base de parcours était « A* » (prononcez Eh-Star), qui pouvait être utilisé pour découvrir un chemin optimal entre deux points sur un graphe (dans ce cas, la carte). Une simple recherche sur Internet permet de découvrir un algorithme propre qui utilise des termes descriptifs comme F, G et H. Je vais vous l'expliquer plus clairement.

D'abord, vous devez établir deux listes : une liste de nœuds qui n'ont pas été vérifiés (Unchecked) et une liste de nœuds qui ont été vérifiés (Checked). Chaque liste est composée d'un nœud de position, de la distance estimée de l'objectif, et d'une référence à son parent (le nœud précédent dans la liste). Au départ, les listes sont vides.

Vous ajoutez ensuite votre position de départ à la liste non vérifiée et le parent. Puis, entrez l'algorithme :

- sélectionnez le meilleur nœud de la liste ;

- si ce nœud est l'objectif, vous avez terminé ;

- si ce nœud n'est pas l'objectif, ajoutez-le à la liste des vérifiés ;

- pour chaque nœud adjacent à ce nœud :

- si le nœud n'est pas praticable, ignorez-le,

- si le nœud est déjà dans une liste (cochée ou décochée), ignorez-le,

- ajoutez tous les autres à la liste non vérifiée, en définissant ces nœuds comme parents et en réestimant la distance à l'objectif (une vérification de la distance brute suffit).

Lorsque l'entité atteint l'objectif, le chemin peut être établi en traçant l'itinéraire des parents vers le nœud qui n'a pas de parent (le nœud de départ). Vous aurez alors le chemin optimal que l'entité pourra alors suivre. Ce processus devant uniquement se faire lorsqu'un agent a reçu un ordre ou a décidé de se déplacer de sa propre initiative, il peut vraiment profiter au multithreading. Un agent peut envoyer une demande de parcours pour retrouver un chemin déjà trouvé sans affecter les performances de l'IA. Le système peut rapidement obtenir des résultats ; mais dans le cas d'un grand nombre de demandes de parcours, l'agent peut soit attendre ou tout simplement commencer à se diriger dans la bonne direction (il peut notamment utiliser la méthode crash and turn). Sur de très grandes cartes, le système peut être décomposé en régions, et des chemins possibles entre les régions (ou points de passage) peuvent être précalculés. Dans ce cas, pour trouver le bon parcours, il vous suffira d'afficher le meilleur chemin et de transmettre immédiatement les résultats. Le module de suivi de parcours peut simplement observer les changements sur la carte - comme un joueur qui construit un mur - et relancer ensuite les vérifications de parcours si nécessaire. L'algorithme peut donc s'adapter sans affecter les performances du reste du jeu.

Dans le sous-système, pour trouver les parcours, le multithreading peut également améliorer les performances du système. Parfait pour un jeu de stratégie en temps réel (RTS) ou dans un système avec un grand nombre d'entités où chacun cherche un chemin potentiellement unique. Plusieurs parcours peuvent être trouvés simultanément par différentes entités. Bien sûr, le système devra garder une trace des chemins découverts. Le même parcours n'a pas besoin d'être découvert plusieurs fois.

III - Exemple de code

Voici un exemple de code A* mis en œuvre simplement en C. Je suis parti des fonctions de soutien dans l'exemple, pour des raisons de simplicité, et parce qu'ils doivent être adaptés pour différents styles d'implémentation. L'échantillon est basé sur une grille simple où chaque case permet soit un déplacement soit ne le permet pas. L'exemple permet uniquement un mouvement dans une case adjacente, mais des modifications mineures permettent de faire des mouvements en diagonale ou d'avoir un jeu de style hexagonal.

c

1

1

/*Get Path will return -1 on failure or a number on distance to path
if a path is found, the array pointed to by path will be set with the path in Points*/
int GetPath(int sx,int sy,int gx,int gy,int team,Point *path,int pathlen)
{
int u,i,p;
memset(&Checked,0,sizeof(Checked));
memset(&Unchecked,0,sizeof(Unchecked));
Unchecked[0].s.x = sx;
Unchecked[0].s.y = sy;
Unchecked[0].d = abs(sx - gx) + abs(sy - gy);
Unchecked[0].p.x = -1;
Unchecked[0].p.y = -1;
Unchecked[0].used = 1;
Unchecked[0].steps = 0;

La section ci-dessus gère l'initialisation de la liste vérifiée et non vérifiée et met le nœud de départ dans la liste non vérifiée. Avec cette configuration, le reste de l'algorithme peut être exécuté en boucle.

c

1

1

do
{
u = GetBestUnchecked();
/*add */
AddtoList(Checked,Unchecked[u]);
if((Unchecked[u].s.x == gx)&&(Unchecked[u].s.y == gy))
{
break;
}

La section ci-dessus s'intéresse au nœud de la liste non vérifiée le plus proche de l'objectif. GetBestUnchecked() est une fonction qui vérifie l'estimation de la distance de chaque nœud à l'objectif. Si la case est l'objectif, la boucle s'arrête et le processus est terminé.

La méthode de calcul de la distance est affichée ci-dessous en prenant la distance estimée à l'objectif dans les directions X et Y et les additionne. Vous pourriez être tenté d'utiliser le théorème de Pythagore (a^2 + b^ 2 = c^2), mais c'est complètement inutile. Vous avez uniquement besoin d'une distance relative, pas d'une distance exacte. Les processeurs peuvent facilement gérer les additions et les soustractions alors qu'ils ont plus de mal à faire plusieurs opérations de multiplication, et sont encore plus lents pour les divisions. Cette section de code étant exécutée de nombreuses fois, l'optimisation est la clé.

c

1

1

/*tile to the left*/
if((Unchecked[u].s.x - 1) >= 0)/*first, make sure we're on the map*/
{
if((IsInList(Unchecked,Unchecked[u].s.x - 1,Unchecked[u].s.y,NULL) == 0)&&(IsInList(Checked,Unchecked[u].s.x - 1,Unchecked[u].s.y,NULL) == 0))
/*make sure we don't repeat a search*/
{
if(TileValid(Unchecked[u].s.x - 1,Unchecked[u].s.y,team))
NewtoList(Unchecked,Unchecked[u].s.x - 1,Unchecked[u].s.y, Unchecked[u].s.x, Unchecked[u].s.y, abs((Unchecked[u].s.x - 1) - gx) + abs(Unchecked[u].s.y - gy), Unchecked[u].steps + 1);
}
}

Dans la section ci-dessus, la fonction porte sur la case à gauche du nœud actuel. Si le nœud n'est pas déjà dans la liste vérifiée ou non vérifiée, cette fonction tentera de l'ajouter à la liste. TileValid() est une autre fonction qui doit être adaptée à votre jeu. Si elle passe la vérification TileValid(), la fonction NewToList() ajoutera une nouvelle case à la liste non vérifiée. Les trois sections suivantes portent sur le même processus, mais couvrent les autres directions : droite, haut et bas.

c

1

1

/*tile to the right*/
if((Unchecked[u].s.x + 1) < WIDTH)/*first, make sure we're on the map*/
{
if((IsInList(Unchecked,Unchecked[u].s.x + 1,Unchecked[u].s.y,NULL) == 0)&&(IsInList(Checked,Unchecked[u].s.x + 1,Unchecked[u].s.y,NULL) == 0))
/*make sure we don't repeat a search*/
{
if(TileValid(Unchecked[u].s.x + 1,Unchecked[u].s.y,team))
NewtoList(Unchecked,Unchecked[u].s.x + 1,Unchecked[u].s.y, Unchecked[u].s.x, Unchecked[u].s.y, abs((Unchecked[u].s.x + 1) - gx) + abs(Unchecked[u].s.y - gy), Unchecked[u].steps + 1);
}
}
/*tile below*/
if((Unchecked[u].s.y + 1) < HEIGHT)/*first, make sure we're on the map*/
{
if((IsInList(Unchecked,Unchecked[u].s.x ,Unchecked[u].s.y + 1,NULL) == 0)&&(IsInList(Checked,Unchecked[u].s.x,Unchecked[u].s.y + 1,NULL) == 0))
/*make sure we don't repeat a search*/
{
if(TileValid(Unchecked[u].s.x,Unchecked[u].s.y + 1,team))
NewtoList(Unchecked,Unchecked[u].s.x,Unchecked[u].s.y + 1, Unchecked[u].s.x, Unchecked[u].s.y, abs(Unchecked[u].s.x - gx) + abs((Unchecked[u].s.y + 1) - gy), Unchecked[u].steps + 1);
}
}
/*tile above*/
if((Unchecked[u].s.y - 1) >= 0)/*first, make sure we're on the map*/
{
if((IsInList(Unchecked,Unchecked[u].s.x ,Unchecked[u].s.y - 1,NULL) == 0)&&(IsInList(Checked,Unchecked[u].s.x,Unchecked[u].s.y - 1,NULL) == 0))
/*make sure we don't repeat a search*/
{
if(TileValid(Unchecked[u].s.x,Unchecked[u].s.y - 1,team))
NewtoList(Unchecked,Unchecked[u].s.x,Unchecked[u].s.y - 1, Unchecked[u].s.x, Unchecked[u].s.y, abs(Unchecked[u].s.x - gx) + abs((Unchecked[u].s.y - 1) - gy), Unchecked[u].steps + 1);
}
}
memset(&Unchecked[u],0,sizeof(PNode));

La dernière chose à faire dans cette itération est de supprimer le nœud actuel de la liste non vérifiée. Pas besoin de vérifier à nouveau cette case.

c

1

1

}
while(1);

Ce dernier élément de code génère le parcours en fonction de la liste vérifiée par retour de suivi de l'objectif. Le retour au point de départ peut toujours être déterminé, parce que chaque nœud du parcours garde trace du nœud précédent. Le parcours final est ensuite renvoyé (par référence). La fonction renvoie la longueur du nouveau parcours.

c

1

1

IsInList(Checked,Unchecked[u].s.x,Unchecked[u].s.y,&u);
p = Checked[u].steps;
if(path != NULL)
{
for(i = (p - 1);i >= 0;i--)
{
path[i].x = Checked[u].s.x;
path[i].y = Checked[u].s.y;
IsInList(Checked,Checked[u].p.x,Checked[u].p.y,&u);
}
}
return p;
}

IV - Résumé

Les agents intelligents doivent observer le monde qui les entoure. Les contrôles simples des limites et les tracés de rayon peuvent être utilisés pour créer rapidement ces observations autour de l'idée de sens de perception - la vue et l'ouïe - qui permettent à vos agents de prendre des décisions plus réalistes au fur et à mesure du déroulement du jeu. Les agents ayant des objectifs précis à accomplir, ils devront trouver les moyens d'arriver là où ils veulent aller. Des méthodes rapides comme le « crash and turn » sont utiles à court terme dans les cartes simples, alors que pour des jeux plus complexes, vous devrez utiliser des méthodes d'analyse des cartes pour trouver la trajectoire optimale. Vous pouvez optimiser ces méthodes pour améliorer les implémentations multithread pour assurer la fluidité du jeu même lorsqu'un grand nombre d'entités évoluent sur des cartes complexes.

V - À 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 « Architecture, programmation et conception de niveaux dans les jeux vidéo », ainsi que d'autres cours sur « l'Intégration des graphismes 3D » dans les jeux. Il passe actuellement 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.

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.

VI - Ressources

- Unity Resource Center

- Intel GameDev Tools

- Intel GPA

- Intel INDE