Le moteur derrière le comportement : GoldSrc et l'architecture AI

Le système d'intelligence artificielle de Half-Life’s est construit sur le moteur GoldSrc, un moteur Quake fortement modifié que Valve Software a développé à la fin des années 1990. L'architecture AI de GoldSrc a été révolutionnaire pour son temps parce qu'elle a dépassé les simples motifs de poursuite et d'attaque dans un système qui pourrait évaluer son environnement, choisir entre plusieurs comportements, et naviguer des espaces tridimensionnels complexes avec une fiabilité surprenante. Le noyau de ce système est le “AI” classe entité, qui est un objet C++ qui met en œuvre une machine à état fini (FSM) combinée avec un sous-système de recherche de trajectoire.

Les points de repère ne suffisent pas : Navigation Mesh Fondements

Le jeu moderne AI repose fortement sur les mailles de navigation (mesh nav) comme représentation principale de l'espace marchable. Cependant, Half-Life prédate l'adoption généralisée de mailles nav dans les moteurs de jeu en temps réel. Au lieu de cela, le moteur GoldSrc utilise un système de navigation basé sur des nœuds qui est conceptuellement similaire à un graphique. Les concepteurs de niveaux placent manuellement waypoints (appelé “path corners” dans l'éditeur Hammer) dans tout l'environnement. Ces points de repère sont reliés par des bords dirigés qui définissent les chemins possibles qu'un personnage d'IA peut prendre. Le système est à la fois élégant et limité : il donne aux concepteurs un contrôle direct sur le mouvement d'IA, mais il nécessite un travail manuel méticuleux pour s'assurer que chaque secteur que l'IA peut avoir besoin d'atteindre est correctement connecté.

Chaque point de cheminement stocke la position, quelles connexions de chemin sont valides, et les drapeaux qui indiquent des conditions particulières telles que des segments de saut requis par le crouch, ou d'escalade. Lorsqu'un caractère AI doit se déplacer d'un point à l'autre, il ne calcule pas un chemin à travers la géométrie arbitraire. Il recherche plutôt le graphique de point de cheminement en utilisant un algorithme de recherche de chemin pour trouver la séquence la plus courte de nœuds connectés. Les surfaces marchables elles-mêmes sont définies par la géométrie de brossage de la carte, mais l'IA ne parvient jamais à traverser directement ces surfaces; il traverse toujours le réseau de nœuds. Cette approche réduit considérablement l'espace de recherche par rapport aux méthodes de mailles basées sur la grille ou nav, ce qui est crucial compte tenu des ressources limitées du CPU disponibles en matériel de l'ère 1998.

Pourquoi les réseaux de nœuds fonctionnent pour GoldSrc

Le système basé sur les nœuds fonctionne bien pour Half-Life parce que les niveaux de jeu sont relativement linéaires des environnements de style corridor avec géométrie prévisible. Le Black Mesa Research Facility, le cadre primaire du jeu et du 8217; est composé de couloirs, de chambres et d'espaces industriels qui se déplacent naturellement par des points de chokepoints. Un réseau bien placé de trente à cinquante points peut couvrir une grande pièce et ses sorties, permettant à l'IA de naviguer efficacement sans avoir besoin d'une grille dense. Le système supporte également la recherche de chemin hiérarchique à un niveau de base : les concepteurs peuvent regrouper des points de points dans “areas” et utiliser des connexions de surface à zone pour accélérer la recherche de chemin à longue distance sur plusieurs sections de cartes.

L'algorithme A* dans la demi-vie et le système d'IA no 8217;

La demi-vie utilise l'algorithme de recherche A* (A-star) comme cheval de route. A* est un algorithme de recherche de la meilleure première fois qui trouve le chemin le plus court d'un nœud de départ à un nœud de but en évaluant la somme de deux fonctions : g(n), le coût du chemin du début au noeud n, et h(n)[, une estimation heuristique du coût du nœud n au but. L'algorithme maintient une file d'attente prioritaire de nœuds à explorer, en élargissant toujours le noeud avec la valeur f(n) = g(n) + h(n) la plus basse.

Heurerie et fonctions de coût

Le choix de l'heuristique est critique pour les performances A*. La demi-vie utilise l'heuristique standard de distance euclidienne, qui est admissible (ne surestime jamais le coût réel) et cohérent, assurant que l'algorithme retourne le chemin le plus court. Cependant, le moteur ajoute quelques optimisations pour tenir compte de la structure du réseau de nœuds. Par exemple, lors du calcul de l'heuristique, le système considère la composante verticale du mouvement plus fortement que la composante horizontale parce que monter des escaliers ou des rampes de navigation impose un coût de mouvement plus élevé sur les caractères AI. Cette pénalité verticale empêche l'algorithme A* de choisir des chemins qui nécessitent une escalade excessive même si la distance horizontale est plus courte.

Smoothing et Waypoint suivant

Une fois A* produit une liste de points de repère, le caractère AI doit suivre ce chemin de manière naturelle. Half-Life implémente un lissage [ étape qui supprime les points de repère inutiles du chemin calculé. Si le caractère peut voir le point de cheminement suivant directement sans obstacle intermédiaire, les points intermédiaires sont cullés. Cela réduit le comportement de zigzag qui peut survenir lorsque vous suivez un réseau de nœuds naïvement. Après lissage, le caractère AI utilise un comportement de direction pour se diriger vers le point de cheminement suivant, appliquant l'accélération et la décélération en fonction de la distance jusqu'à la cible et les capacités de vitesse du caractère. Le système comprend également un mécanisme “look-ahead” le caractère AI ne se déplace pas simplement vers le point de cheminement suivant immédiat, mais vers un point légèrement en avant le long du chemin.

Manipulation des environnements dynamiques

L'un des aspects les plus impressionnants de Half-Life’s AI est sa capacité à gérer les changements dynamiques dans l'environnement. Les séquences scriptées, les portes d'ouverture, les ennemis étant détruits, et même les événements physiques déclenchés par les joueurs peuvent modifier l'espace marchable en temps réel.

Évitement dynamique des obstacles

Lorsqu'un personnage d'IA rencontre un obstacle inattendu qui n'est pas représenté dans le réseau de nœuds et n°8212; tel qu'une pile de débris, une porte de fermeture ou même un autre caractère et n°8212; il utilise un mécanisme local d'évitement des obstacles qui fonctionne indépendamment du chemineur global. Ce système utilise une approche simple raycasting[: le caractère jette des rayons dans sa direction vers l'avant et de chaque côté. Si un rayon détecte un obstacle à une certaine distance, le personnage s'éloigne de lui. Cette évitement local est purement réactif et ne met pas à jour le réseau de nœuds. Si l'évitement local ne trouve pas de chemin clair après quelques secondes, le caractère d'IA revient à un comportement repath: il déclenche une nouvelle recherche A* de sa position actuelle à l'objectif original, mais avec une fonction de coût modifiée qui pénalise les nœuds près de l'obstacle détecté. Cette approche hybride—planification de chemin mondial avec l'évitation locale

Changements environnementaux et réactivité

Les portes et les plates-formes présentent un défi particulier. Lorsqu'une porte se ferme, elle crée une barrière infranchissable que le réseau de nœuds pourrait ne pas rendre compte. La demi-vie s'en charge en joignant un drapeau “bloqué” aux bords de la porte qui passent par les portes. Lorsqu'une porte se ferme, elle place ce drapeau sur les bords touchés, les retirant efficacement du graphique pour la recherche de la trajectoire. Le caractère AI reçoit une notification d'événement lorsque la porte se ferme, ce qui déclenche un rechemin immédiat. De même, les plates-formes mobiles changent la position des points de repère qui leur sont attachés. Le moteur met à jour les positions de ces points de repère chaque cadre, et le pathfinder les traite comme des nœuds dynamiques.

Machines d'État et prise de décision

Le caractère AI doit décider quand se déplacer, où se déplacer, et commentprioriser plusieurs buts. La demi-vie met en œuvre une machine d'état finie (FSM) comme couche de décision de haut niveau pour chaque entité AI. Le FSM définit un ensemble d'états tels que Idle, Alert, Combat, Flee, Patrol. Chaque état a sa propre logique de comportement, y compris la façon dont la recherche de chemin est invoquée et quels objectifs sont sélectionnés.

La machine d'État AI en GoldSrc

Dans l'état Idle, le caractère AI se tient toujours, balayant périodiquement l'environnement pour les ennemis ou les stimuli. Lorsque le joueur est détecté (par la vue, le son ou les dommages), le caractère transitionne vers l'état Alert. Dans Alert, le personnage commence à rechercher la dernière position connue de l'ennemi. Si l'ennemi n'est pas trouvé après un court laps de temps, le personnage entre dans un état de recherche et utilise un comportement de recherche aléatoire de chemin: l'algorithme A* est utilisé pour trouver un chemin vers l'ennemi’s dernier emplacement connu, mais le personnage ne se déplace pas directement là. Au contraire, il se déplace vers un point de cheminement voisin qui fournit un bon point de vue, simulant le comportement d'un garde-patrouille qui cherche un intrus. Si le personnage réacquiert un contact visuel avec l'ennemi, il passe à l'état Combat, qui utilise un comportement de recherche différent qui privilégie les mouvements de flanc et prend la couverture.

Transitions et priorités

Le système de recherche de trajectoires fonctionne main dans la main avec ce système prioritaire parce que la destination de l'algorithme A* est déterminée par l'état actuel et le but le plus prioritaire. Le système de recherche de trajectoires fonctionne de la main à la main parce que la destination de l'algorithme A* est déterminée par l'état actuel et le but le plus prioritaire.

Considérations relatives aux performances

La recherche de chemin A* sur plusieurs caractères d'IA en temps réel a été un défi important pour le matériel 1998. La demi-vie fonctionne sur des processeurs comme le Pentium II à 233-300 MHz avec une bande passante de mémoire limitée. Les développeurs ont mis en œuvre plusieurs stratégies d'optimisation pour s'assurer que la recherche de chemin ne consomme pas plus de 10-15% du budget du CPU par cadre.

CPU Budgétisation et fréquence de recherche de la voie

Chaque caractère AI n'effectue pas une recherche de chemin chaque image. La demi-vie utilise une approche en raccourcissant le temps[ : chaque personnage a un minuteur personnel qui détermine quand il peut demander un nouveau chemin. Le minuteur est randomisé dans une plage (généralement de 0,5 à 2,0 secondes) pour aplanir les requêtes de recherche de chemin entre les images. De plus, les caractères qui sont loin du joueur (au-delà d'un seuil de distance configurable) se voient attribuer un intervalle de temps beaucoup plus grand (jusqu'à 5 secondes) et peuvent utiliser une heuristique simplifiée qui ne nécessite pas une recherche complète A*. Ce niveau de détail basé sur la distance garantit que les ennemis éloignés semblent toujours se déplacer intelligemment sans perdre les cycles CPU sur la recherche de chemin précise que le joueur ne peut pas voir.

Niveau de détail pour AI

Les personnages au-delà d'une certaine distance du joueur sont promus à un état AI simplifié qui utilise uniquement l'évitement d'obstacles locaux sans recherche de chemin global. Ces personnages éloignés patrouillent et réagissent encore aux sons, mais leur mouvement est basé sur un comportement de errance simple qui choisit des points de repère aléatoires à proximité plutôt que de calculer un chemin A* complet. Lorsque le joueur approche à l'intérieur d'un seuil plus proche, le personnage est rétrogradé au système d'IA complet avec machine d'état et recherche de chemin. Cette transition est transparente parce que le comportement de errance est conçu pour être visuellement cohérent avec l'état de patrouille. Le système AI LOD réduit considérablement la charge globale de recherche de chemin, en particulier dans les niveaux avec de nombreux ennemis, tels que le “Surface Tension” chapitre où des dizaines de soldats engagent le joueur simultanément.

Impact et héritage du monde réel

Le système AI en demi-vie a établi un repère pour le comportement ennemi de tir de première personne qui a influencé l'ensemble de l'industrie. Des jeux comme Halo: Combat Evolved et F.E.A.R. citent directement la demi-vie comme une inspiration pour leurs conceptions d'IA. La combinaison de la navigation basée sur les nœuds avec la recherche de trajectoire A*, l'évitement dynamique des obstacles et une machine d'état hiérarchique est devenue le modèle standard pour l'IA dans les tireurs linéaires pendant au moins une décennie.

Les leçons techniques de Half-Life’s système d'IA sont toujours pertinentes pour les développeurs indépendants travaillant avec des budgets limités et les développeurs modernes optimisant pour les grands mondes ouverts. Le principal aperçu est que le comportement intelligent vient de l'interaction entre un algorithme de recherche de chemin et un système de décision, pas de l'un ou l'autre composant seul. Le réseau de nœuds fournit la conscience du terrain, A* fournit le calcul de route efficace, la machine d'État fournit les objectifs et les priorités, et l'évitement local fournit la flexibilité réactive.

Pour les développeurs intéressés à mettre en œuvre des systèmes similaires, des ressources comme GameDev.net’s introduction to A* fournissent des conseils pratiques sur les algorithmes de recherche de trajectoire, tandis que la documentation du Système AI du moteur source offre un aperçu de l'évolution de l'approche GoldSrc originale.

La navigation par nœuds peut produire des mouvements contre nature lorsque la densité de nœud est trop faible, et le positionnement manuel des nœuds est intensif et sujet à des erreurs. Les moteurs modernes ont largement évolué vers la génération automatique de maillage nav en utilisant la voxélisation ou des méthodes basées sur polygone. Cependant, les principes de la recherche hiérarchique de chemin, les demandes de trajets assortis de temps, la LOD basée sur la distance et la navigation mondiale-locale hybride restent les pierres angulaires de la conception de l'IA.