Propagation
| Description | Propagation trouve le chemin de moindre coût entre un point de départ et un point d’arrivée dans une grille de cases à coûts variés et pouvant comporter des obstacles. Cette application Excel est ce que l’on appelle un Pathfinder, c’est-à-dire un outil qui résout le problème mathématique du plus court chemin. Elle reprend le principe de l’algorithme de Dijkstra (1959). Cet algorithme est admissible et optimal : il garantit donc de trouver le meilleur chemin (ou l’un des meilleurs chemins si plusieurs sont strictement équivalents). Propagation peut également trouver le chemin le plus direct dans des grilles à coût nul (cellules vides) comportant des obstacles (cellules = -1). C’est la problématique classique du labyrinthe et de nombreux jeux vidéo. Ces Pathfinders ne traitent que des grilles composées de valeurs entières, qui doivent de surcroît rester relativement basses, car le coût des chemins a une forte incidence sur les performances. Ces valeurs peuvent être :
Deux modes de déplacement sont possibles :
Propagation est capable de traiter des grilles 2D, mais aussi des grilles 3D (dans ce cas, plusieurs grilles 2D sont empilées verticalement avec un interligne d’une ligne). Pour cela, il fait appel à deux modules de Pathfinding distincts mais très similaires. Ces modules sont extrêmement simples à réutiliser : peu de paramètres à ajuster et présence d’un code minimaliste illustrant comment appeler la fonction de Pathfinding. Les Pathfinders sont conçus de telle sorte qu’il est possible de stocker les grilles sur une feuille de calcul dédiée et d’exploiter les résultats sur une ou plusieurs autres feuilles de calcul. |
| Version | V2.2 | |
| Type | Freeware | |
| Auteur | Stéphane Fillon | |
| Post sur le forum | Afficher | |
| Ajouté le | 09.09.2020 | |
| Mis à jour le | 24.11.2025 | |
| Téléchargements | 586 | |
| Télécharger | propagation-v2-2.xlsm |
| Aperçu |  |