Pathfinder Studio, le successeur de Propagation

Bonjour à tous,

J’ai le plaisir de vous présenter le tout dernier Propagation qui a changé de nom pour devenir : Pathfinder Studio. Voici un petit aperçu de ce qui a changé

• Ajout d’un nouveau module de Pathfinding capable de traiter les grilles contenant des Doubles (en fait l’algorithme de la v2.1 de Propagation, amélioré d’où son nom de code 211).
• Ajout du mode de propagation : Périphérique Sprite qui m’a été inspiré par le A* d’Ausecour très didactique. Je tiens à le remercier ici de l’avoir mis en ligne. C’est sa formule retravaillée et codée en AND plutôt qu’en OR que j’ai réutilisée, vous reconnaitrez le Gosub Calcul, un petit clin d’œil.

• Code interruptible à tout moment avec la touche Echap et indicateur de progression dans la barre d’état.
• Random paramétrable depuis l’Userform.
• Relecture de la feuille uniquement si la grille a été modifiée.
• Performances améliorées.
• Ergonomie et finitions très améliorées.
• Code VBA rationalisé et mieux commenté (mais en anglais).
• Application redevenue multilingue (allemand, anglais, espagnol, français, italien et portugais).

Bonsoir,

j'ai testé et je dois dire que cela fonctionne bien.

J'ai sur ma machine un code similaire fourni par h2so4, je vous l'ai fourni pour vous amuser à faire quelque tests de rapidité de l'un par rapport à l'autre. Attention ! C'est juste pour voir, mais si j'ai bien compris le votre il y a des accès "feuilles Excel" pour mettre en mémoire des données de parcours, donc cela devrait le ralentir quelque peu, non ?

Une fois de plus bienvenu dans le "petit" monde des contributeurs !

@ bientôt

LouReeD

Bonjour LouReeD et merci beaucoup pour tes retours. Je commence seulement à chercher à comprendre (j'étais trop absorbé par la finalisation de la version 2 de Propagation) le code de Hero Quest que tu m'as envoyé en MP et vu mon petit niveau en VBA cela risque de me prendre un peu de temps. Ton jeu me semble très prometteur je suis impatient de l'essayer, bravo pour le soin apporté à la présentation ! Et merci de ne m'avoir envoyé que le code qui m'intéresse le plus. Une fois que j'aurai assimilé le code de h2so4 je mènerai un banc d'essai Chrono sur des plateaux de grandes dimensions.

Effectivement le fait d'utiliser des feuilles Excel pour stocker des données n'est peut-être pas le plus judicieux en termes de temps de calcul. Si le code de h2so4 est significativement plus rapide j'essaierai de trouver un autre procédé plutôt que d'utiliser ces feuilles.

A bientôt pour un compte-rendu du comparatif

Bonsoir,

aviez vous vu ce sujet ?

@ bientôt

LouReeD

Merci beaucoup pour ce nouveau Post. Non je ne connaissais pas ce sujet très riche. Je commence à peine à me familiariser avec le code que tu m'as envoyé et avec ce nouveau sujet je sens que je n'ai pas fini de m'amuser… Merci aussi de m'avoir sensibilisé au problème du temps des accès feuille je pense qu'il ne devrait pas être trop difficile de procéder autrement; à voir les résultats en termes de temps de calcul.

Donc très reconnaissant à vous monsieur LouReeD

Bonsoir,

Alors ces temps de calculs, c'en est où ?

@ bientôt

LouReeD

Bonsoir,

Ca avance modestement disons que la matrice que j'avais prise pour exemple et qui était solvée en 8 minutes tout rond l'est maintenant en 24,31 secondes !

Tu sais que tu m'auras donné beaucoup de boulot avec ton foutu lien sur le Post précédent ! Cela aura pour avantage que je pourrai fournir une page d'aide plus documentée mais j'ambitionne maintenant de programmer un estimateur de durée réaliste.

Propagation v2.1 te devras beaucoup

Post supprimé

Retour d'expérience : Optimiser Dijkstra en VBA (Gestion de grilles 3D et performances)

Bonjour à tous,

Après pas mal de travail et d'optimisations, je considère mon projet de Pathfinder comme achevé. En poussant l'outil jusqu'à gérer des grilles 3D de 1 000 au cube (soit 1 milliard de cellules !) sous Excel, je me suis heurté aux limites de performance du VBA.

Pour relever le défi, j'ai implémenté deux variantes distinctes de l'algorithme de Dijkstra. J'avais envie de partager ici les choix techniques et les astuces qui m'ont permis de faire tourner tout cela en arrière-plan sans exploser les temps de calcul.

2. L’algorithme 211 (Traitement par lots avec mCCm, NA et LPA)

Ma seconde approche est un Dijkstra plus conventionnel, adapté au type de données Double et optimisé par des astuces de bas niveau, idéal lorsque le nombre de valeurs de coûts distinctes est limité :

• Le traitement groupé : Plutôt que d'étudier point après point, j'intègre dans une variable mCCm (Même Coût Cumulé Minimal) tous les points partageant le même coût minimal en fin de boucle.
• Les sous-boucles de voisinage :
1. Je calcule le coût des voisins immédiats et les trie par ordre décroissant dans un tableau de taille limitée NA (Nouvellement Atteintes) via un tri de Shell.
2. Si aucun nouveau voisin n'est trouvé, je zappe complètement les étapes suivantes pour gagner du temps.
3. Sinon, j'injecte et fusionne ces points dans un tableau principal LPA (Liste des Points Atteints) maintenu en ordre décroissant.
• La fuite rapide (Exit For) : Je parcours LPA en partant de la fin et je m'arrête dès que les nouveaux voisins ne rivalisent plus avec les premiers éléments, m'évitant de balayer toute l'étendue du tableau.
• Les inconvénients de cet algorithme : Les temps de calcul sont rédhibitoires sur les très grosses grilles ( > 1000 x 1000) et incapable de solutionner efficacement les grilles en 3D

1. L’algorithme 222 (Basé sur un tableau de coûts cumulés)

Pour la seconde approche, j'ai structuré mes données sous la forme d'un tableau de seaux de coûts (que j'ai découvert plus tard correspondre à l'algorithme de Dial de 1969).

• Le principe : Les coûts étant contraints à des entiers (Integer 32 767), je stocke les points dans une variable tableau CCs indexée directement par leur coût cumulé.
• L'optimisation : Au lieu de faire un tri lourd à chaque étape, l'algorithme fait simplement « défiler » les indices de ce tableau vers l'avant jusqu'au prochain seau non vide. L'insertion d'un voisin se fait instantanément, ce qui élimine les surcoûts d'une file de priorité classique en VBA.
• Les limites et inconvénients : Cet algorithme se heurte vite à la limite de mémoire allouée pour un tableau de données de 8 octets. Cela limite le coût maximal du chemin le plus coûteux à environ 134 * 10 ^ 6 (= (2147483647 / 8) / 2). / 2 car la taille du tableau peut être 2 fois supérieure au coût du chemin.

Les performances sont fonction du coût du chemin, de hautes valeurs de random augmentent les temps de calcul.

• Les avantages : cet algorithme est très rapide, permet d’affronter des grilles de très grandes dimensions sans perte de performance significative et est efficace en 3D.

Pour le moment la dernière version de mon pathfinder est disponible sur le premier Post de ce fil.

Bon code à vous !

Bonjour Stéphane1972 !

Deux choses : Lors de l'utilisation du USF en augmentant la taille de la matrice, les colonnes au-dessus de 10, n'ont pas la même largeur !
la deuxième : un très grand merci pour la référence de mon Pseudo ! Cela me fait plaisir ! Si je vous dis que je ne pense pas que ce soit nécessaire vous me répondrez que si ! Alors j'en prend la joie de le voir ! Merci encore.

Bon je ne comprend pas tout dans le code. Sinon comment fait-on pour créer des obstacle sur le chemin afin de forcer un détour ? J'ai réussi en mettant des 999 dans certaines cellules... Peut-être n'ai-je pas vu "l'option".

Bon et beau travail et cette distribution Free !

@ bientôt

LouReeD

Bonjour LouReed,

Je suis heureux que nos chemins se recroisent !

Oui ça Bugge un peu sur la largeur des colonnes je vais devoir me repencher un peu sur la procédure NewMatrix pour l’instant il y a quelque chose qui m’échappe…

C’est vous que je remercie encore pour les raisons que j’ai évoqué dans la page d’aide.

Pour créer des obstacles il faut rentrer un entier négatif par exemple -1

Sinon la page d’aide n’est pas à jour le mode de calcul en arrivée flottante a été supprimé et il faut impérativement spécifier un point d’arrivée sinon bug.

Bonne journée et @+

Stéphane

Juste un petit ColumnWidth avec une valeur de 20 et un RowHeight avec une valeur de 13.

Mais il est vrai qu'il y a sur ma machine un petit temps avant de voir les cellules se mettre en place... Pourtant au niveau de la feuille il n'y a que le masquage de colonnes et lignes non ?

@ bientôt

LouReeD

Oui la procédure NewMatrix est assez décevante je vais essayer de revoir ma copie ! Avez-vous testé de grosses matrices et si oui que pensez-vous des performances du Pathfinder à proprement parler ?

@+

Bonsoir,

je n'ai pas fait de gros tests encore... désolé.

Je pourrais essayer de la comparer au code h2so4

Je vous tiens au courant, restez sur la fréquence !

@ bientôt

LouReeD

Bonsoir et merci d'avance,

Je reste sur la fréquence

Bonjour,

Je tiens d’abord à remercier (bien tardivement…) Sébastien pour le gros travail qu’il a effectué pour l’amélioration de la mise à jour de ma description longue.

Obligé de relativiser sur les performances de mon Pathfinder qui ne sont bonnes qu’à condition que les valeurs dans la grille soient basses (ordre d’idée : étagées de 0 à 250) (Note du 19 octobre 2026: C'est maintenant corrigé on peut maintenant utiliser tout ce que permet un Integer (<=32767). L’intérêt de ce Pathfinder reste :

• D’être rapide si l’on respecte à peu près cette condition.
• De ne pas « bloquer » quand la taille de la grille augmente.
• De savoir résoudre efficacement les systèmes 3D.

Dans les précédentes versions de Propagation on recherchait par une boucle la case présentant le Coût Cumulé minimal et l’on pouvait alors calculer le coût cumulé de ses cases voisines et établir le lien de parenté. Le nombre de cases grappillées augmentant vite cette boucle se retrouvait en inflation plus ou moins rapide selon le mode Adjacent/Périphérique et 2D/3D. Ceci a pour effet de limiter la taille des grilles calculables dans un temps raisonnable.

Avec la version actuellement en ligne on ne recherche plus de coût cumulé minimal mais on enregistre ces coûts en tant qu’index dans une variable tableau de type liste de points :

Private Type Point2D
    X As Integer
    Y As Integer
End Type

Private Type lp     ' lp comme : Liste de Points
    p2d() As Point2D
    cp As Boolean    ' cp comme : Contient des Points
End Type

Après calcul du voisinage des nœuds courants on progresse dans le coût cumulé jusqu’à atteindre un booléen cp à True et on peut alors entamer une nouvelle itération de la boucle principale avec le nouveau coût cumulé incrémenté. Plus aucune boucle en inflation dans ce système donc un temps de calcul par cellule relativement stable quelles-que soient les dimensions de la grille.

Le fichier suivant (qui ne gère plus les obstacles et que les Bytes) offre la possibilité de tester des grilles de dimensions nettement supérieures à celles prises en charge par une feuille Excel classique.

Bonjour le forum,

Propagation est mort, vive Pathfinder Studio ! Vous le trouverez dans le premier Post de ce fil.Il n'attends plus que vos téléchargements...

Bonjour,

téléchargé et testé ! Super travail !
bon j'ai eu peur car en changeant la dimension de la grille j'ai eu une fenêtre de choix d'impression, et cela finissait avec une erreur...
J'ai fini par choisir PDF et cela a arrangé le soucis.

Ensuite, en fonction de la taille de la grille et de la taille des valeurs dans les cellules, une adaptation de la largeur et hauteur des cellules serait le top...

J'ai essayé de double cliquer sur une cellule après avoir sélectionner le textbox "case de départ", mais son adresse ne s'est pas inscrite automatiquement.
Je ne sais si c'est possible, j'en suis arrivé là car j'ai masqué les entête de ligne et de colonnes pour un gain de place sur mon écran.

J'avoue avoir du mal avec la 3D, Z >1, mais on y arrive ! Le top serait de créer une représentation type "rubis cube" pour donner la solution visuellement !
Prochain défi ! ?

Pour mon projet je pense toujours rester sur ma version de chemin par calcul de distance entre la cellule de départ et d'arrivée, mais en soit vu le retard qu'il prend cela n'a pas trop d'importance !

Petit dernière chose : le choix de la langue à l'ouverture du fichier : c'est très bien ! Dommage qu'il n'en soit pas de même pour les commentaires du code !
Il ne me reste plus qu'à analyser le code tout en travaillant mon anglais !

Bonne fin de semaine à vous.

@ bientôt

LouReeD

Bonjour LouReeD,

Merci beaucoup pour votre retour et d’avoir testé mon app. Je vais essayer de vous répondre point par point:

bon j'ai eu peur car en changeant la dimension de la grille j'ai eu une fenêtre de choix d'impression, et cela finissait avec une erreur...

Très mystérieux… le redimensionnement de la grille est assurée par la procédure ButtonNewGrid_Click() et en ce qui concerne l’impression de la feuille elle prévoit seulement de modifier le PageSetup.RightHeader pour y indiquer les dimensions de la grille et aussi de supprimer les sauts de pages existants et d’en ajouter de nouveaux dans le cas des grilles 3D. Peut-être auriez-vous ailleurs (dans votre classeur de macros personnelles ou dans un add-on) une procédure sensible à ces évènements-là ? J’ai testé Pathfinder Studio en long en large et en travers sur 3 PC différents et je n’ai jamais été confronté à ce genre de désagrément.

Ensuite, en fonction de la taille de la grille et de la taille des valeurs dans les cellules, une adaptation de la largeur et hauteur des cellules serait le top...

Actuellement la largeur des colonnes et de 4 et la fonte en taille 7. Cela permet d’afficher les nombres à 5 chiffres (limite pour l’algorithme de Dial qui n’accepte que des Integers) correctement, mais il est vrai pas les nombres à 15 chiffres générés par exemple par ALEA() quand l’algorithme choisi est celui de Dijkstra. Mais si l’on veut afficher les 15 chiffres dans ces cellules carrées la présentation n’est pas top non plus (textes minuscules à l’échelle des cellules). J’ai fait le choix d’utiliser de toutes petites cellules pour permettre d’afficher de grandes grilles en dézoomant.

J'ai essayé de double cliquer sur une cellule après avoir sélectionner le textbox "case de départ", mais son adresse ne s'est pas inscrite automatiquement.

Je ne sais si c'est possible, j'en suis arrivé là car j'ai masqué les entête de ligne et de colonnes pour un gain de place sur mon écran.

Le fait d’avoir masqué les en-têtes n’y est pour rien. Le TextBox a été prévu pour pouvoir saisir manuellement l’adresse voulue. Par contre il y a moyen de compléter ce champ automatiquement soit en cliquant sur une cellule puis en pressant la touche s (Start) ou e (End) ou en cliquant sur les boutons ActiveCell de l’UserForm. Il y a moyen aussi depuis l’UserForm de cliquer sur un des boutons Random, ou encore cliquer sur : Au coins opposés.

J'avoue avoir du mal avec la 3D, Z >1, mais on y arrive ! Le top serait de créer une représentation type "rubis cube" pour donner la solution visuellement !

Je proposai ce genre de fonctionnalité dans les précédentes versions sous forme de création d’un fichier obj, mais je l’ai abandonné ce fichier devenant rapidement volumineux pour les grandes grilles. Maintenant on peut suivre assez facilement le chemin sur les différentes grilles 2D restituant ce cube au moyen du raccourci clavier p (Sélectionner le chemin) puis en faisant défiler les cellules en appuyant sur la touche Entrée. Ou encore en utilisant les raccourcis claviers Ctrl + PgDn/PgUp pour translater la cellule active d’une unité en Z. Vous qui connaissez Excel bien mieux que moi vous sauriez peut-être comment générer ce cube tout en restant dans Excel ?

Pour mon projet je pense toujours rester sur ma version de chemin par calcul de distance entre la cellule de départ et d'arrivée, mais en soit vu le retard qu'il prend cela n'a pas trop d'importance !

Et vous avez raison l’algorithme que vous avez en main est (presque) aussi performant que celui de Dial pour les grilles à coût nul et est mieux adapté à votre application. Utiliser le mien vous imposerait de dupliquer et modifier légèrement votre plateau. Bref vous n’y gagneriez rien !

Petit dernière chose : le choix de la langue à l'ouverture du fichier : c'est très bien ! Dommage qu'il n'en soit pas de même pour les commentaires du code !

Si vous avez une solution technique à me proposer pour traduire également les commentaires des modules je suis preneur. Mon Pathfinder étant maintenant bien finalisé je vais maintenant m’atteler à sa promotion (Youtube, Reddit…) je cherche à m’attirer un public anglophone car sa moyenne de 9 téléchargements mensuels ne me satisfait guère. J’ai tellement travaillé sur cette application…

Bonne semaine à vous itou et @ bientôt !

Bonsoir,

il va s'en dire que j'utilise tout ce que j'achète ou ce que je télécharge sans lire les notices !

Donc je m'excuse pour mes questions hors sujet ! Mes connaissances en VBA ne me permettent pas de créer un objet 3D résultat d'un chemin en 3D, désolé.

Je n'ai pas d'application de traduction des aides sous VBA non plus, s'ils m'intéressent alors je les traduirais à la demande...

Pour ce qui est du jeu HeroQuest, je ne peux donner une date de "sortie", en ce moment je m'éloigne de plus en plus de l'ordinateur/Excel/VBA. Pourtant l'application "La Fabrique" a bien avancée avec pas mal de paramètres, maos je me noie dans tout cela, mais ce n'est pas le sujet d'ici.

Demande de création d'une grille de 10 x10 x 3, message "Windows" m'indiquant que l'ordi attend la connexion à l'imprimante :

et ensuite j'ai l'erreur :

Alors oui ce doit être un problème de mon côté au niveau de mon imprimante réseau sans fil.
dès que je passe sous Excel en imprimante "PDF", alors ça fonctionne. Avec vitesse en plus malgré la taille de certaines grilles de tests ! Bravo !

L'explication du "p" mérite une précision sinon ce dernier ne marche pas : bascule entre le chemin et la cellule active mais cette dernière doit être sur le chemin.
Le USF ne s'efface pas lors du changement de feuille, du coup un clic malencontreux engendre une erreur si l'on se trouve sur la feuille explication.

Bonne chance pour votre distribution à l'international ! Vous pouvez commencer par ceci, la version anglaise d'Excel-pratique.com

@ bientôt

LouReeD