NaviGator

🎯 Le Contexte & L'Objectif

NaviGator est né dans le cadre de la SAE du quatrième semestre du BUT Informatique à l'IUT de Montpellier. Le sujet était ambitieux : construire un calculateur d'itinéraires capable de trouver le chemin le plus court entre plusieurs communes françaises, en s'appuyant sur les données géographiques réelles du réseau routier national. Pas de simple exercice algorithmique — il s'agissait de créer une véritable application web, utilisable et performante, capable de traiter un graphe de dizaines de milliers de nœuds routiers couvrant l'ensemble de la France métropolitaine.

Le cahier des charges imposait l'implémentation de l'algorithme A*, mais le projet allait bien au-delà. Nous avons construit un produit complet intégrant la gestion d'utilisateurs, un historique de trajets persistant, la possibilité de définir des étapes intermédiaires, une carte interactive avec sélection au clic, de l'autocomplétion sur les noms de communes et une estimation de consommation de carburant en fonction du véhicule de l'utilisateur.

🛠️ Ma Contribution & Mon Rôle

Nous étions une équipe de trois développeurs, et la plupart des sujets ont été traités de manière collaborative — les pourcentages d'investissement étaient d'ailleurs très équilibrés. Mon rôle principal était celui de responsable base de données, mais j'ai également contribué activement au backend PHP, au JavaScript et au webdesign.

Concrètement, voici ce que nous avons réalisé collectivement, avec mes responsabilités spécifiques mises en avant :

• Base de données PostgreSQL/PostGIS (ma responsabilité principale) : conception du schéma relationnel, création des vues matérialisées, écriture des procédures stockées PL/pgSQL, et mise en place de l'indexation (B-tree, GiST) pour optimiser les performances du calcul d'itinéraire sur un jeu de données volumineux.
• Optimisations SQL (ma responsabilité) : conception de la vue matérialisée vitesses_route exploitant les jointures spatiales PostGIS (ST_DWithin, ST_Expand) pour pré-calculer les connexions entre nœuds routiers avec les vitesses associées à chaque type de voie — un choix déterminant pour les performances de l'algorithme A*.
• Backend PHP & architecture : nous avons développé les services et leurs interfaces (ServiceInterface), structuré l'architecture MVC, et construit les templates Twig. De mon côté, j'ai contribué au refactoring du code et à une partie des vues Twig.
• Programmation réactive : nous avons mis en place un moteur de réactivité en JavaScript vanilla — un système de Proxy-based reactivity inspiré de Vue.js, permettant de lier automatiquement les interactions utilisateur aux mises à jour du DOM sans framework.
• Webdesign : nous avons intégré des effets visuels avancés (parallax, animations au scroll) pour donner du caractère à l'interface, en réutilisant des composants issus de mon ancien portfolio.

💻 Stack Technique

• Backend : PHP 8.x structuré en MVC, alimenté par les composants Symfony (Routing, DependencyInjection, HttpKernel, HttpFoundation) pour le routage, l'injection de dépendances et la résolution des contrôleurs. Twig 3 pour le rendu des vues côté serveur, avec un système de fonctions personnalisées pour la génération d'URL et la gestion des sessions.
• Base de données : PostgreSQL avec l'extension PostGIS pour la manipulation de données géométriques. Vues matérialisées pour pré-calculer les adjacences du graphe routier, procédures stockées PL/pgSQL pour encapsuler la logique métier (inscription, historique), et indexation GiST sur les colonnes géométriques pour accélérer les requêtes spatiales.
• Frontend : JavaScript vanilla structuré en modules ES6, avec un moteur de réactivité fait maison (Proxy + WeakMap). OpenLayers pour le rendu cartographique interactif (marqueurs, tracé d'itinéraire, interaction au clic). CSS custom avec effets parallax et animations au scroll.
• Authentification : double mécanisme — sessions PHP côté serveur pour l'interface web, et JSON Web Tokens (JWT via firebase/php-jwt) pour les endpoints API REST.
• Tests : PHPUnit 9 pour les tests unitaires du service de plus court chemin et de la reconstruction d'itinéraire.

⚙️ Architecture & Défis Techniques

A* sur un graphe géospatial massif

Le défi principal résidait dans l'application de l'algorithme A* sur un graphe réel de plusieurs dizaines de milliers de nœuds routiers. Contrairement à un exercice académique classique sur grille, chaque nœud est géolocalisé et ses voisins sont déterminés par les tronçons routiers physiques. L'heuristique choisie — la formule de Haversine — calcule la distance à vol d'oiseau en tenant compte de la courbure terrestre, garantissant une estimation admissible qui ne surestime jamais la distance réelle.

// Heuristique de Haversine — distance à vol d'oiseau sur la sphère terrestre
public function getHeuristiqueHaversine(float $latArrivee, float $longArrivee, float $lat, float $long): float {
    $dLat = deg2rad($latArrivee - $lat);
    $dLon = deg2rad($longArrivee - $long);
    $a = sin($dLat / 2) ** 2 + cos(deg2rad($lat)) * cos(deg2rad($latArrivee)) * sin($dLon / 2) ** 2;
    $c = 2 * asin(sqrt($a));
    return self::EARTH_RADIUS * $c;
}

Pour les itinéraires multi-étapes (ex. Montpellier → Paris → Brest), l'algorithme est exécuté séquentiellement entre chaque paire de points, en réinitialisant les structures de données internes à chaque segment tout en accumulant le chemin global, les distances et les temps de parcours.

Cache par département et vues matérialisées

Charger l'intégralité du graphe routier en mémoire était inenvisageable. Nous avons opté pour un cache par département : seuls les nœuds du département courant sont chargés en mémoire, et lorsqu'un nœud franchit une frontière départementale, le département adjacent est récupéré à la volée. Ce mécanisme, couplé à une vue matérialisée vitesses_route qui pré-calcule les jointures spatiales PostGIS et associe chaque tronçon à sa vitesse autorisée, a permis de réduire considérablement les temps de calcul.

L'indexation GiST sur les colonnes géométriques, combinée à des index B-tree sur les identifiants de département et les clés primaires, garantit des temps de réponse acceptables même sur les trajets longue distance.

Réactivité JavaScript sans framework

Plutôt que d'intégrer React ou Vue, nous avons développé un moteur réactif en JavaScript vanilla basé sur le pattern Proxy. Le système intercepte les accès en lecture (pour enregistrer les dépendances) et en écriture (pour déclencher les effets) sur des objets réactifs, exactement comme le fait le reactivity core de Vue 3.

// Proxy-based reactivity — enregistrement et déclenchement automatique des effets
function reactive(passiveObject, name) {
    objetDependencies.set(passiveObject, new Map());
    const handler = {
        get(target, key) {
            if (registeringEffect !== null) registerEffect(target, key);
            return target[key];
        },
        set(target, key, value) {
            target[key] = value;
            trigger(target, key);
            return true;
        },
    };
    return new Proxy(passiveObject, handler);
}

Ce système gère les ajouts/suppressions d'étapes dans le formulaire d'itinéraire, la mise à jour dynamique des marqueurs sur la carte OpenLayers, et les interactions avec l'historique — le tout sans rechargement de page.

Interaction cartographique et nœud le plus proche

L'intégration avec OpenLayers dépasse le simple affichage de carte. Un clic sur la carte déclenche un appel API vers le serveur pour récupérer le nœud routier le plus proche des coordonnées cliquées (en exploitant les fonctions spatiales PostGIS), puis place automatiquement un marqueur et remplit le champ de destination correspondant. Cette fonctionnalité, combinée à l'autocomplétion textuelle des noms de communes, offre deux modes de saisie complémentaires et fluides.

🚀 Résultats & Impact

• Itinéraires opérationnels : l'application calcule des trajets réalistes sur l'ensemble de la France métropolitaine, avec distance, temps estimé et consommation de carburant affichés instantanément.
• Multi-étapes : jusqu'à 10 étapes intermédiaires prises en charge, chacune avec autocomplétion ou sélection par clic sur la carte.
• Performance : grâce au cache par département et aux vues matérialisées, les trajets longue distance (ex. Perpignan → Lille) sont calculés en quelques secondes malgré le volume du graphe routier.
• Expérience utilisateur soignée : carte interactive, parallax, chargement asynchrone des résultats, historique des trajets consultable et rejouable, estimation de consommation personnalisée selon le véhicule.
• Collaboration efficace : projet mené à bien en équipe de 3, avec une répartition claire des responsabilités et un travail collaboratif constant facilité par une bonne organisation (Discord, Git).

💡 Ce que j'ai appris

NaviGator a été mon premier contact avec les données géospatiales à grande échelle. Manipuler PostGIS, comprendre les index spatiaux GiST, et concevoir des vues matérialisées pour pré-calculer des jointures coûteuses m'a appris que la performance d'un algorithme dépend autant de la manière dont les données sont organisées en base que de l'algorithme lui-même. Sans les optimisations côté SQL — vues, index, procédures — le A* aurait été inutilisable en conditions réelles.

Le travail sur le moteur réactif en JavaScript nous a permis de comprendre en profondeur les mécanismes internes de frameworks comme Vue.js. Implémenter soi-même le tracking de dépendances par Proxy et l'exécution différée des effets donne une compréhension qu'aucun tutoriel ne peut offrir.

Avec le recul, plusieurs améliorations s'imposeraient :

• Utiliser Dijkstra bidirectionnel ou des hiérarchies de contraction (Contraction Hierarchies) pour améliorer les temps de calcul sur les trajets très longs — A* seul atteint ses limites sur un graphe de cette taille.
• Remplacer le cache par département par un chargement par bounding box : les frontières départementales sont un découpage administratif, pas géographique, et peuvent provoquer des chargements inutiles.
• Ajouter un cache côté client (Service Worker ou localStorage) pour éviter de re-calculer les trajets déjà consultés.
• Intégrer des données de trafic temps réel pour pondérer dynamiquement les vitesses de chaque tronçon — une évolution naturelle vers un vrai GPS collaboratif.