[Résolu] Possibilité de mouvement avec case et obstacles

[uriak]

Le mieux reste un balayage horizontal, avec des listes proches de A *, sans fonction d'évaluation.
Une liste de cases ouvertes sur le front F, et une liste de cases qui vont constituer l'anneau suivant N et une liste de cases traitées T

En gros tu prend ta case de départ et tu fais

départ : F = case de départ, i=0
pour chaque niveau i < distance max.
{
si F est vide on arrête : plus de passage !
pour chaque élément de F
{
on regarde les cases adjacentes possibles (pas bloquées) qui ne sont pas dans O ni dans T*. On les ajoute à N. L'élément de F est déplacé dans T
}
on augmente i de 1
on copie N dans F et on vide N
}
à la fin on obtient dans T toutes cases à distance_max -1 et dans F celles à distance_max

Pour gagner du temps on peut exclure de la recherche la case parente de celle de F (si on la note). de même je pense qu'on peut vider T régulièrement, car il est inutile de remonter deux générations en arrière alors on ajoute une liste P (pour parents) :
pour chaque élément de F
{
on regarde les cases adjacentes qui ne sont pas dans O ni dans P. On les ajoute à N.
}
On copie P dans T et F dans P et N dans F.

à la fin l'ensemble des cases se trouve dans T,P et F

Mais dans ce cas on perd le bénéfice de connaître tous les chemins. De plus cet algo doit être modifié pour tenir compte de différentes valeurs de terrain...