Je sais pas si ça peut t'aider mais il y a quelques années (et je crois que c'est le premier algo que j'ai jamais "inventé". J'avait donc eu l'idée de trouver le chemin a partir du contour des cases ou groupes de cases non franchissables.
Description rapide de l'algo qui trouve le trajet :
On va en direction du point de destination. Si on rencontre un obstacle, on suit son contour un fois par la gauche, une fois par la droite puis on repere si entre un des point du contour et le point de destination il y a un chemin sans obstacle. Si oui voila un chemin non réduit trouvé, sinon prendre le point du contour le plus proche du point de destination et recommencer.
Ensuite opérer à une réduction du chemin complet avec un petit algo récursif.
Je n'ai pas trop envie de réfléchir la dessus mais je peux te dire qu'il y a plein de bidouillages a découvrir pour améliorer l'efficacité (le plus simple c'est d'avoir les contours des objets déja calculés au lieu de les retrouver a chaque fois).
Sinon je peux t'assurer que meme avec des labyrinthes le chemin est toujours trouvé (a part certains cas, ça dépent de l'algo) et si il est réduit correctement il peut etre le quasi plus court. Mais bon cet algo est bien car il reproduit une marche intelligente si tu veux l'implémenter dans un jeu ou tu peux guider un perso. J'entend ici par intelligente car elle ressemble au trajet qu'aurait eu un humain et non pas a un sujet omniscient qui voit tout et aurait tracé un trajet en conséquent.
, je te soupconne de pas avoir lu la page 1
)
