NavMesh, A* et flow field : le pathfinding de 200 agents

Deux cents agents bloqués devant une seule porte

À la fin de l'année dernière, je travaillais sur une scène de siège : une unique porte de château et 200 instances de NavMeshAgent qui couraient dessus. La navigation en IA de jeu s'effondre exactement dans ce genre de scène. L'enregistrement que la QA avait joint au nightly build se figeait toujours au même endroit : à quinze mètres de la porte, une soixantaine d'agents se frottaient les uns aux autres en tremblant, certains reculaient. Dans les dix premières secondes, une quarantaine seulement atteignaient la cour située derrière la porte.

Le temps de frame était de 11 ms tant que les agents restaient loin, et montait à 26 ms dès qu'ils approchaient de la porte. Ma première intuition a été que A* avait explosé. Le profiler disait autre chose : NavMesh.CalculatePath totalisait 3,2 ms tandis que la mise à jour interne de NavMeshAgent se tenait à 9,8 ms. Le goulot d'étranglement n'était donc pas dans la recherche, mais dans le travail que chaque agent effectue à chaque frame.

Deux problèmes distincts apparaissaient en même temps et n'en formaient plus qu'un seul dans nos têtes : le coût du calcul du chemin global, et le comportement des agents les uns par rapport aux autres. Toute discussion qui range les deux sous le même titre tourne en rond, parce que les remèdes se trouvent à des endroits complètement différents. Tant qu'on ne les sépare pas, on ne voit jamais quel réglage a déplacé quel chiffre. Chez nous, la séparation a commencé par une habitude : suivre séparément, dans le profiler, la ligne de la recherche et celle de la mise à jour des agents.

Ce que le NavMesh regarde vraiment

Un NavMesh est un maillage de triangles généré à partir de la surface praticable de la scène, rétréci depuis chaque bord de la valeur du rayon de l'agent. La zone où un agent peut marcher n'est donc pas le sol que vous voyez dans le viewport. Quand un rapport d'agent bloqué arrive, la première chose à faire est d'afficher le mesh dans la fenêtre Navigation et de mesurer combien de centimètres de passage survivent réellement au seuil de la porte. Avec la Voxel Size par défaut de 0,166 m, j'ai vu plus d'une fois des polygones disparaître un à un dans les angles serrés.

Chez nous, l'ouverture de la porte faisait 1,6 m et l'Agent Radius 0,5 m : il restait une seule voie de 0,6 m, un agent passe, deux ne passent pas. Descendre le rayon à 0,35 avait l'air de la solution facile, mais les agents se sont mis à traverser les murs sur toute la carte. La bonne correction a été d'élargir la porte à 2,4 m côté level. Le rayon de l'agent n'est pas un réglage cosmétique : c'est l'unité de base de toute la navigation.

Le deuxième piège classique est une destination posée hors du mesh. SetDestination renvoie alors false et personne ne lit la valeur de retour, ou bien le chemin arrive en NavMeshPathStatus.PathPartial : l'agent marche jusqu'au point atteignable le plus proche et attend là. Vu de l'extérieur, cela ressemble exactement à "il est bloqué". Plaquer chaque destination sur le mesh avec NavMesh.SamplePosition dans un rayon de 2 m a fait disparaître la plupart de ces rapports. Appliquez le même contrôle aux points de spawn : un agent né hors du mesh est perdu dès sa première frame.

Les discontinuités comme les escaliers, les trous et les portes demandent des off-mesh links. Les composants OffMeshLink placés à la main se comportent bien plus prévisiblement que ceux générés automatiquement. Avec le coût par défaut de 1.0, 140 de nos 200 agents essayaient de s'engouffrer dans un unique trou de 1,2 m ; passer costOverride à 5.0 en a poussé la plupart vers l'itinéraire plus long mais dégagé. Gardez les deux extrémités d'un link sur le mesh : un link dont une extrémité pend dans le vide est ignoré en silence.

Le coût d'A* et le pathfinding hiérarchique

Le coût du A* pathfinding croît avec le nombre de nœuds explorés. Sur un NavMesh de 41.000 polygones, une requête d'un bout de la carte à l'autre prenait 0,35 ms. Deux cents agents qui demandent dans la même frame, cela ferait 70 ms, mais un tel à-coup, vous ne le verrez jamais : Unity met les requêtes en file, le chemin arrive trois ou quatre frames plus tard, et les agents continuent pendant ce temps sur l'ancien cap. Le symptôme n'est pas un blocage, c'est un virage en retard.

Le pathfinding hiérarchique coupe ce coût deux fois de suite. On découpe la carte en régions et on écrit les transitions entre elles sous forme de portails dans un graphe ; la recherche tourne d'abord sur un graphe grossier de 30-40 nœuds (0,02 ms), puis un A* détaillé ne va que jusqu'au portail suivant. Notre requête moyenne est passée de 0,35 ms à 0,06 ms, et le chemin complet d'un agent n'a plus jamais été calculé d'un seul coup. Le graphe grossier est construit une fois au bake et n'est mis à jour à l'exécution que lorsqu'un obstacle dynamique ferme un portail.

L'alternative que nous avons essayée puis abandonnée était un cache de chemins partagé. Nous arrondissions les destinations à des cellules de 4 m et donnions un même chemin à tous les agents visant la même cellule. Le taux de réussite atteignait 70 % sur des cibles statiques, mais tombait à 18 % en poursuite du joueur, et la logique d'invalidation reprenait plus que le cache ne faisait gagner. Nous avons supprimé le code. Le partage de chemins ne se justifie que là où la destination reste immobile pendant des dizaines de frames.

Un seul flow field pour toute la foule

Si 200 agents partagent la même destination, lancer 200 recherches distinctes n'a aucun sens. Un flow field exécute une unique propagation de coût en remontant depuis le but, puis écrit dans chaque cellule un vecteur de direction pointant vers son voisin le moins cher. Le nôtre était une grille de 128x128 à 0,5 m par cellule, et une reconstruction complète prenait 4,1 ms. La propagation remplit toutes les cellules en une passe : le coût est donc totalement indépendant du nombre d'agents.

Ce qui compte, c'est que ces 4,1 ms se paient quand la cellule but change, et non à chaque frame. Pendant que le joueur courait, cela arrivait trois ou quatre fois par seconde, soit environ 14 ms par seconde. Le coût par agent se réduit à deux échantillonnages bilinéaires : 0,004 ms, soit 0,8 ms pour 200 agents. La même foule coûtait 12 ms en A* hiérarchique.

La limite est nette : chaque destination distincte veut son propre champ. Au-delà de trois ou quatre buts, la mémoire et le coût de reconstruction dépassent l'A*. Nous sommes donc restés hybrides : les NPC nommés et les agents boss sur A*, la simulation de foule sur le flow field. Les deux reposent sur les mêmes triangles du NavMesh, seule la source du cap change. La distinction tient dans un unique bool dans le code, et un designer peut la basculer sur le prefab.

Le local avoidance n'est pas de la navigation globale

RVO, et ORCA qui en dérive, ne font qu'une chose : chaque agent lit la position et la vitesse de ses voisins, retranche par demi-plans les vitesses qui mènent à une collision, puis choisit dans ce qui reste celle qui est la plus proche de sa vitesse préférée. Son horizon est d'une seconde ou deux et il ne sait rien de la géométrie du niveau. C'est une correction de cap, pas de la navigation. Laissez un agent seul avec ça et RVO ne l'amènera jamais au but.

C'est pourquoi attendre une solution globale du local avoidance est faux dès le départ. Contre un mur de cour en U, RVO colle l'agent à la paroi et deux agents qui se croisent de face se bloquent mutuellement. Passer obstacleAvoidanceType à HighQuality ne corrige rien ; cela mange seulement 6,2 des 9,8 ms sur 200 agents. Redescendre à Good a ramené le chiffre à 3,9 ms, sans différence visible à distance de caméra.

Le vrai gain était dans le champ avoidancePriority. Tant que tous les agents restent à la valeur par défaut de 50, la situation demeure symétrique et personne ne cède le passage. Distribuer au spawn une priorité aléatoire entre 0 et 99 a fait passer l'embouteillage devant la porte de 4,2 secondes à 1,1 seconde. C'était une modification d'une seule ligne.

Obstacles dynamiques et budget de path requests

Les obstacles dynamiques passent par NavMeshObstacle et le carving, mais le carving refait le bake de la tile à chaque déplacement. Avec 12 tonneaux qui roulaient dans la scène, nous voyions des spikes réguliers de 5,8 ms. Monter carvingMoveThreshold à 0,5 m et activer carveOnlyStationary a ramené la même scène à 0,9 ms. Ne faites jamais d'un objet en mouvement permanent un obstacle : ceux-là relèvent du local avoidance.

La partie budget est simple : fixez le nombre de requêtes de chemin complètes autorisées par frame. Chez nous, c'est 12. Les agents demandent selon un intervalle de 0,45 seconde plus un décalage aléatoire de 0-0,15 seconde, car sans ce jitter la vague de spawn range toutes les requêtes dans la même frame. Quand le budget est plein, la requête n'est pas annulée, elle glisse à la frame suivante, et personne ne s'en aperçoit puisque l'agent continue entre-temps sur son chemin existant. Mesurez ce budget sur le matériel cible : les 12 que nous utilisons sur console tiennent sans peine à 30 sur desktop.

Dans cette scène, le temps de frame total est passé de 26 ms à 13,4 ms et la part du pathfinding de 13 ms à 2,1 ms, et le gain le moins cher là-dedans était la modification d'une ligne sur la priorité. Ordonnez le travail ainsi : vérifiez d'abord la géométrie du NavMesh de vos propres yeux, posez ensuite un budget de requêtes par frame, déplacez ensuite la foule sur un flow field, et ne touchez aux réglages du local avoidance qu'en tout dernier. Dans l'ordre inverse, des heures disparaissent dans les paramètres d'ORCA pendant que la porte de 0,6 mètre reste exactement où elle était. Ne changez aucun réglage que vous n'avez pas mesuré : tous les chiffres donnés ici sortent du profiler, aucun d'une supposition.