IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Codes sources à télécharger Delphi Discussion :

[FMX] Path Finder : rechercher le chemin le plus court pour aller d'un point à un autre


Sujet :

Codes sources à télécharger Delphi

  1. #1
    Membre expert

    Homme Profil pro
    Développeur informatique
    Inscrit en
    novembre 2006
    Messages
    578
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Deux Sèvres (Poitou Charente)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Finance

    Informations forums :
    Inscription : novembre 2006
    Messages : 578
    Points : 3 129
    Points
    3 129
    Billets dans le blog
    2
    Par défaut [FMX] Path Finder : rechercher le chemin le plus court pour aller d'un point à un autre
    Bonjour,

    Je vous propose dans cet exemple une implémentation de l’algorithme A* qui permet de trouver le chemin le plus court pour aller d'un point à un autre (https://fr.wikipedia.org/wiki/Algorithme_A*).
    Ça change des exemples habituels que j'ai donnés sur ce site (la 3D "ludique"), mais cet algorithme peut être utilisé dans de nombreux domaines dont le jeu vidéo

    L'objectif étant de trouver le chemin le plus court entre un point de départ et un point d'arrivée en évitant les éventuels obstacles.

    Pour ce faire, imaginons une grille. Définissons dans cette grille une cellule de départ "D" et une cellule d'arrivée "A".
    L'objectif va être de déterminer le plus court chemin possible pour relier "D" à "A" en se déplaçant cellule par cellule.

    Les déplacements autorisés sont donc à droite, à gauche, en haut, en bas et les diagonales à partir d'une case donnée. Pour déterminer la meilleure case voisine, nous allons attribuer des "coûts" à chacune.
    On va par exemple attribuer arbitrairement les coûts suivants :
    - déplacement sur une case adjacente a un coût de 10;
    - déplacement sur une case en diagonal a un coût de 15 (c'est plus cher qu'un déplacement sur une case adjacente mais moins cher que deux déplacements adjacents consécutifs pour parvenir au même déplacement final).

    A partir de ce postulat, on va calculer pour les 8 cases voisines d'une case donnée :
    - le coût du déplacement de la case donnée à cette case voisine (ça sera donc 10 ou 15 en fonction de la position de la case voisine par rapport à la case donnée);
    - le coût du déplacement de la case voisine vers la case d'arrivée (tout en respectant les règles sur les coûts de déplacement);
    - un coût global qui est la somme des deux coûts précédents.

    Pour illustrer cela, voici un petit schéma :
    Nom : explications.png
Affichages : 98
Taille : 16,4 Ko

    Sur la grille, on est sur la case bleue "D". La case bleue "A" est la case d'arrivée.
    Les cases vertes sont les voisines de "D". Elles ont 3 nombres :
    - celui en haut à gauche de la case est le coût de déplacement depuis la case "D";
    - celui en bas à droite est le coût estimé des déplacements jusqu'à la case "A";
    - le nombre en orange au centre est le coût total (la somme des deux coûts précédents).

    Dans cet exemple, on constate que les cases voisines au nord et nord est ont le coût global minimum par rapport aux autres voisines. L'algorithme A* va donc privilégier les pistes qui partent de ces cases.
    En revanche, on constate également que ces deux cases ont un cout global identique. Il va falloir déterminer un critère différenciant. Dans mon implémentation, il est possible de choisir le mode que l'on souhaite suivre.
    Par défaut, il va examiner le coût estimé des déplacements jusqu'à l'arrivée et privilégier la case qui aura le plus petit.
    Dans l'exemple, l'algorithme choisira donc la case située au nord est de la case "D". Et ainsi de suite jusqu'à tomber sur la case d'arrivée.

    Je dis "par défaut", car dans l'implémentation que j'ai faite, il est possible de choisir le mode. Le mode "deplacementsMinimum" est celui par défaut qui en cas d'égalité sur le coût global privilégiera la case avec le coût estimé jusqu'à l'arrivée le plus petit, et le mode "coutMinimum" va privilégier le coût le plus petit.

    Voici une capture d'écran du programme exemple :
    Nom : capture.png
Affichages : 98
Taille : 37,4 Ko

    Le programme prend en compte la présence de cases "obstacles" qui ne peuvent pas être franchies (les grises). Vous pouvez placer les cases obstacles en cliquant sur les cases blanches. Vous pouvez également modifier la taille de la grille (il faut alors cliquer sur le bouton "Générer la grille" pour prise en compte).
    Vous avez également des checkbox qui permettent de jouer sur le traitement :
    - si la case "Autoriser les déplacements en diagonal" est cochée, alors les cases en diagonales seront prises en compte dans les voisines d'une case donnée, sinon, seules les cases adjacentes le seront;
    - si la case "Ne faire que la 1ere étape" est cochée, alors seulement la première étape de l'algorithme est effectuée : les cases bleues seront en fait toutes les cases que l'algorithme aura parcourues pour trouver un chemin mais ça ne sera pas le chemin. Si cette case n'est pas cochée, alors la seconde étape de l'algorithme sera exécutée : parmi les cases parcourues, il va reconstituer le chemin depuis la case d'arrivée vers la case départ.
    - si la case "Mode coût minimum" est coché, cela active le mode "coutMinimum".

    Les cases de départ et d'arrivée sont placées aléatoirement.

    Enfin, cliquez sur le bouton "Recherche du chemin le plus court de D vers A" pour lancer le traitement.

    J'ai commenté le code (surtout l'unité uGBEPathFinder.pas) pour donner plus d'explications.

    Le ZIP du projet : PathFinder.zip
    Mon site - Mes tutoriels - GitHub - N'oubliez pas de consulter les FAQ Delphi et les cours et tutoriels Delphi

  2. #2
    Expert éminent sénior
    Avatar de Paul TOTH
    Homme Profil pro
    Freelance
    Inscrit en
    novembre 2002
    Messages
    7 911
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Freelance
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : novembre 2002
    Messages : 7 911
    Points : 25 677
    Points
    25 677
    Par défaut
    haha ça me rappelle un vieux test que j'avais fait un Javascript

    http://www.execute.fr/isomap3.htm
    Nom : isomap.png
Affichages : 95
Taille : 29,2 Ko
    Developpez.com: Mes articles, forum FlashPascal
    Entreprise: Execute SARL
    Le Store Excute Store

  3. #3
    Expert éminent sénior
    Avatar de ShaiLeTroll
    Homme Profil pro
    Développeur C++\Delphi
    Inscrit en
    juillet 2006
    Messages
    11 903
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Développeur C++\Delphi
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : juillet 2006
    Messages : 11 903
    Points : 20 825
    Points
    20 825
    Par défaut
    Cela me fait penser à un entretien d'embauche pour travailler sur les logiciels de routage réseau fait en Lazarus, il y a quelques années, en dehors de savoir qu'il fallait appliquer un Algorithme de Dijkstra que j'ai très mal expliqué, là mes lacunes en mathématiques ont été flagrantes.

    Si j'ai du temps, je serais intéressé pour voir comment tu as mis cela en place.
    Aide via F1 - FAQ - Guide du développeur Delphi devant un problème - Pensez-y !
    Attention Troll Méchant !
    "Quand un homme a faim, mieux vaut lui apprendre à pêcher que de lui donner un poisson" Confucius
    Mieux vaut se taire et paraître idiot, Que l'ouvrir et de le confirmer !
    L'ignorance n'excuse pas la médiocrité !

    L'expérience, c'est le nom que chacun donne à ses erreurs. (Oscar Wilde)
    Il faut avoir le courage de se tromper et d'apprendre de ses erreurs

  4. #4
    Membre émérite
    Avatar de Charly910
    Homme Profil pro
    Ingénieur TP
    Inscrit en
    décembre 2006
    Messages
    1 826
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur TP
    Secteur : Bâtiment Travaux Publics

    Informations forums :
    Inscription : décembre 2006
    Messages : 1 826
    Points : 2 654
    Points
    2 654
    Par défaut
    Bravo gbegreg,
    J'ai testé sous D10.3.3 CE. ça fonctionne bien sauf que la propriété ParentShowHint de RectangleModele n'est pas trouvée.

    Sinon pas de problème. Beau travail.

    A+
    Charly

  5. #5
    Membre averti Avatar de blonde
    Femme Profil pro
    Développeur Embarcadero mutliplateforme
    Inscrit en
    septembre 2003
    Messages
    186
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur Embarcadero mutliplateforme

    Informations forums :
    Inscription : septembre 2003
    Messages : 186
    Points : 316
    Points
    316
    Par défaut
    Bravo, j'aime beaucoup !

  6. #6
    Membre expert

    Homme Profil pro
    Développeur informatique
    Inscrit en
    novembre 2006
    Messages
    578
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Deux Sèvres (Poitou Charente)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Finance

    Informations forums :
    Inscription : novembre 2006
    Messages : 578
    Points : 3 129
    Points
    3 129
    Billets dans le blog
    2
    Par défaut
    Citation Envoyé par Charly910 Voir le message
    J'ai testé sous D10.3.3 CE. ça fonctionne bien sauf que la propriété ParentShowHint de RectangleModele n'est pas trouvée.
    Effectivement, j'ai fait le projet avec la version 10.4 Syndey et je n'ai pas testé avec les versions antérieures de Delphi. Il se peut donc que de nouvelles propriétés soient apparues depuis la version 10.3 Rio.
    Mon site - Mes tutoriels - GitHub - N'oubliez pas de consulter les FAQ Delphi et les cours et tutoriels Delphi

Discussions similaires

  1. Recherche de chemin le plus court
    Par Batou69 dans le forum Algorithmes et structures de données
    Réponses: 38
    Dernier message: 23/06/2011, 11h11
  2. Chemin le plus court pour indexer un texte
    Par vallica dans le forum Langage
    Réponses: 2
    Dernier message: 23/04/2009, 21h29
  3. recherche du chemin le plus court entre 2 points
    Par ram-0000 dans le forum Boost
    Réponses: 4
    Dernier message: 31/03/2009, 01h22
  4. 2D C++ : Améliorer Recherche chemin le plus court
    Par Julien_C++ dans le forum Développement 2D, 3D et Jeux
    Réponses: 1
    Dernier message: 04/11/2006, 14h58
  5. algorithme de Ford (recherche chemin le plus court)
    Par abstraite dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 19/05/2005, 11h39

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo