Labyrithe en c

haytra -  
mamiemando Messages postés 33228 Date d'inscription   Statut Modérateur Dernière intervention   - 
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   <a href="http://haytra.freeheberg.com/Projet.pdf"> ICI</a> 
Configuration: Windows Vista
Firefox 3.0.1

4 réponses

  1.
    mamiemando Messages postés 33228 Date d'inscription   Statut Modérateur Dernière intervention   7 944
     
    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
    0
  2. haytra
     
    merci pour ta réponse mais je crois que la methode ideale ce n'est pas pour moi :p
    0
  3. mamiemando Messages postés 33228 Date d'inscription   Statut Modérateur Dernière intervention   7 944
     
    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
    0
    1. haytra
       
      d'abord merci encore pour tes réponses! je t'explique pourquoi je peut pas faire comme tu ma dit: l'utilisateur doit avoir une grille en face de lui, puis en utilisant les touches du clavier (droites,gauches,..)il se crée son propre labyrinthe a partir de la grile. Un vrai casse tette
      0
  4. mamiemando Messages postés 33228 Date d'inscription   Statut Modérateur Dernière intervention   7 944
     
    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.
    0