Bonjour à tous,

Je ne sais pas bien où poster cet exercice. A défaut je le fais ici, désolé si je me trompe de section.

J'ai fait en PHP l'algorithme A* en suivant les bons conseils de Patrick Lester

Vous allez surement me dire que le faire en PHP n'a pas bcp d'intérêt.
Je répondrais à cela "et pourquoi pas !"
J'ajouterai que le code PHP en lui même me semble assez simple à porter pour d'autre langage (ce n'est que mon avis).
Et puis on peut faire tellement de chose en PHP, tout est permis

C'est la première fois que je poste un code ici, aussi je fais appelle à votre indulgence, ne pas taper svp si vous trouvez çà pas terrible, j'ai fais aussi bien que j'ai pu.

Quelques mots sur le code
Pour une raison de clarté j'ai répartie le code sur 3 fichiers :
- Le premier est le "Main" (très court) qui symbolise l'initialisation et l'appel de l'algorithme - Les deux boucles - (Main_astar.php)
- Le second est l'algorithme Astar. Il est indépendant en lui même (Algo_astar.php)
- Le 3eme fichier est le rendu graphique du chemin sous la forme d'une simple grille (Visuel_astar.php)

Il y a 2 Classes, l'une pour l'algorithme (class Astar) et une autre le visuel (class RenduVisuel).

Les 3 fichiers sont abondamment commentés (Règle maison d'IBM) et aéré afin de permettre une compréhension du code et de l'algorithme.
Le code en lui même repose sur des instructions simples.

Installation
- Télécharger le zip à l'adresse suivante :
http://www.dedikam.com/telechargement.p ... 1eed174088
- Copier le dossier à la racine de votre dossier www local sous Wamp ou EasyPHP ou sur votre Serveur HTTP
- En local, taper dans votre navigateur l'adresse (après avoir exécuté Wamp ou EasyPHP) :
http://127.0.0.1/astar/Main_astar.php

Il ne reste plus qu'à rafraichir la page (F5) Autant de fois que vous le souhaitez.

Note:
Par défaut le départ et l'arrivée sont placés au hasard tout comme le nombre de murs.
Certains parcours sont extrêmement simples, d'autres montrent que l'algo se débrouille plutôt bien
Il ne faut perdre de vue que le but est simplement de voir que le programme trouve toujours un chemin, le plus proche possible du meilleur chemin et le plus rapidement possible, si cela est physiquement possible.


Modification
- Dans le fichier Main (Main_astar.php) se règle le départ et l'arrivée si vous souhaitez forcer des valeurs.
- Dans le fichier Visuel_astar.php vous pouvez changer la taille de la grille (Faites un "CTRL -" si vous choisissez une grille plus grande selon la taille de votre résolution) et/ou changer la densité des murs du pseudo Labyrinthe.
- Vous pouvez aussi décommenter la section des valeurs dans la grille afin de comprendre les valeurs utiles pour l'algorithme (dans ce cas choisissez une taille de grille plus petite comme 40 * 20 pour la lisibilité des cases).
- Dans le fichier Algo_astar.php vous pouvez changer la valeur de la 'diagonale' afin d'avoir un chemin avec une préférence pour la diagonale (par défaut) ou la ligne droite (un peu plus long à l'exécution).

Voilà, si cela peut servir à quelqu'un.
N'hésitez à faire toutes les remarques que vous souhaitez

Merci de votre attention
Amicalement,
Mostal

Pour ceux qui se demanderaient de quoi on parle ici :

http://giik.net/algorithme_cheminleplus ... rithm.html

C'est un algorithme de recherche du chemin le plus court ( ou en anglais : Pathfinder )

Moi je suis tombé sur un cas où le chemin n'était pas le plus court... =) (en rouge le bon chemin)

en effet, je le précise bien un peu plus haut en disant " le plus proche possible du meilleur chemin"

Le plus souvent l'algo trouve le chemin le plus court mais certaines imprécisions, à commencer entre autre par le calcul des distances par une simple soustraction entre le point courant et l'arrivée en X et Y, induit une petite imprécision.
Par contre elle a l'avantage de ne traiter que des entiers, tout en restant assez correct.

Au final, dans de très nombreux cas, le chemin sera bel et bien le plus court et avec une rapidité supérieure à d'autres méthodes qui se voudraient strictement plus précises

Malgré tout, bien vu Savageman =D>

P.S.
En effet, Dans mon désir de clarté, j'en ai oublié l'essentiel en omettant de dire ce qu'était le A* (mais c'est expliqué dans le code malgré tout )
Merci d'avoir corrigé ce point Calimero

**Edit**
Je viens de compter et j'ai l'impression que la distance entre ce que l'ordi propose et le chemin que tu indiques est identique (ou à 1 prés), non ?

Bonjour,

**Edit**
Je viens de compter et j'ai l'impression que la distance entre ce que l'ordi propose et le chemin que tu indiques est identique (ou à 1 prés), non ?

Je trouve aussi que la distance est la même ...


**Edit**
j'ai considéré ( à tort ? ) que la distance se mesurait en nombre de "pas".

oui je crois qu'on peut considérer la distance ici sur le nombre de "coup" qu'il faut pour se rendre d'un point à un autre

Oui ok, en nombre de coup c'est pareil. Mais si tu compte qu'un coup diagonal fait 1,4 de distance (racine de 2), alors la solution donnée par ton A* est plus grande.

Ceci dit, c'est juste un petit problème d'heuristique, rien de bien méchant. =)

A* n'est pas là pour trouver le chemin le plus court, mais le chemin le moins coûteux, pondéré par une heuristique. C'est cette fonction heuristique (en général c'est la distance entre la position actuelle et la position finale, ça permet de tendre à ne pas faire trop de détours (*)) qui permet de modifier le comportement de déplacement d'une entité à l'autre en utilisant pourtant le même algorithme.


(*) exemple (non réel, mais c'est pour donner une idée), imaginons le terrain suivant, le chiffre représente le coût d'accès à la case (0 = inaccessible), et l'heuristique est la distance entre la position actuelle et la position finale (B) à chaque itération, et j'ai droit à 20 points de déplacement.
Si on passait par les cases 1, ça coûte 13 points, alors que si on prend le chemin direct ça en coûte 16. Un A* avec une heuristique = distance donnera le chemin à 16 points, un A* avec une heuristique constante donnera le chemin à 13 points.

Le cout en déplacement à en effet toute son importance.

J'ajoute une petite variation autour du même thème : La boucle
Le programme va tracer un chemin de 'patrouille' en dessinant des formes polygonales dans un espace donné

Pour cela j'ai créé un découpage de "zones" pour tracer un losange (ou un diamant) qui va servir au Astar à se déplacer de point en point.
(note : La classe Astar n'a pas été modifié)

On voit ici le programme tracer un chemin d'un point à un autre jusqu'à rejoindre le point de départ.

Précision : Bien que la forme du tracé ne soit pas sujet au croisement, le chemin ne peut pas se croiser car les valeurs "fermées" sont conservées (sans obligation).

Il est toujours possible de forcer la valeur de la diagonale (dans le fichier Astar) pour voir des dessins en formes polygonales cubiques

Téléchargement : http://www.dedikam.com/telechargement.p ... e5a875ebf1


Voilà, Merci
Amicalement,