Beauvais-Monestime, Katia
(2026).
« Replanification efficace de chemin dans un monde de jeu fortement dynamique » Mémoire.
Montréal (Québec), Université du Québec à Montréal, Maîtrise en informatique.
Fichier(s) associé(s) à ce document :
Résumé
Dans l’univers du jeu vidéo, les agents intelligents servent à enrichir le monde et l’expérience pour le joueur. Ils doivent être en mesure de se déplacer dans un monde réinterprété en tant que graphe de navigation. Il doit le faire de manière efficace et crédible tout en s’adaptant aux changements qui peuvent survenir. En planification de chemin dans les jeux vidéo, l’algorithme A* est souvent la solution utilisée pour répondre à ce besoin. Mais dans un contexte où le monde de jeu est constitué d’une grille 2D dont le facteur de branchement est très élevé, l’algorithme A* perd de son efficacité. Dans le cadre de ce mémoire, nous explorons différents algorithmes de planification de chemin ainsi que des techniques permettant de planifier un chemin plus efficacement dans un contexte dynamique, principalement la contraction hiérarchique. C’est une technique de prétraitement de graphe de navigation permettant d’avoir des raccourcis et d’accélérer la recherche de chemin. Le présent mémoire s’est basé sur cette dernière. Nous proposons une heuristique pour la contraction hiérarchique qui ajoute deux nouveaux critères dans le calcul de l’ordre de priorité des sommets, soit si le sommet est dynamique (SD) et le nombre de voisins directs du sommet courant étant dynamique (NVD). Nous comparons la recherche de chemin avec et sans la contraction hiérarchique en prétraitement sur le graphe. Nous constatons que le graphe hiérarchique est nettement plus efficace pour une carte en grille 2D. Nous évaluons la performance d’un graphe hiérarchique utilisant notre heuristique proposée face à un graphe hiérarchique utilisant l’heuristique de base. Ceci mène à la conclusion que, pour de grandes cartes, la contraction hiérarchique et la planification de chemin avec notre heuristique étaient moins efficaces que celle utilisant l’heuristique de base. Néanmoins, dans de plus petites cartes avec un plus petit nombre de sommets dynamiques, notre heuristique permet une contraction hiérarchique créant moins de raccourcis aidant à des planifications de chemin plus efficace. En réglant les limitations observées lors de ce mémoire, soit la sélection manuelle des sommets dynamiques et la grosseur des cartes de jeu causant une contraction hiérarchique trop longue, il serait possible d’avoir de meilleures performances avec la contraction hiérarchique qui utilise l’heuristique que nous avons proposée.
_____________________________________________________________________________
MOTS-CLÉS DE L’AUTEUR : planification de chemin, contraction hiérarchique, A*, jeux vidéo, heuristique, dynamisme
| Type: |
Mémoire accepté
|
| Informations complémentaires: |
Fichier numérique reçu et enrichi en format PDF/A. |
|
Directeur de thèse: |
Beaudry, Éric |
| Mots-clés ou Sujets: |
Planification de chemin / Algorithmes / Contraction hiérarchique / Jeux vidéo |
| Unité d'appartenance: |
Faculté des sciences > Département d'informatique |
| Déposé par: |
Service des bibliothèques
|
| Date de dépôt: |
17 mars 2026 14:35 |
| Dernière modification: |
17 mars 2026 14:35 |
| Adresse URL : |
https://archipel.uqam.ca/secure/id/eprint/19787 |
RECHERCHER
PARCOURIR
LIBRE ACCÈS
