Chemin un peu trop long sur mon pathfinder maison

Salut,

J'ai fait un pathfinder maison qui correspond à ce dont j'ai besoin par volonté de tout faire moi-même, mais je rencontre une légère difficulté.
Je précise que je suis sur grille isométrique !

Au départ le pathfinder s'étale du point d'arrivée (là où je vais cliquer) jusqu’à ce qu'il trouve le joueur. Il suit les cases "marchables", de la sorte j'obtiens une liste des cellules réduite contenant à coup sûr un chemin.
À chaque nouvelle couche, j'ajoute un "niveau" à la case ainsi que sa distance entre elle et le joueur.
(je n'utilise pas le niveau de la case dans mon code mais bon, je le virerais après si je n'en ai vraiment pas besoin)

Ensuite, il va partir du point où je clique et passer de cases adjacentes en cases adjacentes en les préférant à leur distance avec le point où se situe le joueur, mais il ajoutera la case précédente à une liste "path" pour ne pas passer deux fois par le même endroit.

Si par exemple il y a un cul de sac qui semblait être le chemin idéal, le pathfinder va passer sa case dans une liste d'exclusions, petit-à-petit il va démonter son chemin jusqu’à trouver des cases n'étant ni dans le path ni dans la liste d'exclusions. Ensuite, il va continuer et fatalement trouver le chemin.

Cela marche extrêmement bien, j'en suis assez content. Le soucis c'est qu'il peut rester des traces du chemin passé.

J'ai ajouté des images, je ne sais pas où elles vont apparaitre, je ne suis pas encore familiarisé avec ce forum.

légende : en vert la case ciblée, en bleu le path et en rouge l'exclusion.

Donc ma question serait : comment savoir quelles cases me rallongent inutilement le chemin ?

Je pense faire des fils tendus, ou plutôt des rayons dans les cases bleues afin de repérer les lignes droites ou zones pouvant ne pas être traversées mais j'ai peur que cela soit un peu lourd. Vos avis ? Comment feriez-vous à ma place en utilisant la base que j'ai fait ?
Si j'ai été imprécis sur des faits dites-le moi.

Je vous remercie de votre aide :)

Pièce jointe 181712

Pièce jointe 181713

Pièce jointe 181714

J'ai eu une idée en regardant mon topic seul et sans réponse : j'assigne un numéro à chaque case (de 1 à la taille du path) et je parcours chaque case en voyant si je ne trouve pas une case adjacente sur mon chemin qui a un numéro plus élevé que la case suivante théorique. Comme ça, je saute les cases non voulue. Et puis pour les gros pâtés, je peux répéter l’opération jusqu'à qu'il n'y ait plus de résultat. Est-ce la meilleure solution ? Des idées ?

Vu que tu es sur du pathfinding et des recherches de plus court chemin, je vais te conseiller de te rapprocher de mon ami Mathématiques porté par l'imprononçable Dijkstra !

https://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra

C'est pas la seule solution (il y en a d'autres : https://fr.wikipedia.org/wiki/Probl%...de_cheminement ) mais elle est solide.



Sinon, ça a l'air sympa ce que tu fais !

Tu appliques une technique systématique, je ne comprends pas comment tu ne peux pas avoir le plus court chemin.
Supposons une matrice de case, certaines sont interdites (obstacle). La case d'arrivée est numérotée "1" et est placée dans une file d'attente.
Tant que la file d'attente n'est pas vide, alors prendre la première case de la file. Pour cette case numérotée X, si la case du haut est déjà numérotée, l'ignorer. Sinon, la numéroté à X+1 et la placée dans la file. Faire de même pour les cases en bas, à gauche et à droite. S'arrêter lorsque la case du personnage est trouvée et donner un numéro à cette case.
Pour trouver le plus court chemin, partir de la case du personnage numérotée Y et trouver la case adjacente (haut, bas, droite ou gauche) numérotée Y-1. Recommencer jusqu'à trouver la case numérotée 1.
Le plus court chemin est assuré par l'usage de la file d'attente.

Ce que tu chereches à faire, c'est comme deja précisé l'algorithme de Dijkstra. Ou, dans le cas des jeux, la variante quasiment toujours utilisée: l'algorithme A* (voir sur google "A star").

Note qu'on peut voir sur tes images que ton algo n'est pas optimal puisqu'il utilise parfois des doubles cases (sur ta premiere image, les cases 351 et 342 par exemple alors que ce devrait etre que 351).

Bref, pour l'avoir implementé, l'idée est de maintenir une liste des cases deja testées pour eviter de refaire plusieurs fois le meme chemin ainsi qu'une liste des cases à tester. Cette derniere liste sera classée selon un critere de meilleure case (généralement la distance entre la case concernée et la destination).
Je ne te mets pas le detail de l'algo, ca se trouve tres facilement.
Par contre, il faut savoir que l'algo peut etre tres gourmand en memoire si la carte est grande et qu'il y a beaucoup d'obstacles. En general, la liste de cases deja testées est parcourue pour chaque nouvelle case à ajouter. Et plus elle est grande, plus le temps de parcours est long. Sur ce genre d'algo, ca peut etre non negligeable. Dans mon cas, j'avais utilisé une liste de boolean dont je connaissais l'index grace aux coordonnées de chaque case. Ca permet d'aller directement au bon endroit plutot que de parcourir une liste qui peut contenir des milliers de cases. Et ca a beaucoup raccourci le temps de recherche global (dans mon cas, 7 fois plus rapide qu'avec l'algo qui parcourait la liste dans le cas que j'ai testé).

En fait la taille de ma map n'a rien à voir avec le pathfinder étant donné que je fais un étalement. Je le fais par cases adjacentes. Du coup il ne peut pas y avoir trop de cases dans mes listes car le joueur ne peut pas de-zoomer, les maps sont restreinte et l'écran est petit.
J'ai réussis à avoir mon chemin le plus court. Je numérote les cases et après je fais le chemin inverses en cherchant toujours le chiffre le plus petit autour. Je boucle jusqu’à qu'il n'y ai plus de résultat et après je recommence avec une distance d'une case autour.
Sujet résolus. Conso de mémoire très basse, le code s’exécute instantanément, tout vas bien :)

Merci à vos réponses, je vais tout de même fouiller du côté de ce que vous m'avez dis.
Résolut.