Champs de flux : partager une destination sans imposer un chemin unique et rigide

Mutualiser la requête coûteuse vers une destination

Lorsque de nombreuses unités partagent la même destination, un champ de flux (flow field) peut remplacer des recherches d'itinéraire individuelles répétées par un guidage commun. Chaque unité lit une direction à proximité de sa position actuelle ; il n'est donc pas nécessaire de construire un chemin complet supplémentaire pour chaque déplacement. Le résultat réutilisable reste toutefois lié à une destination et à un modèle de déplacement précis. Emerson décrit une implémentation par tuiles ; Patel explique la recherche sous-jacente de toutes les sources vers un seul objectif. [1][2]

Séparer coût de traversée, intégration et direction

Il faut distinguer le coût d'entrée ou de traversée d'un terrain du coût intégré pour atteindre l'objectif. Dans un modèle de graphe discret, on pose D(goal) = 0 et on résout D(x) = min(c(x,y) + D(y)) sur les arêtes sortantes autorisées. Avec des poids non négatifs, une recherche de Dijkstra inversée permet de construire ces distances. On parcourt les arêtes inversées tout en conservant leurs coûts d'origine, dans le sens direct.

Il faut stocker explicitement un marqueur d'inaccessibilité. La direction choisie doit être une direction sortante autorisée, évaluée avec le même modèle de coût ; se contenter de suivre le voisin dont la distance stockée est la plus faible ne suffit pas lorsque les coûts des arêtes diffèrent.

Exemple détaillé : la route dont le reste est le plus court n'est pas toujours la moins chère

À un carrefour, la route A coûte d'abord 8, puis il reste un coût de 1. La route B coûte d'abord 1, puis il reste un coût de 4. Leurs totaux sont 8 + 1 = 9 et 1 + 4 = 5. Le champ doit donc orienter une unité vers B, même si la distance restante de A est plus petite.

Supposons que 200 unités partagent cette destination et cette classe de déplacement. Elles peuvent partager le même champ une fois calculé ; cela ne signifie pas que leur résolution des collisions ou leur pilotage (steering) soient eux aussi mutualisés ou gratuits. Ces coûts et ces nombres d'unités sont donnés à titre d'illustration d'une conception, et non comme un gain de performance mesuré.

Construire un champ que l'on puisse inspecter

On commence par une petite carte comportant un mur, une bande coûteuse et une poche inaccessible. On représente séparément les coûts de traversée, les valeurs intégrées et les directions choisies. On suit les flèches depuis chaque cellule accessible pour vérifier que l'on arrive à destination sans cycle. On contrôle que le guidage en diagonale respecte les mêmes règles de coin que celles utilisées pour générer les distances.

Les champs en cache sont indexés par objectif, classe de déplacement et version pertinente du terrain. Il faut reconstruire les données concernées lorsqu'un pont disparaît ou qu'une autorisation de traversée change. Les générations de champs terminées doivent être publiées ensemble, afin que les unités ne lisent jamais des distances et des directions partiellement mises à jour. Il faut aussi tester les transitions aux frontières de tuiles et les unités qui entrent depuis des positions inattendues.

Budgéter séparément le partage et l'exécution physique

Un grand nombre d'objectifs ou de classes de déplacement distincts réduit la réutilisation et multiplie les données en cache. Des cellules grossières peuvent masquer des passages étroits, et des vecteurs interpolés près des murs peuvent pointer à travers des obstacles. Un champ fournit un guidage d'itinéraire ; l'encombrement du corps, la séparation, la circulation dans les goulets d'étranglement et l'occupation de la destination demandent encore un traitement explicite. Avant de décider de ce que le champ partagé économise réellement pour le déplacement de la foule, il faut mesurer séparément la construction du champ, le renouvellement du cache, l'échantillonnage et le mouvement local.

Sources

• [1] Crowd Pathfinding and Steering Using Flow Field Tiles — Elijah Emerson, Game AI Pro.
• [2] Flow Field Pathfinding for Tower Defense — Amit Patel, Red Blob Games.