Discussion :

[gbegreg]

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 :

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 :

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

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

[Charly910]

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

[blonde]

Bravo, j'aime beaucoup !

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

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.