j'ai codé un algo A* vite fait sous python histoire de prototyper le fonctionnement
(http://deeplo.free.fr/a-star.py pour les petits curieux)
Ca génère une image png sur fond blanc avec des pixels noirs (les cases ou on ne peut pas aller) et le tracé du chemin du point vert vers le point rouge. Dans les conditions de déplacement, je n'autorise que les déplacements que j'appelle orthogonaux (haut, bas, gauche, droite)
Les autres couleurs sont :
le jaune : les points de la liste ouverte qui ne sont pas passés ds la liste valide
le bleu clair : les points de la liste valide qui ne font pas partie du chemin trouvé.
Le bleu foncé est le chemin solution
A la ligne 127, le critere de validité pour le chemin est : 'd+step' : d, la distance euclidienne au carrée, et step, le nombre de cases deja parcourues depuis le debut du chemin pour la case en cours. En pondérant ces deux valeurs l'une par rapport à l'autre j'ai des comportements qui varient mais qui donnent quand meme sensiblement le meme resultat on va dire.... peu importe je m'etale là ;-)
Maintenant j'ai une question : je cherche à trouver d'autres manières d'utiliser cet algo (le modifier quoi) et je me demandais si calculer les chemins en partant à la fois du point vert et du point rouge et modifier la fonction heuristique pour que chacun des "demi-chemins" se dirigent vers l'autre (normalement ils devraient converger l'un vers l'autre : en fait c'est comme si je calculais deux chemins au lieu d'un seul et que la destination bougeait à chaque tour.)
Est ce que cela a un sens de faire ça ? Est que cela peut permettre d'optimiser le chemin (en tps de calcul ou bien distance finale trouvée) ?
J'aurais tendance à dire que cela ne change rien, ou pas grand chose, mais j'aurais aimé avoir l'avis de la communauté la-dessus avant de le prototyper (oui je suis flemmard, c'est l'âge ;))
@+ les geeks !
