Optimisation de la recherche d’un plus court chemin dans un environnement contenant des obstacles

🎯 Présentation du projet

Ce projet s’inscrit dans le cadre du TIPE (Travaux d’Initiative Personnelle Encadrés). Il porte sur l’optimisation de la recherche de plus courts chemins dans des environnements 2D comportant des obstacles.

Le pathfinding est un enjeu crucial dans les jeux vidéo et d’autres domaines où des agents doivent se déplacer efficacement dans un environnement complexe. L’objectif est de minimiser le temps de calcul et l’utilisation mémoire tout en respectant des contraintes physiques et structurelles propres à l’environnement.

📌 Problématique

Comment optimiser la recherche d’un plus court chemin dans un environnement restreignant les déplacements, tout en respectant des contraintes de temps et de mémoire ?

🛠️ Objectifs du projet

1. Modéliser un environnement 2D simplifié et implémenter une première version d’un algorithme de pathfinding en Python.
2. Améliorer l’efficacité de la recherche de plus courts chemins, mesurer et comparer les performances avec la version initiale.
3. Étendre l’étude à un cas plus complexe en modifiant la modélisation de l’environnement et/ou de l’entité à déplacer.
4. Évaluer la compatibilité de ces implémentations avec les contraintes typiques de temps réel et de mémoire dans les jeux vidéo.

🧩 Méthodologie

• Représentation de l’environnement via graphes (graphes de visibilité, grilles, any-angle pathfinding).
• Implémentation d’algorithmes classiques de recherche de chemin comme A*, puis amélioration par des optimisations.
• Étude comparative des performances en temps et en mémoire selon différentes approches.
• Application des méthodes issues de la géométrie algorithmique pour la détection de visibilité et le traitement des obstacles.

🔑 Mots-clés

• Pathfinding / Recherche de chemin
• Plus court chemin
• Graphe de visibilité
• Optimisation
• Géométrie algorithmique

📚 Références principales

• Anguelov B. Video Game Pathfinding and Improvements to Discrete Search on Grid-based Maps, 2011
• Oh S., Leong H. W. Edge N-Level Sparse Visibility Graphs: Fast Optimal Any-Angle Pathfinding, 2017
• Preparata F., Shamos M. I. Computational Geometry: An Introduction, 1985
• Boissonnat J.-D., Yvinec M. Géométrie algorithmique, 1995
• Kapi A. Y., Sunar M. S., Zamri M. N. A Review on Informed Search Algorithms for Video Games Pathfinding, 2020
• Lawande S. R., Jasmine G., Anbarasi J., Izhar L. I. A Systematic Review and Analysis of Intelligence-Based Pathfinding Algorithms in the Field of Video Games, 2022

🚀 Technologies

• Langage : Python
• Dépendences externes : math, random (génération aléatoire de polygones), tkinter (pour la visualisation), pathlib, sys, heapq, timeit (mesure de performances)

📂 Organisation du dépôt

├── grilles/            # Fichiers .txt décrivant des grilles
├── src/                # Code source Python
│   ├── basique/        # Implémentation basique
│   └── optimisation/   # Version optimisée
├── tests/              # Scripts de tests
├── docs/               # Documentation, schémas, compte-rendus
└── README.md           # Présentation du projet