Discussion :

[fabetvince]

Bonjour tout le monde,

En fait, je suis en pleine creation d'un labyrinthe, et j'aimerai bien connaitre une technique pour trouver le chemin le plus court.

J'explique un peu comment est crée le labyrinthe :
C'est un tableau de structure de deux dimensions.

voici la structure :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
typedef struct{
        int d[4];	// une case pour une direction.
        }ts;

chaque case de "d" correspond à un degrée de liberté de la pièce. On met à "0" si le chemin n'est pas possible dans cette direction, sinon "1".

Si mon explication n'est pas très claire, je peux recommencer :o

Merci

[Skyounet]

Non, ce n'est pas clair.

Va voir du cote du forum Algorithmique, je pense que les gens seront plus aptes à t'aider là-bas.

[MatRem]

C'est assez clair, c'est en effet une question d'algorithme.

Je vois une solution pour trouver le chemin le plus court entre deux cases:
Essayer tous les chemins possibles en comptant le nombre de cases et garder celui qui en a le moins.

[progfou]

Il faut représenter ton labyrinthe sous la forme d'un graphe, puis, par exemple, chercher le chemin le plus court entre les deux sommets qui sont tes cases avec un algorithme comme Dijkstra.

[reggae]

Je sais que chez Boost, il existe une fonction qui t'évitera de réécrire tout l'algo: http://www.boost.org/libs/graph/doc/...est_paths.html
A+

[fabetvince]

Merci de vos réponse. En fait, je fais un projet info pour l'école, et le problème, c'est que l'on a pas fait les graphes.

Mon tableau à deux dimension, est-ce un graphe ? Ou dois-je le convertir en graphe ?
Car dans une case, je peux avoir la direction droite autorisé, et dans la case à côté, la direction gauche interdite.
J'ai fais un petit dessin pour que se soit plus compréhensible.

[speedcore]

ou sinon vous pouvez allez voir Mme Ru..o

[fearyourself]

Mon tableau à deux dimension, est-ce un graphe ? Ou dois-je le convertir en graphe ?

Ce qu'est un graphe est arbitraire. Un tableau peut tout à fait représenter un graphe. La question est après de voir si la gestion et l'utilisation de ton graphe sera facile. Mais de toute façon, ta question est plutôt une question algorithmique et il y a un forum pour ce genre de question.

Résumons:

- Oui ta structure de donnée peut fonctionner bien que ce sera plus difficile je pense
- Non, on ne peut pas t'aider ici, tu n'as pas encore l'algorithme
- Oui, on t'aidera avec le code lorsque tu auras un problème précis.

Jc

[fabetvince]

Est ce qu'en changeant mon tableau de structure( voir précédemment) de la façon suivante cela serai plus facil pour gérer les déplacement du perso dans le labyrinthe???

Je pense agrandir le tableau, en ne mettant plus 4 cases pour les directions. Chaque case du tableau contiendra une couleur(ex noir=mur, blanc=chemin), j'ai regardé beaucoup de structure pour faire un labyrinthe, et je ne sais pas comment m'y prendre.

Pourriez vous m'aider svp