📌 Projet de Fin de Module : Algorithme de Pathfinding

📝 Introduction

Ce projet vise à implémenter un algorithme permettant de trouver le plus court chemin dans un graphe. Il s'inscrit dans le cadre de l'évaluation de la première année de Coda et met l'accent sur :

• La lecture et l'analyse de fichiers contenant des graphes.
• L'implémentation d'algorithmes de recherche de chemin tels que BFS (Breadth-First Search), Dijkstra et A*.
• La gestion efficace des structures de données pour la représentation et l'exploration du graphe.

---

🚀 Fonctionnalités

📂 Lecture et analyse du graphe

• Chargement d'un graphe à partir d'un fichier texte.
• Extraction des informations essentielles :
  • Nœuds et arêtes
  • Poids des arêtes (si applicable)
  • Définition du nœud de départ et d’arrivée

🔍 Algorithmes de pathfinding implémentés

• BFS : Algorithme simple pour les graphes non pondérés.
• Dijkstra : Algorithme efficace pour trouver le chemin le plus court dans un graphe pondéré.
• A* : Version optimisée avec heuristique pour accélérer la recherche.

📊 Affichage des résultats

• Affichage du chemin optimal et de sa distance totale.
• Indication des nœuds explorés.
• Visualisation optionnelle du graphe.

❌ Gestion des erreurs

• Fichier introuvable ou mal formaté.
• Absence de chemin entre deux nœuds.
• Incohérences dans les données du graphe.

---

⚙️ Installation et exécution

📥 Prérequis

• Langage : C
• Compilateur : GCC (ou tout autre compilateur C compatible)
• Outils : Makefile pour la compilation

📦 Installation

1. Cloner le projet

   git clone https://github.com/Logipek/Pathfinding.git
   cd Pathfinding
   

2. Compiler le projet

   make
   

   L'exécutable pathfinding sera généré.

▶️ Exécution

Lancer le programme avec un fichier de graphe en argument :

./pathfinding <nom_fichier_graphe>

Exemple :

./pathfinding exemple.txt

---

📄 Format du fichier graphe

Le fichier doit suivre ce format :

nombre_de_noeuds
noeud1 noeud2 poids
noeud2 noeud3 poids
...
debut fin

Exemple :

5
A B 4
A C 2
B C 5
B D 10
C D 3
C E 8
D E 6
A E

---

🔬 Tests et validation

📌 Tests unitaires

Des tests unitaires sont fournis pour valider les fonctions critiques du projet.

make test

🐛 Debugging

Utiliser gdb pour le débogage :

gdb ./pathfinding

---

📈 Améliorations futures

• Ajout d’une interface graphique pour la visualisation du graphe.
• Prise en charge des graphes orientés et non pondérés.
• Optimisation des performances avec des structures de données avancées (tas binaire, arbre AVL).

---

📝 Licence

Projet sous licence MIT.

📞 Contact

Logipek - hugo-damion.me

Projet disponible sur GitHub : Pathfinding