Planification de chemin en temps réel pour des agents virtuels dans des environnements dynamiques

Nous présentons une approche novatrice pour la planification de chemin en temps réel de plusieurs agents virtuels dans des scènes dynamiques complexes. Nous introduisons une nouvelle structure de données, le Graphique de Navigation Multi-agent (MaNG), qui est construit à partir des diagrammes de Voronoi de premier et de second ordre. Le MaNG est utilisé pour effectuer la planification d'itinéraire et les calculs de proximité pour chaque agent en temps réel. Nous calculons le MaNG en utilisant du matériel graphique et présentons des techniques de culling pour accélérer le calcul. Nous abordons également les problèmes de sous-échantillonnage pour un calcul précis. Notre algorithme est utilisé pour la planification multi-agent en temps réel dans des scénarios de poursuite-évasion et de simulation de foule composés de centaines d'agents en mouvement, chacun ayant un objectif distinct.