Propagation
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.
Propagation v2.2.png



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.

En espérant que vous serez nombreux à l'apprécier !
Auteur
Stéphane Fillon
Version
v2.2.1
  • 10x10fr.png
    10x10fr.png
    58.9 KB · Affichages: 366
  • Matrice 200x200 peripheral.png
    Matrice 200x200 peripheral.png
    383.4 KB · Affichages: 315

Dernières mises à jour

  1. Propagation v2.2

    Propagation trouve le chemin de moindre coût dans une grille de points pondérés. Propagation...
Retour