Propagation trouve le
chemin de moindre coût dans une grille de points pondérés.
Propagation est ce que l’on appelle un
PathFinder, soit un outil répondant au
problème mathématique du plus court-chemin. Il reprend l’algorithme de
Dijkstra publié en 1959.
Ce PathFinder est
capable de traiter des grilles 2D et aussi des grilles tridimensionnelles (dans ce cas des grilles 2D sont empilées les unes au-dessus des autres dans la feuille de calcul avec un interligne d’une ligne).
Propagation gère deux modes de cheminement pour chacun de ces deux types de grille : «
Adjacent » (4 carrés partageant une arête avec un carré central en 2D ; 6 cubes partageant une face avec un cube central en 3D) et «
Périphérique » (8 carrés autour du carré central en 2D ou 26 cubes entourant un cube central en 3D).
Propagation est très performant mais au prix de ne savoir traiter que les grilles comportant des valeurs entières qui peuvent soit être :
- Négatives dans ce cas elles sont interprétées comme des obstacles infranchissables.
- Nulles dans ce cas le point est gratuit.
- Positives dans ce cas la valeur correspond au coût du point.
Ainsi une grille 1 000 x 1 000 en mode périphérique (plus long à calculer que le mode adjacent) avec départ et arrivée situés dans les deux coins opposés est résolue en environ 1 seconde (après un temps préalable de lecture de la feuille de calcul d’environ 5 secondes).
Le codes des modules de Pathfinding de Propagation (sfPathFinder2D et sfPathFinder3D) comportent chacun l’intégralité des codes nécessaires au Pathfinding plus une procédure minimaliste : « VotreCode » montrant comment utiliser les autres procédures. Ces modules
sont largement commentés (en français pour le module 2D et en anglais pour le 3D) et
vous pourrez les réutiliser avec facilité pour vos propres applications (des jeux par exemple). Quelques paramètres seront à ajuster pour ce réemploi, ils sont tous identifiés par la séquence de commentaire : ‘# ce qui facilitera leur recherche.
Mathématiquement on peut dire que l’algorithme de Propagation est :
- Admissible, ce qui signifie qu’il fournit à coup sûr le meilleur résultat (enfin un des meilleurs résultats s’il existe plusieurs alternatives strictement équivalentes).
- Très peu glouton, ce qui signifie que le temps de calcul par cellule n’augmente que très faiblement (et linéairement) au fur et à mesure que les dimensions de la grille s’accroissent.
En espérant que vous serez nombreux à l'apprécier !
