Le Pathfinding ou la recherche de chemin par VBA

Hello, Hello ou Hellsoir,

En regardant le Pause Proccess 22 et en bossant sur mon prochain jeu, j'ai eu un assemblement d'idées qui pourrait intéresser :

Le Pathtfinding en VBA. 8)

pathfinding

En Français, c'est un process de calculs de recherche de chemin d'un point A à un point B, qui s'applique à un grand nombre d'appli. : jeux, navigation GPS, gestion de trajets logistique.... Qui date d'après ce que j'ai pu en lire de 1959 et 1968, y'avait même pas encore le minitel à l'époque.

Après quelques courtes recherches, (oui il y'a pas mal de doc ), ça marche plutôt bien dans Excel, pas de quoi faire un Wargame temps réel à grande échelle, mais y'a de la marge, ça ouvre des possibilités super cool. 8)


Je ne vais pas faire un cours, car je débute, mais en gros il y'a 2 grands type d'algo. :

L'algorithme de Dijkstra, qui permet de déterminer un chemin optimal, mais long à calculer

L'algorithme A*, qui est plus rapide à calculer, mais aussi plus souvent moins optimale

Apparemment, l'enjeu dans ce genre de problématique qui va se poser pour une reprise dans une appli., va être le choix entre le besoin de la meilleure solution et le temps de calculs/puissance demandé.

Et comme pour le calcul de combinaisons de lettrage, plus la taille de la grille est grande, plus c'est long.


Je n'ai pas vu de cours en français sur la programmation du pathfinding en VBA et en Français, mais ces 3 cours m'ont semblé intéressant dans l'explication générale des algo.

Cours sur l'algorithme A*, par Greg sur le site benicourt.com :

pathfinding a

Cours sur l'algorithme Dijkstra, par clemherreman sur le site openclassrooms.com:

151279

8) Mais le plus important, reste encore une démo concrète expliquée (en anglais) et j'en ai trouvé 2 sympas chez get-digital-help.com par Oscar, dont le site en 2 liens, montre de jolies gif de démo de ce que donnera le code utilisant l'algo. A*. Cool.

1er Démo :

http://www.get-digital-help.com/2014/05/27/finding-the-shortest-path-a-pathfinding/

find shortest path1 gif pagespeed ce xy0a5hlt9x

2e Démo :

http://www.get-digital-help.com/2014/06/16/a-quicker-a-pathfinding-algorithm/

optimize path test5 gif pagespeed ce ec5fvidepc

Et voilà pour mon petit partage, si ça vous ouvre des idées, en tout cas moi je pense l'intégrer dans mon prochain jeu.

Et le Pause Process 22 : https://www.youtube.com/watch?v=DlgnB4UKU74

hqdefault

Bonne recherche de chemin

Bonjour waard,

Ton sujet m'intéresse de trop. C'est LouReeD qui vient de me faire parvenir le lien. Je viens en effet de diffuser une application qui à première vue ressemblerait à l'algorithme de Dijkstra je n'ai pas encore bien lu tout ton sujet. Par contre sur ton Gif animé pour la première démo il semblerait que l'algorithme de Dijkstra parvienne au résultat en calculant moins de cellules que le mien. Je reviendrais certainement à toi une fois que j'aurais bien potassé tout ça car ce sujet me passionne et m'a tenu en haleine pendant tout le mois de septembre

Cordialement,

J'arrive un peu tardivement sur le sujet pour joindre un petit fichier, j'avais fait du pathfinding par VBA également, si je ne me trompe pas il utilisait l'algorithme de Dijkstra et utilise un module de classe, ça servira peut-être...

66pathfinder.zip (341.78 Ko)

Le chemin est éditable dans la zone encadrée, il faudra un point de départ a, et un point d'arrivée b les passages bloqués sont représentés par des croix qui vont noircir la case avec mfc, on peut choisir de mettre un délai pour voir l'algorithme calculer case par case.

Bonsoir,

j'aime bien votre proposition, bien que je pense rester sur celle de h2so4.
Dans le principe c'est à peu près le même, si ce n'est que lui ne met pas de coefficient sur la valeur des cellules, juste un incrément de distance par rapport au point de départ, comme cela, le chemin le plus court du point de départ au point d'arrivée est trouvé en faisant le chemin inverse du plus grand vers le plus petit :

sans titre

@ bientôt

LouReeD

Oh je vois, en effet ça y ressemble beaucoup, il ne se déplace pas en diagonale, c'est bien la seule différence vraiment visible.

On pourrait après pousser encore plus loin en affectant des bonus ou malus aux cases, comme si on bougeait sur une route principale ou un marais, mais la base est là

Bonne soirée!

J'ai adapté votre code dans ce sens, car c'était pour l'adaptation d'un jeu de plateau où les déplacements en diagonales ne sont pas possibles.

@ bientôt

LouReeD

Bonjour à tous,

Un algorithme de Pathfindage de plus...Propagation béta

Gère 2 modes de diffusion (périphérique ou adjacent) et les systèmes tridimensionnels.

Plus grosse matrice soumise 3500x3500 adja en un peu moins de 16H50. Dans le coup ?

Ci-attaché document simplifié déroulé résolution matrice 5x5 en périphérique en 21 appels Process (pdf)

Bonsoir,

sur tous les fronts Stéphane1972 !

@ bientôt

LouReeD

Bonjour LouReeD, content de te recroiser. Non toujours un peu sur le même front au contraire et je me suis intéressé pas plus tard que tout-à-l'heure à ton Mosaique-Maker. Une image n'est-elle pas autre chose qu'une matrice 2D ? Et je suis tombé sur une limitation à 833 colonnes par 563 lignes.

Je tombe à l'instant sur ton Post et n'ai pas encore bien chercher à contourner ce problème dont pour l'instant je n'ai pas encore vu l'origine. Est-ce une limitation volontaire face à un algorithme qui te semblerait prendre trop de temps pour une grosse image ? Perso rien ne me presse le calcul à suivre prendra certainement beaucoup plus de temps !

Stéphane

Bonsoir

A voir s'il n'y a pas une limitation au niveau des USF... Faut que je me replonge dans le code, mais de mémoire je ne me rappelle pas d'une limite come indiquée. Au pire si j'en avais mis une elle aurait été "conforme" à une resolution standard du style 800 x 600, ou 1024 x 768 bref vous avez compris.

@ bientôt

LouReeD

Rechercher des sujets similaires à "pathfinding recherche chemin vba"