Résumé Technique : Validation des Navmesh par Géométrie : Analyse Voxelisée avec Exploration Priorisée

Énoncé du Problème

Les maillages de navigation (navmeshes) sont fondamentaux pour le déplacement des personnages non jouables (PNJ) dans les jeux vidéo, définissant les zones praticables et la connectivité. Cependant, dans le développement de jeux à grande échelle, les environnements sont dynamiques ; le terrain, les assets et la géométrie de collision changent fréquemment. Par conséquent, les navmeshes échouent souvent à se régénérer en parfaite synchronisation avec ces changements, entraînant des incohérences entre les données de navigation et l'espace réellement praticable défini par la géométrie sous-jacente.

Les méthodes de validation automatisées existantes reposent généralement sur une exploration basée sur des agents (par exemple, des agents d'apprentissage par renforcement naviguant dans le monde) ou sur une analyse du comportement en temps d'exécution. Ces approches infèrent les problèmes indirectement — par exemple, un agent bloqué ou incapable d'atteindre une cible — plutôt que de vérifier explicitement si la représentation de navigation reflète fidèlement la géométrie réelle. De plus, ces méthodes sont coûteuses en calcul, difficiles à intégrer dans des pipelines automatisés et échouent souvent à détecter des incohérences structurelles qui ne se manifestent pas immédiatement par des échecs en temps d'exécution. Il existe un manque de méthodes directes et hors ligne pour valider l'exactitude des navmeshes indépendamment de la simulation en temps d'exécution.

Méthodologie

L'article propose un cadre hors ligne qui traite la validation des navmeshes comme un problème de cohérence géométrique. Au lieu de simuler le comportement d'un agent, le système reconstruit indépendamment l'espace praticable à partir de la géométrie de l'environnement et le compare au navmesh généré par le moteur. La méthodologie se compose de trois composants principaux :

1. Reconstruction de l'Espace Praticable par Voxélisation

Le système reconstruit une référence indépendante de l'espace praticable directement à partir du terrain et de la géométrie de collision en utilisant une représentation basée sur des voxels :

• Voxélisation : Les cartes de hauteur du terrain et les maillages de collision des assets sont convertis en une grille 3D discrète de voxels.
• Classification Sensible aux Contraintes : Chaque voxel est évalué par rapport aux contraintes de navigation (limites de pente, hauteur de marche, rayon de l'agent et dégagement vertical) dérivées de la configuration du moteur de jeu. Les voxels ne respectant pas ces contraintes sont écartés.
• Graphe de Connectivité : Les voxels praticables restants forment un graphe $G_v = (V_w, E)$, où l'adjacence est déterminée par un rayon de voisinage. Un algorithme de remplissage (flood-fill) extrait le composant connexe principal pour éliminer les artefacts isolés, aboutissant à un modèle de accessibilité dérivé de la géométrie $R_{vox}$.

2. Exploration Priorisée Guidée par l'Apprentissage

Puisqu'une validation exhaustive de grands espaces de voxels est prohibitive en termes de calcul, le cadre formule l'exploration comme un problème de recherche priorisée :

• Apprentissage par Renforcement (RL) : Un Double Deep Q-Network (DDQN) est entraîné pour guider le processus d'échantillonnage. L'agent RL ne simule pas la navigation ; il apprend plutôt une politique pour prioriser les régions ayant une probabilité plus élevée de contenir des incohérences.
• État et Récompense : L'état inclut le contexte géométrique local, l'importance sémantique (par exemple, la proximité des routes de patrouille ou des points de réapparition) et l'historique de l'exploration. La fonction de récompense encourage la visite de régions sémantiquement importantes tout en pénalisant les étapes redondantes et les revisites.
• Rejeu d'Expérience Priorisé : Le processus d'entraînement utilise un rejeu d'expérience priorisé pour se concentrer sur les transitions associées à des régions à haute valeur ou structurellement complexes, accélérant ainsi la convergence.

3. Validation de la Cohérence

Pour chaque position échantillonnée par la politique guidée par le RL :

• Le système interroge le moteur pour déterminer l'accessibilité sur le navmesh généré ($R_{nav}$).
• Il compare $R_{nav}$ à l'accessibilité dérivée de la géométrie $R_{vox}$.
• Un mismatch ($R_{nav} \neq R_{vox}$) signale une incohérence potentielle.
• Post-Traitement : Les incohérences détectées subissent un filtrage basé sur la tolérance et un regroupement spatial (analyse de composantes connexes) pour éliminer les artefacts mineurs causés par la discrétisation des voxels, ne conservant que les régions de défauts structurellement significatives.

Contributions Clés

1. Formulation de la Cohérence Géométrique : L'article formule la validation des navmeshes comme une comparaison directe entre la praticabilité dérivée de la géométrie et la connectivité du navmesh, découplant la validation du comportement de l'agent et de la simulation en temps d'exécution.
2. Modèle de Référence Basé sur les Voxels : Il introduit une représentation basée sur les voxels et sensible aux contraintes qui reconstruit l'espace praticable à partir de données brutes de terrain et de collision, servant de vérité terrain indépendante pour la validation.
3. Exploration Guidée par l'Apprentissage : L'ouvrage démontre l'utilisation de l'apprentissage par renforcement non pas pour la simulation de navigation, mais pour prioriser l'exploration. Cette approche améliore considérablement l'efficacité de la validation en concentrant l'échantillonnage sur les régions susceptibles de contenir des défauts, surpassant les stratégies d'échantillonnage uniforme et heuristique.
4. Pipeline Prêt pour la Production : Le cadre est conçu comme un outil hors ligne intégré au sein du moteur de jeu, capable de traitement parallèle et d'intégration dans des flux de travail de QA automatisés pour des environnements à grande échelle et évolutifs.

Résultats Expérimentaux

Le cadre a été évalué sur plusieurs environnements de production à grande échelle utilisant à la fois les moteurs Unity et Anvil d'Ubisoft.

• Efficacité : La stratégie priorisée guidée par l'apprentissage a nécessité environ 45 % d'échantillons en moins que le parcours exhaustif (BFS/DFS) et 24 % d'échantillons en moins que l'échantillonnage heuristique basé sur l'importance pour atteindre des niveaux de couverture similaires (85 % de couverture pondérée par l'importance).
• Détection : Bien que les taux de détection aient été comparables entre les méthodes (variant d'environ 87 % à 92,6 %), la méthode proposée a atteint le taux de détection le plus élevé (92,6 %) avec le nombre d'échantillons le plus faible (55 % de la ligne de base).
• Faux Positifs : L'approche RL priorisée a maintenu un faible taux de faux positifs (4,1 %), comparable ou supérieur à celui des autres stratégies, grâce au post-traitement par filtrage basé sur la tolérance et regroupement.
• Évolutivité : Les temps de reconstruction et de validation se sont révélés pratiques pour une utilisation en production, la validation complète de grandes régions s'achevant en 1 à 7 minutes.

Importance et Revendications

L'article revendique que cette approche offre une méthode directe, déterministe et répétable pour valider l'exactitude des navmeshes. En s'appuyant principalement sur la géométrie et les requêtes du moteur, la méthode est adaptable à différents moteurs de jeu avec des modifications minimales.

L'importance réside dans le changement de paradigme, passant de la « recherche de bugs via l'échec de l'agent » à la « vérification de la cohérence structurelle via la comparaison géométrique ». Cela permet de détecter des erreurs de navigation qui pourraient ne pas bloquer immédiatement un agent mais qui représentent un mismatch fondamental entre la conception du monde et les données de navigation. Le cadre permet une assurance qualité automatisée et évolutive capable de suivre les cycles d'itération rapides du développement de jeux en monde ouvert moderne, garantissant que les données de navigation restent synchronisées avec l'environnement de jeu évolutif sans nécessiter de simulations en temps d'exécution coûteuses.