Propagation: Trouver le plus court chemin dans une matrice

Bonjour le forum,

J’ai le plaisir de vous présenter le tout dernier Propagation, sa version 3, voici les principales nouveautés :

• Ajout d’un nouveau module de Pathfinding capable de traiter les grilles contenant des Doubles (en fait l’algorithme de la v2.1 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.
• Ergonomie et finitions améliorées.
• Performances du Pathfinder 3D améliorées
• Code VBA rationnalisé et mieux commenté ; fin des anglicismes dans les noms de variables.

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é

Bonjour le forum,

Voici en avant-première la dernière version de mon Pathfinder. La mauvaise nouvelle c’est qu’il ne sait plus traiter que des entiers. Les bonnes nouvelles c’est que :

• Il traite maintenant une grille de 16384x16384 (mon ordinateur est doté de 32Go de RAM) avec points de départ et d’arrivée aux deux coins opposés en seulement 5 minutes et 6 secondes*
• Son code est devenu plus conventionnel, fini les variables à nom à rallonge et les rappels de type de données partout dans le code (type &, %) qui je le pensais amélioreraient la lisibilité du code mais c’était une erreur de ma part.
• Son code est abondamment commenté.
• Son code est plus court.

Pour info la plus grosse matrice adjacente que j’avais testé avec Propagation v2.1 était une 10000x10000 adja et elle avait réclamé plus de 21 heures de calcul ! Et avec un random à priori plus favorable.

Propagation v2.2 reste un algorithme admissible (càd qu’il fournit à coup sûr le meilleur chemin) ; il n’utilise aucune heuristique et aucune probabilité. Son gain de temps s’explique par le fait que j’ai pu supprimer tout tri et même toute recherche de minima si coûteuses en temps…

J’espère que vous serez curieux de l’essayer et avoir vos retours !

* Avec mon PC Icore5 de 6ème génération, en mode adjacent et avec un random =ENT(ALEA()*51) et hors temps de lecture de la feuille qui avoisine les 22 minutes.

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). 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.