# Environnements de dveloppement > Delphi > Codes sources  tlcharger >  [FMX] Path Finder : rechercher le chemin le plus court pour aller d'un point  un autre

## gbegreg

Bonjour,

Je vous propose dans cet exemple une implmentation de lalgorithme 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 donns sur ce site (la 3D "ludique"), mais cet algorithme peut tre utilis dans de nombreux domaines dont le jeu vido  :;): 

L'objectif tant de trouver le chemin le plus court entre un point de dpart et un point d'arrive en vitant les ventuels obstacles.

Pour ce faire, imaginons une grille. Dfinissons dans cette grille une cellule de dpart "D" et une cellule d'arrive "A".
L'objectif va tre de dterminer le plus court chemin possible pour relier "D"  "A" en se dplaant cellule par cellule.

Les dplacements autoriss sont donc  droite,  gauche, en haut, en bas et les diagonales  partir d'une case donne. Pour dterminer la meilleure case voisine, nous allons attribuer des "cots"  chacune.
On va par exemple attribuer arbitrairement les cots suivants :
- dplacement sur une case adjacente a un cot de 10;
- dplacement sur une case en diagonal a un cot de 15 (c'est plus cher qu'un dplacement sur une case adjacente mais moins cher que deux dplacements adjacents conscutifs pour parvenir au mme dplacement final).

A partir de ce postulat, on va calculer pour les 8 cases voisines d'une case donne :
- le cot du dplacement de la case donne  cette case voisine (a sera donc 10 ou 15 en fonction de la position de la case voisine par rapport  la case donne);
- le cot du dplacement de la case voisine vers la case d'arrive (tout en respectant les rgles sur les cots de dplacement);
- un cot global qui est la somme des deux cots prcdents.

Pour illustrer cela, voici un petit schma :

Sur la grille, on est sur la case bleue "D". La case bleue "A" est la case d'arrive.
Les cases vertes sont les voisines de "D". Elles ont 3 nombres : 
- celui en haut  gauche de la case est le cot de dplacement depuis la case "D";
- celui en bas  droite est le cot estim des dplacements jusqu' la case "A";
- le nombre en orange au centre est le cot total (la somme des deux cots prcdents).

Dans cet exemple, on constate que les cases voisines au nord et nord est ont le cot global minimum par rapport aux autres voisines. L'algorithme A* va donc privilgier les pistes qui partent de ces cases.
En revanche, on constate galement que ces deux cases ont un cout global identique. Il va falloir dterminer un critre diffrenciant. Dans mon implmentation, il est possible de choisir le mode que l'on souhaite suivre. 
Par dfaut, il va examiner le cot estim des dplacements jusqu' l'arrive et privilgier la case qui aura le plus petit.
Dans l'exemple, l'algorithme choisira donc la case situe au nord est de la case "D". Et ainsi de suite jusqu' tomber sur la case d'arrive.

Je dis "par dfaut", car dans l'implmentation que j'ai faite, il est possible de choisir le mode. Le mode "deplacementsMinimum" est celui par dfaut qui en cas d'galit sur le cot global privilgiera la case avec le cot estim jusqu' l'arrive le plus petit, et le mode "coutMinimum" va privilgier le cot le plus petit.  

Voici une capture d'cran du programme exemple :

Le programme prend en compte la prsence 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 "Gnrer la grille" pour prise en compte).
Vous avez galement des checkbox qui permettent de jouer sur le traitement :
- si la case "Autoriser les dplacements en diagonal" est coche, alors les cases en diagonales seront prises en compte dans les voisines d'une case donne, sinon, seules les cases adjacentes le seront;
- si la case "Ne faire que la 1ere tape" est coche, alors seulement la premire tape de l'algorithme est effectue : 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 coche, alors la seconde tape de l'algorithme sera excute : parmi les cases parcourues, il va reconstituer le chemin depuis la case d'arrive vers la case dpart.
- si la case "Mode cot minimum" est coch, cela active le mode "coutMinimum".

Les cases de dpart et d'arrive sont places alatoirement.

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

----------


## Paul TOTH

haha a me rappelle un vieux test que j'avais fait un Javascript

http://www.execute.fr/isomap3.htm

----------


## ShaiLeTroll

Cela me fait penser  un entretien d'embauche pour travailler sur les logiciels de routage rseau fait en Lazarus, il y a quelques annes, en dehors de savoir qu'il fallait appliquer un Algorithme de Dijkstra que j'ai trs mal expliqu, l mes lacunes en mathmatiques ont t flagrantes.

Si j'ai du temps, je serais intress pour voir comment tu as mis cela en place.

----------


## Charly910

Bravo  gbegreg,
J'ai test sous D10.3.3 CE. a fonctionne bien sauf que la proprit ParentShowHint de RectangleModele n'est pas trouve.

Sinon pas de problme. Beau travail.

A+
Charly

----------


## blonde

Bravo, j'aime beaucoup !

----------


## gbegreg

> J'ai test sous D10.3.3 CE. a fonctionne bien sauf que la proprit ParentShowHint de RectangleModele n'est pas trouve.


Effectivement, j'ai fait le projet avec la version 10.4 Syndey et je n'ai pas test avec les versions antrieures de Delphi. Il se peut donc que de nouvelles proprits soient apparues depuis la version 10.3 Rio.

----------

