Création de Labyrinthe en C
Bonjour à tous,
Tout nouveau sur ce forum, je commence donc par me présenter, je suis étudiant en 2ème année de licence et je viens d'effectuer un changement de licence (ce semestre), afin d'accéder plus facilement au master que je vise.
Mon problème c'est justement cette réorientation, je suis dans cette nouvelle promo depuis 2 semaines, et la formation est très peu différente de ma précédente formation, si ce n'est en un point, enfin en une case de l'emploi du temps qui s'appelle : "PROGRAMMATION" (quand on ne connait pas et qu'on arrive comme moi, ça fait peur ) ... Enfin, j'arrive donc dans une promo qui fait de la programmation depuis au moins 6 mois et moi avant la semaine dernière je ne savais pas ce qu'était un int. Depuis 2 semaines je suis en formation intensive de C, j'ai énormément parcouru ce site et bien d'autres afin de découvrir ce langage, et en 2 semaines j'ai quand même réussi à faire quelques trucs, tout d'abord, un fabuleux "Hello World", dont je fus très fier, ensuite une calculette qui ne sert à rien mais dont je fus encore plus fier, ensuite divers exercices permettant de découvrir les tableaux et enfin un programme de résolution de sudoku, sur lequel j'ai passé un temps incroyable mais qui fonctionne (encore plus fier ça lol, en plus ça peut être utile ... enfin si on joue au sudoku ... ).
Voilà, vous savez tout de moi, maintenant j'ai un nouveau problème, pour mardi prochain, je dois créer un programme (ça c'est pour l'école, les autres trucs c'était perso, pour apprendre), qui crée un labyrinthe, ça a l'air super intéressant comme ça, mais j'ai passé la nuit sur le problème et j'avoue que je n'ai pas vraiment avancé, sur le papier je trouve comment faire, mais dès que je dois tapoter tout ça sur l'ordi, je suis perdu.
Je vous donne donc le sujet (enfin des extraits) :
" Les 2 methodes les plus connues pour fabriquer un laby parfait sont l'exploration récursive et la fusion de zone (ça j'ai compris) ...
... Une case est choisie aléatoirement comme point de départ ...
... Les labyrinthes seront modélisés à l'aide de tableaux de taille prédéfinie (par exemple 15x15). ...
... Chaque case sera modifiée par une structure contenant les informations nécessaires (un drapeau booléen pour chaque mur, et un entier pour les identificateurs/marques de visite). ...
... Définissez les types CASE, LABYRINTHE et POSITION (structure pour les 2 coordonnées d'une case quelconque). ... "
... ... ...
... Donc avec ça, le laby doit etre créé, et une seconde partie (mais si j'arrive jusque là ça sera deja pas mal), demande de créer le jeu, en definissant au hasard une sortie (place peripherique), et en plaçant le joueur au milieu (loin de la sortie) du labyrinthe, lui dire où se trouve la sortie, quelles directions il peut emprunter de la place où il se trouve, et le laisser se debrouiller (en boucle). En bonus il veut meme qu'on lache un tigre qui se deplace en meme temps que le joueur, ... mais tt ça c'est du bonus, je vais deja essayer de créer ce maudit labyrinthe.
Voici où en est mon étude du problème :
Si j'utilise l'exploration récursive, ça me donnera quelque chose, comme ça :
explore (L,P) //Labyrinthe, position
marquer P // pour dire que je suis bien passé par ici
melanger di //ça c'est le conseil du prof d'utiliser des directions Nord Sud Est Ouest, dc on mélange comme ça, les laby ne sont jamais les memes
pour tous les di
si P+di n'est pas en dehors ET pas deja marqué //si je sors pas du laby ET que je suis pas deja passé
alors
je casse le mur entre P et P+di
explore (L,P+di)
(Je pense vraiment que c'est ici qu'il veut en venir, vu les explications données et en plus sur le papier ça marche sauf que si je suis en dehors ou sur une case deja marqué, pour toutes les directions, je dois revenir en arrière (ça fera une impasse), et ça je sais pas faire, le prof m'a dit : "ça revient en arrière et garde à chaque fois en mémoire où tu en étais", j'ai dis "ah ok", mais en fait, j'ai pas compris comment on fait :s)
Pour la fusion de zone, l'étude a été bien plus longue mais le résultat est plus simple :
tant que (pas fini) //ça sera fini quand toutes les cases vaudront 1
choisir un mur separant 2 cases ayant des numeros different i et j //oui parce qu'au début j'ai numéroté les cases (par exemple de 1 à 16 pour un 4x4).
fusionner les zones i et j // remplacer le plus grand nombre par le plus petit)
(sur le papier ça marche, et je crois que malgré la complexité, je cerne mieux cette façon de faire, et sur le papier les laby produit sont plus jolie lol)
Une autre question se pose, est-ce que les murs sont autour d'une case ( des traits et des + pour les angles) ou est-ce que je fais des gros murs avec des # (dans ce cas, je devrais à chaque fois sauter une case au lieu de prendre la case d'a coté, et si je veux casser le mur, je devrais vider la case où était le #)
Voilà, vous savez tout ce que je sais, j'ai étais long, mais je tenais à être précis au cas où quelqu'un se pencherait sur mon problème, en tout cas, je ne vous demande pas de faire ce travail à ma place (bon si vous y tenez ou si vous l'avez fais, j'veux bien lol :p ) mais ce n'est vraiment pas mon but premier, mon but, ça serait plutot que vous m'expliquiez la démarche qui vous semble la plus judicieuse, et que vous m'indiquiez quelques petits points que je n'ai pas cerné, ou des façons de faire, ...
Si quelqu'un pouvait m'aider, je ne sais pas ce que je peux faire pour le remercier, mais vraiment je lui en serai très reconnaissant.
Merci à vous
