PathVisualizer C++ / WebAssembly

Un visualiseur interactif d'algorithmes de recherche de chemin (Pathfinding), développé avec un backend en C++ compilé en WebAssembly (Wasm), et un frontend en HTML/CSS/JS.

Fonctionnalités

• Algorithmes implémentés :
  • BFS (Breadth-First Search) : Recherche en largeur classique, idéale pour trouver le chemin le plus court (en nombre de sauts) dans un graphe non pondéré.
  • Dijkstra : Implémentation complète basée sur l'ouvrage Introduction to Algorithms (Cormen et al.), avec gestion des poids des arêtes via une file de priorité (Min-Heap). Cet algorithme garantit le chemin le moins coûteux.
• Interactions en temps réel :
  • Placement libre des points de départ et d'arrivée.
  • Outil de dessin de murs (obstacles infranchissables).
  • Outil "Boue" (Terrain lourd avec un coût de déplacement augmenté pour démontrer l'utilité de Dijkstra face au BFS).
  • Bascule dynamique entre une grille à 4 directions (orthogonales) et 8 directions (diagonales).
• Hautes Performances :
  • Le calcul du graphe est entièrement déporté sur le binaire C++ exécuté via WebAssembly.
  • Cela garantit un temps de résolution extrêmement rapide (de l'ordre de la milliseconde), même sur des grilles très denses, surpassant largement une implémentation purement JavaScript.

Architecture du Projet

Le projet suit une architecture stricte de séparation des responsabilités, illustrant une intégration avancée entre le web et les langages de bas niveau :

1. Couche Présentation & Contrôle (JavaScript / DOM) :
   • Gère les interactions utilisateur (clics, dessins).
   • Construit dynamiquement la structure du graphe (nœuds, arêtes, poids) en fonction de l'état visuel de la grille.
   • Gère les animations de l'exploration et du chemin final.
2. Couche de Liaison (Emscripten / Embind) :
   • Agit comme un pont (Glue Code) entre le JS et le C++.
   • Permet la conversion transparente et sécurisée des structures de données (tableaux plats JS vers structures std::vector et std::map en C++).
3. Moteur Logique (C++) :
   • Le cœur du système. Il reçoit la définition abstraite du graphe (nœuds et arêtes).
   • Exécute l'algorithme sélectionné de manière optimisée.
   • Retourne le chemin optimal ainsi que l'ordre exact des nœuds explorés.

Comment lancer le projet (Environnement Docker)

Pour éviter les problèmes complexes liés à l'installation locale du compilateur C++ vers WebAssembly (emcc), ce projet utilise Docker et Docker Compose pour gérer à la fois la compilation et l'hébergement local.

Prérequis

• Avoir Docker Desktop installé et en cours d'exécution sur votre machine.

Instructions d'installation

1. Cloner le dépôt :

   git clone [https://github.com/bi-aya/Labyrinth-ProjetCpp.git](https://github.com/bi-aya/Labyrinth-ProjetCpp.git)
   cd Labyrinth-ProjetCpp
   

2. Lancer l'environnement : Dans votre terminal, à la racine du projet, exécutez :

   docker compose up
   

3. Accéder à l'application : Ouvrez votre navigateur web et rendez-vous à l'adresse : http://localhost:8085

Cycle de développement

• Si vous modifiez les fichiers web (index.html, CSS, JS) : Rechargez simplement la page web (F5), les changements sont immédiats.
• Si vous modifiez le code logique (logic.cpp) :
  1. Arrêtez le processus Docker dans votre terminal avec Ctrl+C.
  2. Relancez docker compose up. Le compilateur Emscripten regénérera automatiquement les fichiers .wasm et pathfinding.js avant de démarrer le serveur.

Références

• Introduction to Algorithms, Fourth Edition (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein) pour l'implémentation formelle de Dijkstra.