But du projet.
Le projet Rational Autonomous Cybernetic Commandos (RACC) vise à implémenter une Intelligence Artificielle totalement rationelle dans des personnages cybernétiques non joueur (NPCs ou "bots") autonomes dont les principales caractéristiques sont l'analyse environnementale en temps réel et l'intelligence d'équipe de commandos.
Des compétences non cognitives de l'IA.
Le côté instinctif d'une intelligence constitue la somme des sens, moyens et actions dont l'être est capable sans que ceux-ci découlent de la raison. L'Instinct représente la dimension mécanique automatique des capacités de l'individu. Il s'agit pour les systèmes biologiques d'un phénomène nerveux dont le comportement obéit à des règles établies au niveau génétique. Il s'agira pour les systèmes cybernétiques d'un programme non modifiable dont le comportement obéira à des règles établies par le programmeur de manière à simuler le comportement instinctif connu des systèmes biologiques, en l'occurence l'Homme.
Le programme est le génome de l'Intelligence artificielle.
Le génome est le programme de l'intelligence humaine.
Tous deux sont des machines de Turing.
Le robot est donc un être vivant anthropomorphe (ou, relativement à son Univers, "joueur-o-morphe"). Les compétences non cognitives de cette IA se déclinent en trois domaines : la sensitivité, l'action et la navigation.
Sensitivité et sensibilité de l'individu cybernétique.
Le monde virtuel des jeux vidéo de combat subjectif fournit trois vecteurs de sensations, respectivement par ordre d'importance vitale la vue, l'ouïe et le toucher. Ceux-ci doivent être implémentés de manière aussi réaliste que possible dans le programme instinctif de l'IA. De leur qualité dépendent les capacités d'adaptation et d'apprentissage, c'est-à-dire la capacité de survie, de l'individu cybernétique.
La vision est implémentée par considération spatiale. La mise en parallèle avec le système de fonctionnement de l'oeil humain révèle un principe de fonctionnement identique, le ray caster, ou traceur de rayons, chargé pour chaque angle du champ de vision considéré de quantifier la distance entre l'individu et son plus proche obstacle dans cette direction. L'être cybernétique acquiert ainsi des facultés de considération spatiale de son Univers comparables à celles que l'être humain a du sien. La quantification temporelle de la vision humaine permettant 15 captures discernables par seconde, le bot ne doit pas être censé échantillonner son champ de vision plus de 15 fois par seconde.
Ce traceur de rayons émet successivement des rafales de TraceLines (lignes de test. Cf. documentation technique des moteurs 3D d'ID Software) à partir de la position du personnage selon un angle incrémenté à chaque itération. Les distances ainsi obtenues renseignent un tableau dont l'indice médian correspond à la direction à laquelle le bot fait face.
La liste des entités est fournie par le moteur à la demande, sous forme d'une liste chaînée. Pour chacune un test est fait sur leur position respective afin de déterminer si l'entité en question est potentiellement visible, auquel cas une TraceLine supplémentaire est envoyée pour tester la LOS (Line Of Sight, ligne de visibilité). Si le résultat est positif, l'entité est conservée dans le jeu des entités visibles et replacée dans son contexte, comme ici le joueur en arrière-plan. Une requête est alors effectuée, soit directement par le pointeur de cette entité, soit par l'appel d'une fonction spécialisée du moteur, pour acquérir ses paramètres visuels (luminosité, taille, modèle, etc).
Ce tout constitue une modélisation logique de l'oeil humain.
Vision comparée : modèle humain |
Vision comparée : modèle IA |
L'ouïe est implémentée par considération temporelle et spatiale. Idéalement, il s'agit de calculer logiciellement, pour chaque instant t du temps virtuel, l'intensité sonore potentiellement entendue par le personnage cybernétique en sommant la valeur des échantillons sonores en cours de lecture à cet instant t. L'onde sonore ainsi obtenue représente le bruit ambiant, dont il est alors possible d'identifier les énénements sonores dérangeants ou surprenants par simple dérivation de cette courbe. La technologie du moteur de jeu ne permet pas d'acquérir à chaque instant cette intensité sonore, mais se borne à signaler, aux instants opportuns, le départ de lecture d'un échantillon sonore.
Le modèle humain ne sera donc qu'imparfaitement reproduit. La solution retenue consiste à calculer au préalable, la durée et le bruit moyen de chaque échantillon, et à faire varier en temps réel, le seuil auditif en conséquence. Nous obtenons alors une courbe temporelle dont les valeurs élevées signalent une intensité sonore importante, où le système auditif est censé plafonner (ignorer les sons supplémentaires qui se confondent alors avec le bruit ambiant), et dont les pics de dérivation signalent la surprise, dont l'effet sera un sursaut et un retournement dans cette direction, d'intensité proportionnelle au coefficient de surprise lui-même.
Il s'agit d'une modélisation logique de l'oreille humaine.
Audition comparée : modèle humain |
Audition comparée : modèle IA |
Le toucher est, dans ce type de monde virtuel, une sensation acquise par procuration. L'interface machine-homme étant composée uniquement d'un écran et de haut-parleurs, la sensation de toucher ne peut être transmise que par ces deux vecteurs.
Le moteur du jeu simule, afin que le joueur le considère ainsi, le toucher de manière tout d'abord auditive : bruits de pas, bruits de chute, bruits de coups. Ces échantillons sonores sont ainsi référencés et font l'objet d'un traitement spécial dans la partie auditive de l'IA. Les résultats de ce traitement se doivent d'être amplifiés si la sensation de toucher est également ressentie au moyen d'un vecteur visuel : saut d'écran (flinch), blessure (damage), sang. Auquel cas il est opportun d'ajuster un facteur de panique en conséquence, dont la variation d'intensité est fonction directe de l'intensité du flinch et du damage combinés, et dont la variation temporelle est fonction de la durée du flinch. Atteignant un certain seuil, le facteur de panique (qui peut être confondu avec la confiance en soi) déclenche une réaction de survie (la fuite), en prenant possession, jusqu'à rétablissement d'un cycle de pensée cognitive normal, du contrôle de la dernière compétence non-cognitive de l'IA : la navigation.
Des moyens d'action de l'individu cybernétique.
L'interface homme-machine classique entre l'humain et son avatar contrôlé dans le monde virtuel (le joueur), se constitue habituellement d'une souris et d'un clavier.
On peut modéliser le déplacement de la souris sous l'action d'une main humaine d'un point à l'écran de coordonnées (x(0), y(0)) vers un point de coordonnées (x(+¥), y(+¥)) en fonction du temps t mesuré en trames d'affichage (t Î N), par le système de fonctions logarithmiques suivant (remerciements : Tobias "Killaruna" Heimann, Johannes "@$3.1415rin" Lampel) :
dy/dt = a·(dy/d(t-1) × e(a·log (s / 2)) + s·(y(+¥)-y(t)) × (1 - e(a·log (s / 2)))) dx/dt = a·(dx/d(t-1) × e(a·log (s / 2)) + s·(x(+¥)-x(t)) × (1 - e(a·log (s / 2)))) où a équivaut à 20 fois la durée en millisecondes de la trame. où s correspond à la vitesse de réaction de l'individu (constante empirique entre 0 et 1). |
La vitesse de réaction de l'individu varie suivant le degré d'expérience et de confiance en soi.
Il est en outre nécessaire d'introduire un bruit inhérent à la coordination des axes x et y :
dx/dt + c·(dy/dt)·((dx/dt)/|dx/dt|) dy/dt + c·(dx/dt)·((dy/dt)/|dy/dt|) où c équivaut au coefficient d'habileté inféré à l'individu cybernétique. |
L'orientation de l'individu cybernétique sera donc décrite en utilisant deux axes vectoriels et un couple d'entiers : l'axe courant, l'axe idéal, et la vitesse de déplacement du curseur.
De même, on peut modéliser l'action sur les touches du clavier en considérant les deux paramètres qui suffisent à décrire un événement minimal de ce type : la date d'appui sur la touche et sa date de relâchement. Un test est fait à chaque trame afin de savoir si, parmi les canaux d'entrée clavier autorisés, l'un d'eux doit être activé ou suspendu. L'interface homme-machine clavier/souris ainsi implémentée permet à l'IA de disposer de facilités d'action comparables à celles dont dispose le joueur humain pour contrôler son avatar informatique.
Navigation tactique non waypointée.
Se mouvoir est pour tout système biologique possédant cette faculté un besoin instinctif vital. Il en sera de même pour l'individu cybernétique.
La compétence navigationnelle se décline idéalement en deux pôles, respectivement instinctif et cognitif. Dans le premier cité s'exprime le besoin d'exploration de l'environnement ; dans le second s'expriment les moyens conscients influençant sa performance : la prudence, la tactique ; l'appellation "tactique" regroupant, par opposition à "stratégique", la somme des moyens consciemment considérés comme les meilleurs, mis en oeuvre dans l'achèvement d'un but dont la validité temporelle ne dépasse pas un futur proche de quelques secondes.
Ce modèle a du être simplifié pour des raisons d'ordre technique, car il nécessite une puissance de calcul trop grande que le matériel puisse fournir. Il a donc été inféré à l'individu cybernétique la capacité instinctive du mouvement tactique, traditionnellement située sur le plan cognitif chez l'être humain.
Tout être humain de condition psychologique normale dans un environnement sans danger a priori, a en l'absence de tout centre d'intérêt cognitif, une tendance naturelle à orienter son regard en direction de la plus longue distance couvrable par son champ de vision. Il s'agit d'un postulat dont je suis auteur et seul responsable, mais que je crois suffisament pertinent pour être accepté comme axiome de base. La pré-version RACC a d'ailleurs prouvé qu'une navigation non waypointée basée uniquement sur cet axiome et sur lui seul, suffisait amplement à la navigation dans des mondes virtuels de géométrie relativement simple. En fonction de quoi, le point focal lors du déplacement du personnage cybernétique s'adapte conséquemment aux variations de son champ de vision.
Une attention particulière doit néanmoins être apportée aux intersections latérales, en tant qu'elles sont potentiellement représentatrices d'une distance couvrable supérieure à celle focalisée à cet instant. Le personnage peut, à l'aide de quelques TraceLines, anticiper le passage découvert et orienter temporairement son point focal dans la direction de l'intersection, la durée du processus étant de l'ordre de la seconde.
Navigation : orientation du point focal |
Navigation : anticipation latérale |
L'utilisation rationnelle des données collectées par l'oeil du personnage cybernétique permet l'implémentation d'une approche tactique du déplacement. Dans un environnement a priori dangereux, la navigation tactique consiste à se mouvoir de couverture en couverture en évitant autant que faire se peut l'exposition directe à la source présumée du danger.
- Tout pic du graphe représentant le champ de vision, représente un angle d'obstacles convexe. Si une TraceLine envoyée de l'emplacement correspondant vers la source de la menace retourne un résultat négatif, ce point représente également une zone de couverture.
- Tout pic dans la dérivée du graphe représentant le champ de vision, représente un angle concave. Tout indice de ce type représente une source de danger potentielle, en tant qu'il signale une intersection latérale. Ces angles devront faire l'objet d'une surveillance particulière.
L'étude des réactions de mouvement instinctives d'un individu engagé dans un combat urbain montre en outre que, dans l'intervalle de temps où la menace n'a pas encore explicitement manifesté sa source, celle-ci doit être assimilée à tout angle concave (i.e. intersection latérale) à proximité, tant que l'angle formé par les vecteurs positionnés en direction de l'objectif d'une part et en direction de l'intersection suspecte d'autre part, n'excède pas 90° en valeur absolue, ceci afin de garantir que le personnage cybernétique ne tournera jamais le dos à son objectif.
Navigation tactique en action |
Graphe FOV correspondant |
La détermination d'itinéraire (pathfinding), nécessite toujours la division symbolique de l'univers virtuel, soit en points de passage (waypoints), soit en zones d'espace parcourables (navmesh). Contrairement à l'orientation traditionnellement choisie lors de la programmation d'une entité mouvante, la deuxième solution doit être retenue car elle fournit précisément la dimension spatiale de la zone parcourable, chose que les points de passage ne permettent pas, ou de manière très imprécise.
La liste des espaces parcourables est obtenue par interprétation du fichier BSP où sont décrits spatialement la totalité des polygones qui composent la carte (map) du monde virtuel. Le format BSP (Binary Space Partition) stocke une arborescence décrivant les divisions successives à effectuer sur un seul volume afin de reproduire toute la géométrie de l'univers en polygones non concaves. L'interprétation en est faite en utilisant les travaux de botman et notamment ses excellents BSP Tools. Il est à noter que cette opération n'est réalisée qu'une fois par carte, ceci afin de constituer le fichier de données correspondant.
Chaque polygone horizontal ou soumis à une pente n'excédant pas la valeur maximale franchissable (45°), est listé comme potentiellement parcourable. Leur joignabilité sera construite en temps réel par expérience et monitoring. Chaque individu cybernétique acquiert ainsi le souvenir de ses propres déplacements, ainsi que de ceux des autres individus qu'il voit. Un bitmask correctement renseigné permet de différencier chaque type de joignabilité entre l'un ou l'autre des polygones parcourables (échelle, saut, liquide, nécessite un déplacement accroupi, etc.)
Le système de connexions décrit ci-dessus constitue le navmesh (carte pseudo-cognitive) de l'IA, lequel peut être parcouru par un algorithme de type A*, afin de déterminer un itinéraire selon un choix stratégique dépendant de la situation (le plus court, le plus sûr, etc.)
NOTE : Il est absolument hors de question de stocker le danger, la fréquentation, ou n'importe quelle sorte d'information non strictement objective dans la structure de ces espaces parcourables. Le stockage de ces informations subjectives est fait dans la mémoire cognitive de l'individu, laquelle doit de ce fait être questionnée lors de la détermination d'itinéraire.
Détermination d'itinéraire : A*
Des compétences cognitives de l'IA.
[ cette partie est en cours de rédaction ]
Si vous êtes intéressés par des explications plus détaillées sur le code source, davantage d'informations techniques sont disponibles dans le readme.txt original de botman, fourni avec sa maquette HPB. Il s'agit d'un tutoriel complet pour l'étude du HPB_bot.
botman est également l'auteur d'un tutoriel C++ qui explique très bien la base des classes et héritages en C++. Même si la connaissance du C est suffisante pour travailler le code, les programmeurs doivent se souvenir que l'interface avec le moteur Half-Life est écrite en C++.
Le code source des Rational Autonomous Cybernetic Commandos est libre pour chacun à voir et utiliser. Une forte emphase a été placée sur l'exactitude, la tenue, la lisibilité et le commentaire.
Use the source, Luke!
Avtomat Kalashnikov AK-47