labyrithe en c Fermé

Question

Salut a tous!Ma question concerne la creation, d'un labyrinthe en c. L'utilisateur a face a lui une grille n*n correspondant aux limites du labyrinthe. Au debut un curseur est positionné sur la case de départ . La definitiondu labyrinthe se fait en deplacant le curseur de case en case. Une fois le labyrinthe defini il est memorisé puis effacé de l'ecran. Alors je sait pas comment faire surtout pour la phase de memorisation et du dessin du labyrinthe a partir d'un tableau a 2 dimension :strange: Voici les consignes plus en detail pour ceux que ca interesse ICI

mamiemando · Answer

Méthode naïve

Si c'est juste une représentation sans avoir à faire tourner d'algorithme de cheminement, le plus simple c'est de coder une matrice dont chaque case permettra de décrire les murs. Si je note avec des * les coins de la case ça pourrait donner, par exemple
0 mur :
* *
 0
* *
1 mur :
*-*
 1
* *

* *
|2
* *

* *
 3|
* *

* *
 4
*-*
etc... Je te laisse la joie de faire les cas avec les combinaisons de 2murs, 3 murs, et 4 murs. Il devient alors facile connaissant la position du joueur dans cette matrice de savoir dans quelle direction il peut se déplacer.

Le principal avantage de la méthode est que le labyrinthe devient facile à tracer

Méthode idéale

Je ne sais pas si tu as eu la joie de faire de la théorie des graphes, mais c'est dans ton cas l'outil le plus adapté. En effet chaque case du labyrinthe est un sommet ayant au plus 4 voisins (les cases adjacentes), sachant qu'on ne construit un arc entre deux sommets (cases) que si elles sont adjacentes et qu'elles ne sont pas séparées par un mur.

En affectant une métrique de 1 à chaque arc et en choisissant pour sommet source la case où est positionné le joueur, il devient facile de calculer le plus court chemin avec un algorithme de Dijkstra vers n'importe quelle case du labyrinthe.

Idéalement tu peux utiliser en C++ la librairie boost qui propose un algorithme de Dijkstra et un export graphviz de ton graphe. Si tu dois te contenter d'un mode texte tu as intérêt à stocker dans les sommets du graphe leurs coordonnées afin de les ordonner facilement et de retrouver quelles cases voisines sont accessibles ou non.

Bonne chance

haytra · Answer

merci pour ta réponse mais je crois que la methode ideale ce n'est pas pour moi :p

mamiemando · Answer

Si tu n'as pas besoin de calculer de chemin dans ton labyrinthe, la première est clairement plus simple. As-tu d'autres questions ou tu penses t'en sortir comme ça ?

Bonne chance

mamiemando · Answer

Les deux méthodes marchent pour ce que tu veux faire, mais la première est clairement plus adaptée. La deuxième est utilisée comme je te le disais si tu dois chercher un chemin dans le labyrinthe entre deux points, mais c'est son seul intérêt dans ton cas.

Dans les deux cas il faut simplement étoffer ton labyrinthe au fur et à mesure des choix de l'utilisateur. Par exemple dans la première méthode, ça consiste simplement à corriger les deux cases de matrices intervenant lors d'un déplacement.

Labyrithe en c

4 réponses