Propagation: Trouver le plus court chemin dans une matrice
Propagation trouve le chemin le moins résistif entre un point de départ et un point d'arrivée dans une matrice résistive
Cette application est le résultat d'un défi logique que je m'étais donné après avoir joué à Civilization II à savoir reproduire l'intelligence artificielle qui permettait aux unités de toujours emprunter le chemin le plus judicieux
L'algorithme court (Le calcul n'implique que trois procédures, une quatrième est nécessaire pour générer une nouvelle matrice) de cette application pourra donc peut-être intéresser un développeur de jeux. Le code de cette application est abondamment commenté et j'y ai laissé dans la procédure : "NouveauCalcul" en commentaire quelques lignes de codes qui permettront de comprendre à ceux qui le désireront comment Propagation arrive au résultat
Je n'ai pour le moment eu que très peu de téléchargements, je serais très intéressé par vos éventuels retours et de connaitre en quoi consistent vos résistances (durée pour une orientation routière, résistance électrique en électricité, coût en points de déplacement dans un jeu, ...) et quelle application pratique vous imaginez pour cet algorithme
Si vous avez connaissance d'un autre algorithme capable de traiter cette problématique (trouver le chemin le moins résistif dans une matrice) je vous serais très reconnaissant de me le procurer
Merci à tous ceux qui me fourniront des retours
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
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 basée sur ce qu'on peut trouver en haut de cet article WikiPédia
Propagation v2.1 te devras beaucoup
Bonjour ,
Ce Post est en lien avec un autre déposé sur maths-forum.com. Il est destiné principalement aux matheux venant de ce forum. Il contient les fichiers qu'il est impossible de déposer dans les Posts de maths-forum.
En plus de ces fichiers je vais tenter d'expliquer un peu mieux le principe de Propagation:
La matrice Excel est convertie en Cubes. Une périphérie isolante (Cubes.Matrix = -1) s'ajoute aux Cubes de la matrice. Ainsi pour une matrice NbX x Nby x NbZ cellules il y a (NbX+2) x (NbY+2) x (NbZ+2) Cubes
Les Cubes sont des Arrays à trois dimensions : Cube(X, Y, Z) et ont trois propriétés définies par un type personnalisé :
- .Matrix correspond aux valeurs de résistance telles qu'on les retrouve dans la feuille : "Matrice"
- .Cumulation est la somme résistive du Cube par rapport au point de départ. Une fois que celui-ci a été calculé une première fois on ne revient plus dessus. C'est ce qui permet à l'algorithme d'avancer.
- .Path stocke les adresses du chemin et ne sert à rien d'autre qu'à permettre à Excel de tracer le chemin en vert, c'est pour cela que je ne l'ai même pas présenté dans le logigramme
L'Array : "UnderStudy" comporte tous les Cubes en cours d'étude. Le premier élément confié à UnderStudy est le point de départ et il est solutionné niveau Cumulation. Viendront s'y ajouter ensuite et en premier lieu les Cubes immédiatement adjacents ou périphériques à ce point. Ces derniers sont dès lors solutionnés niveau Cumulation.
Une fois tous les Cubes autour du point de départ calculés celui-ci est exclu de UnderStudy. Le Cube appartenant à UnderStudy et de résistance minimale au niveau Cumulation devient alors le centre du même calcul que pour le point de départ.
Le calcul prend fin lorsque le Cube d'arrivée a été atteint. S'il ne l'est pas c'est qu'il ne peut pas l'être et le calcul prend fin une fois tous les Cubes de la matrice calculables calculés, le résultat est alors : "Sans solution"
Merci à tous ceux qui auront pris la peine de lire ce Post et un remerciement beaucoup plus appuyé à celui qui saura ou m'aidera à trouver l'équation juste pour l'estimateur de durées. Il figurera avec LouReeD de ce forum dans les remerciements de cette app !