deplacer arbres

salut
j ai un probleme ou j ai un tableau(de dimensiosn carrees) et dans ce tableau j ai un arbre que je veux deplacer d une position a une autre pour cela j ai 5 mouvements a ma diposition :
haut : qui deplace mon arbre d un cran vers le haut
bas : idem mais vers le bas
gauche : idem vers la gauche
droite : idem vers la droite
rotation : qui tourne l arbre dans le sens des aiguille d une montre de 90 degres

et mon probleme est de trouver un chemin(pas forcement l optimal) du depart jusqu a l arrivee et bien sur il y a des obstacles sur le chemin et les mouvements ne peuvent se faire que si il n y pas d obstacles les empechant

Exemple :
B 0 0 1 1
B 0 0 0 0
B 0 0 0 0
1 1 0 0 0
E E E 0 0
la ligne des B represente le placement de l arbre au depart

un des chemin est
droite,droite,bas,droite,tourner,bas,bas,gauche,gauche;

j espere que j ai ete suffisament claire et merci d avance.
la lignes des E represente le placement de l arbre a l arrivee
0 : emplacement vide
1 : obstacles

Est-ce qu'un arbre est toujours un segment (un tronc?) ou est-ce que cela peut être un objet plus compliqué?

Quand on tourne y a-t-il des contraintes autres que: l'emplacement de départ et d'arrivée sont libres?

Code:

---

1 2 3 4

X00 000 X10 010 X00 XXX

---

est-il possible?

Quoi qu'il en soit, on peut représenter un graphe des états possibles où les noeuds (les états) sont définis par (x,y,p). x et y sont les coordonnées de l'arbre et p est la position verticale ou horizontale.

On relie par un arc deux états s'il est possible de passer d'un état à l'autre par un déplacement/rotation et on cherche s'il y a un chemin dans ce graphe d'états.

Si le labyrinthe initial est très grand, on a intérêt à faire du A* sinon, n'importe quel algo de chemin fait l'affaire.

pour la rotation elle se fait par rapport au centre de l arbre qui a toujours une longueur impaire pour justement toujours avoir un centre mais aussi la rotation ne peut ce faire que si rien ne la gene c est a dire:

avant rotation:

0 0 0 0
0 0 B 0
0 0 B 0
1 0 B 0

la rotation est possible car il n y a pas de "1" sur la zone en gras

si la map etait comme ca :
0 0 0 0
0 1 B 0
0 0 B 0
1 0 B 0

le "1" souligne n empeche la rotation la rotation car l arbre tourne dans le sens des aiguilles d une montre maissi la map etait comme ca :

0 0 0 0
0 0 B 0
0 0 B 0
1 1 B 0

alors le 1 souligne empecherait la rotation de meme pour la droite de l arbre en haut = genant et en bas =pas genant

le probleme est que je na sais pas utiliser les graphes donc....difficile de mettre en applications ton aide.

A mon avis tu devrais chercher des cours dessus (je me souviens par ex en avoir fait beaucoup en automatisme) ou si tes arbres sont assez grands efectivement l'algo A* est tout indiqué... Et là il y a vraiment plein de doc partout, c'est un algo ultra classique, bien que un peu compliqué au premier abord, il finit par se laisser dompter :wink: ....

A+

Citation:

---

Envoyé par brennus

le probleme est que je na sais pas utiliser les graphes donc....difficile de mettre en applications ton aide.

---

Il y a plein de références sur le web.
Par exemple dans wikipedia:
http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra
Sinon, ce livre est bien
http://www.univ-valenciennes.fr/sp/sevaux/graphes/