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

[Argorate]

Bonjour a vous, je me suis mis en tete la creation d'un petit jeu, et voila que je tombe sur un pb que je n'avais pas prévus:

Screenshot
Donc dans mon exemple, le petit bonhomme ne peut se deplacer que de 10 cases, mais il ne peut pas allez sur les cases bleues. autrement dit se que j'ai baré en rouge ne devrait pas lui etre accecible.
Je ne sais pas comment calculer tout les chemins a 10cases avec les obstacle au milieu...

donc si vous pouviez me dire comment faire pour me debloquer cela me serais d'un grand secour!

merci bien.

[Harparine]

Regarde sur le wiki : naholyr avait posté un truc super sur l'algorithme de recherche de chemin A* et tu peux compléter avec des recherches sur le net.

[Argorate]

j'ai vu l'algo A*, c'est pas se qu'il me faut en l'occurence.
je n'ai pas un point de depart et un point d'arrivé, d'autant plus que sa ne prend pas le chemin le plus cours...
bref c'est pas vraiment ce qu'il me faut.

[X-ZoD]

si tu n'as pas de point de depart ni d'arrivé comme veu tu savoir si son chemin est bon ? XD

[uriak]

En réalité il a un point de départ et il veut connaître tous les points d'arrivée atteignables afin de les afficher, je me trompe ?

[Argorate]

tout a fait. il me faut mettre en évidence toute les case ou il peut allez avec 10 cases de deplacement donc.

[Harparine]

A part tester tous les chemins (ce qui est assez lourd), je ne vois pas vraiment comment tu peux faire ce genre de truc. L'idée serait donc de définir la zone max de déplacement (ici le carré de dix sur dix) et de simuler un déplacement jusque chaque case de la zone. Tu peux bosser avec 3 tableaux : un tableau contenant l'ensemble des cases à tester, un contenant les cases déjà testées et un autre contenant les cases valides qui te servira à afficher la vraie zone de déploiement. Dans l'idée, c'est très proche de A* car il y a les mêmes tableaux.

[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...

[Roworll]

Tout ceci me parait bien lourd. Ce ne serait pas plus judicieux de repenser le système de déplacement plutôt que de se lancer la dedans ?
J'ai déjà vu des jeux en PHP avec une petite interface JS pour gérer les déplacements dont le résultat était plus que correct.
Par exemple,
- un personnage a 10 points de mouvement.
- sur la map, il clique les cases les une après les autres dans l'ordre de son déplacement.
- a la validation, la série de case cliquée est envoyée au moteur du jeu qui se charge de valider et de renvoyer le réaffichage.

Pas d'algo lourd et casse tête, juste à vérifier que les cases dans l'ordre de clic sont contigües et accessibles.

[Argorate]

ce n'est pas possible, j'ai plusieurs unités, auquel je dois pouvoir conaitre a tout moment leur capacité de mouvement et leur porte de tir, je ne peut donc pas faire un systeme aussi trivial qu'une case apres une autre.
d'ou mon pb...
je vais esseyer de voir si je trouve qq chose avec se que tu as dit uriak, mais si vous avez d'autre proposition, n'attendez pas ^^