Bon, déjà faut savoir deux trucs :
- C'est moins efficace qu'un "vrai" A* puisque ça fait bcp moins de tests, du coup l'algo a du mal à s'y retrouver dans des petits couloirs
- Il faut être patient pour l'ajuster, c'est souvent une histoire de réglages avant d'arriver à qqchose de correct
Par contre bien sûr, c'est plus rapide qu'un A* classique, d'où l'interet sur Ti. Bon je vais essayer d'expliquer ça de mémoire, vu que je n'arrive plus à trouver la page sur laquelle était l'algo (ça doit dater de 2 ans, elle a pê disparu depuis).
Imaginons un labyrinthe composé de cases qui contiennent, pour simplifier, soit un mur, soit rien. Tu commences avec ton perso à déplacer jusqu'à la sortie. Première chose à faire : l'orienter vers ce point de sortie (on utilise 8 directions, haut bas droite gauche et les diagonales). Ensuite commence la boucle principale qui doit ressembler un peu à ça :
tant que le perso n'est pas arrivé à destination
tester les 3 cases devant lui (si il "regarde" vers le bas, ça sera bas/gauche, bas, et bas/droite, si il "regarde" en haut à gauche, ça sera haut, haut/gauche, gauche, etc...)
en fonction du nombre de cases libres :
- si il n'y en a aucune, marquer la position actuelle comme un mur (pour ne jamais y retourner), et revenir à la position précedente (ce qui implique de sauver qqpart la succession des déplacements)
- si il y en a une, y aller, sans changer l'orientation du perso
- si il y en a deux, aller à celle qui se rapproche le plus du but à atteindre, sans changer l'orientation du perso
- si il y en a trois (si elles sont toutes libres), changer la direction du perso pour qu'il "regarde" vers la case la plus interessante (la plus proche du but), et s'y rendre
Ça c'est la version de base, à partir de laquelle tu peux envisager beaucoup de modifications. Par exemple tu peux tester 5 cases au lieu de 3, changer la direction de différentes façons (faire la moyenne entre la direction actuelle et celle vers la case, quand il y en a 2 de libres), etc... Le plus long sera vraiment de trouver la combinaison qui te convient le mieux.
Un autre truc facile à faire et qui améliore pas mal les perf (j'avais fait ça pr GBS justement), c'est répartir la recherche sur plusieurs frames : par exemple n'autoriser que 50 ou 100 tests par frame, si le chemin n'a tjrs pas été trouvé, alors on continuera à la frame suivante pour éviter de faire trop ramer.
Je viens de retrouver un screenshot de ce que ça donnait avec une vieille version pour GBS (y'avait qq merdes, puisque des fois le bot passe par des cases inutiles, mais grosso modo ça marche) :
http://databob.free.fr/Volatile/Image/Prog/GBS/GBSBotPathfindTest.gif
