Abstract (FR)

Cette thèse aborde le problème de la génération de plans en temps-réel permettant le contrôle de plusieurs millions de personnages non-joueurs (PNJs) dans les jeux vidéo et les mondes virtuels. La planification d’actions basée sur des algorithmes de recherche, introduite dans le jeu F.E.A.R. en 2005, a une complexité temporelle exponentielle. Elle ne permet de ne gérer qu'au maximum plusieurs dizaines de PNJs par image et avec peu d'actions par plan. J'ai mené une étude approfondie des plans générés dans les jeux de tir à la première personne et cette étude montre que : (1) les états sont des vecteurs de valeurs énumérées, (2) les états initiaux et finaux peuvent être totalement définis, (3) les actions sont à la fois post-uniques et unaires, (4) les plans sont totalement ordonnés, et (5) les actions n'apparaissent qu’une seule fois dans les plans. (1) à (3) correspondent à des problèmes de planification polynomiaux du cadre Simplified Action Structure (SAS), mais pas (4) ni (5) : je présente donc de nouvelles restrictions satisfaisant (5) pour ces problèmes SAS et un nouvel algorithme de complexité linéaire satisfaisant (4). A l'aide d'expériences mettant en œuvre des problèmes de planification modélisés à partir de jeu-vidéo commerciaux, je montre que mon planificateur surpasse de façon spectaculaire les planificateurs SAS précédents et qu'il est en effet capable de construire des plans plus longs et pour plusieurs millions de PNJs en temps-réel.