Discussion :

[Marco17]

Bonsoir, voilà je m'intéresse un peu aux solutions algorithmiques pour le pathfinding (pour l'instant je ne me suis pas documenté, j'ai juste essayé de réfléchir par moi-même), et je me demandais s'il était possible (ou si c'est déjà fait) de faire une résolution de pathfinding (sur une grille) par remontée d'un gradient...

Par exemple, on commence à un point au hasard dans un labyrinthe, et on veut aller à un autre point connu, par le chemin le plus court, alors on attribut une variable à la case d'arrivée qui a une valeur élevée, puis pour chaque case voisine "libre" (en partant de l'arrivée) cette variable décroit un peu, on établit ainsi un gradient de cette variable sur l'ensemble de la grille, et on peut après - depuis notre point de départ - remonter le gradient de la dite variable pour trouver le chemin qui mène à la sortie...

Bon voilà, je sais pas si c'est très clair, je voulais savoir :
1) Si ça fonctionne
2) Si ça existe déjà
3) (à condition que ça marche), si ça peut être performant...

J'espère que vous pourrez m'éclairer à ce sujet !

[pseudocode]

Bon voilà, je sais pas si c'est très clair, je voulais savoir :
1) Si ça fonctionne

Oui.

http://fr.wikipedia.org/wiki/Image:P...ing_A_Star.svg

2) Si ça existe déjà

Oui, c'est l'algo A-Star avec exploration complete.

3) (à condition que ça marche), si ça peut être performant...

L'exploration complete est couteuse mais permet toujours d'avoir le résultat optimal. Generalement, avec A-Star, on fait une exploration partielle en utilisant une heuristique: c'est plus rapide pour les tres grandes grilles. A toi de voir suivant la taille de ta grille.

[Marco17]

ah d'accord Eh ben j'avais entendu parler de A*, mais j'ai jamais eu le courage de me pencher sur son fonctionnement... Avoir retrouvé un algo identique (ou similaire ?) m'aidera probablement à le comprendre ^^.

En tout cas merci beaucoup pour ta réponse !