Bonjour à tous,

Je suis étudiant débutant en langage c, mon projet et de générer et réaliser l'interface graphique d'un labyrinthe.
J'ai choisi la méthode exhaustive partant d'un labyrinthe où chaque porte est fermée ( voir [ Lien ] )
J'ai choisi comme interface graphique, SDL, pour gérer l'affichage du labyrinthe.
Le labyrinthe aura la possibilité d'être sauvegardé, trois niveaux de difficultés devront être possible.
Je cherche donc un algorithme qui concorderait avec ce programme assez rapidement car comme tout les étudiant je m'y prend au dernier moment.
ps: le code a quasiment été finit par un camarade mais son implication et le temps qu'il nous reste l'empéche de faire cet algorithme et j'avoue que j'aimerais comprendre le fonctionnement de son code via un algorithme.

Merci d'avance.

euh... son turc est tres bien explique hein...
je l'ai lu dans un linux mag, il y a plusieurs annees.

dit au moins ce que tu ne comprends pas...

en fait j'aimerais avoir un arbre algorithmique afin de comprendre le déroulement du programme car j'ai lu et je pense bien cerné le sujet mais je ne sais pas par quel bout le prendre !!

merci de t'interresser a mon sujet.

un arbre algorithmique ? c'est quoi ?

des programmes qui font ca, j'en ai fait un en C#, un en javascript, et en C aussi... c'est vraiment pas dur a faire...

http://www.javascriptfr.com/codes/LABYRINTHE_24661.aspx

http://www.javafr.com/codes/APPLET-GENERATEUR-LABYRINTHES-ALEATOIRES_40576.aspx

http://www.csharpfr.com/codes/GENERATEUR-LABYRINTHES-ALEATOIRE_44802.aspx

sinon, j'avais un petit texte au sujet des labys...

copie le dans un .txt, t'auras un meilleur rendu...

Quelle est la deffinition mathématique du labyrinthe ? Il n'y en a pas exactement... C'est pour cette raison qu'on ne peut pas faire de générateur universel de labyrinthe, on ne peut que faire une version des multitudes de générateurs possibles, et ce générateur ne fournira qu'un seul type de labyrinthe sur la multitude de labyrinthe possible...

Pour la suite, on considerera que notre personnage n'a pas droit de revennir sur ses pas : si il passe de la case C1 a la case C2, alors de la case C2, il n'a pas le droit d'aller vers la case C1. On appellera ca faire un demi tour (sur une seule case donc).

Si on désires faire une animation 3d d'un gars qui parcourt un labyrinthe en revennant toujours au même endroit, alors on doit faire un labyrinthe qui possède plusieurs chemin possible pour aller d'un point à un autre (ou alors, le gars devra faire des demis tours, ce qui est interdit)... Pour la suite, on nomera cette propriété : la propriété deuxchemins.

Pour certains jeux vidéos, on devra générer des labyrinthes deuxchemins, et d'autres, on devra faire des labyrinthes simplechemin, exemple: vous faites un rpg, vous devez poser des objets spéciaux dont le personage principal a obligatoirement besoin, vous devez alors faire un labyrinthe simplechemin car vous serez alors sur que le personnage passera au moins par les cases de votre chemin.

Pour d'autres jeux, genre un doom-like ou un pacman, la solution plusieurs chemins peut être plus appropriée car le personnage pourra surprendre son adversaire plus facilement.

Si on choisit deux cases au hazard, dans un labyrinthe simplechemin, il existe un chemin unique qui va d'une case à l'autre. Dans un labyrinthe deuxchemins, il existe au moins un chemin qui va d'une case à l'autre. Tout labyrinthe simplechemin est aussi un labyrinthe deuxchemins. Un labyrinthe deuxchemins est strictement deuxchemins si il n'est pas simplechemin.


Ceci est un simplechemin :
  __________________
 |____ |______    _|
 |   |______ |_|   |
 | |______ |__ | | |
 | |  _______| | | |
 | |______ |  _| | |
 | |  __ |___|  _| |
 |___|  _|  ___| | |
 |   | |_________| |
 |_|_______________|

et ceci est un deuxchemins strict.
  __________________
 |____ |______    _|
 |   |__ ___ |_|   |
 | |______ |__   | |
 |    ____ __  | | |
 | |_ ____ |  _|   |
 | |  __ |___|  _| |
 |___   _|  ___| | |
 |   | |___ _____| |
 |_|_______________|

Pour l'obtennir j'ai enlevé des murs aux premier... On observe que l'on peut faire une boucle (partir dans une direction, et revennir à son point de départ sans jamais revennir sur ses pas).

Certains labyrinthes ne sont pas simplechemin, et ne sont pas non plus deuxchemins. Lorsque l'on choisit deux cases au hazard, il n'y a pas forcément de chemins qui mène d'une case à l'autre :

  __________________
 |____ |______    _|
 |   |__|___ |_|   |
 | |______ |__ | | |
 | |  _______| | | |
 | |______ |  _| | |
 | |  __ |___|  _| |
 |___|  _|  ___| | |
 |   | |_________| |
 |_|_______________|

On observe qu'au coin en haut à gauche, on est enfermé sur un nombre réduit de cases... Il n'existe pas de chemin pour aller du coin en haut à gauche au coin en bas à droite.
Ce labyrinthe sera nommé paschemin.


Un pacman utilise un deuxchemins, un rpg utilisera plus souvent un simplechemins, et peu de jeux utilisent des paschemin, car une case à laquelle on ne peut accèder et qui est quand même en mémoire, c'est domage... Les paschemins peuvent etre generes en ajoutant des murs aleatoirement, les autres, c'est plus complique...

Pour générer un deuxchemins, ou un paschemin, il n'existe pas vraiment de formule magique... Pour un deuxchemins, on part d'un simplechemin, et on ouvre quelques cases, et pour un paschemin, il serait domage de voir son pacman emprisoné dès le départ, alors on ne s'interessera pas à ce cas...

GENERATION D'UN SIMPLECHEMIN

On démare avec un bloc de portes...
Le but de l'algorithme : ouvrir juste assez de portes pour permettre une chemin aléatoire de toute cases vers toute autre cases...
  __________________
 |_|_|_|_|_|_|_|_|_|
 |_|_|_|_|_|_|_|_|_|
 |_|_|_|_|_|_|_|_|_|
 |_| |_|_|_|_|_|_|_|
 |_|_|_|_|_|_|_|_|_|
 |_|_|_|_|_|_|_|_|_|
 |_|_|_|_|_|_|_|_|_|
 |_|_|_|_|_|_|_|_|_|
 |_|_|_|_|_|_|_|_|_|

On démare à un endroit choisi (il constituera d'un des deux points les plus éloignés...) Dans l'exemple on choisira le coin superieur gauche. le principe : on libère une case qui touche et sur laquelle on n'est pas encore allé, aléatoirement, et on note : "je suis passé sur cette case", et on recommence jusqu'a ce que l'on ne puisse plus (jusqu'a ce que toutes les cases que l'on touche aient déjà étés visités...) alors on retourne sur nos pas, et recommençons... Une idée d'algo récursif se fait sentir ;)
  __________________
 |__ |_|_|_|_|_|_|_|
 |_|_|_|_|_|_|_|_|_|
 |_|_|_|_|_|_|_|_|_|
 |_| |_|_|_|_|_|_|_|
 |_|_|_|_|_|_|_|_|_|
 |_|_|_|_|_|_|_|_|_|
 |_|_|_|_|_|_|_|_|_|
 |_|_|_|_|_|_|_|_|_|
 |_|_|_|_|_|_|_|_|_|
  __________________
 |__ |_|_|_|_|_|_|_|
 |_|_____|_|_|_|_|_|
 |_|_|_|_|_|_|_|_|_|
 |_| |_|_|_|_|_|_|_|
 |_|_|_|_|_|_|_|_|_|
 |_|_|_|_|_|_|_|_|_|
 |_|_|_|_|_|_|_|_|_|
 |_|_|_|_|_|_|_|_|_|
 |_|_|_|_|_|_|_|_|_|
  __________________
 |__ |____ |_|_|_|_|
 |_|____ | |_|_|_|_|
 |_|_|_|___|_|_|_|_|
 |_| |_|_|_|_|_|_|_|
 |_|_|_|_|_|_|_|_|_|
 |_|_|_|_|_|_|_|_|_|
 |_|_|_|_|_|_|_|_|_|
 |_|_|_|_|_|_|_|_|_|
 |_|_|_|_|_|_|_|_|_|
Ici, on se trouve bloque : aucune case ne permet de continuer, alors on doit retourner sur nos pas, jusqu'a ce que l'on trouve une case qui touche une case sur laquelle on n'est pas allée...
  __________________
 |__ |____ __|_|_|_|
 |_|____ | |_|_|_|_|
 |_|_|_|___|_|_|_|_|
 |_| |_|_|_|_|_|_|_|
 |_|_|_|_|_|_|_|_|_|
 |_|_|_|_|_|_|_|_|_|
 |_|_|_|_|_|_|_|_|_|
 |_|_|_|_|_|_|_|_|_|
 |_|_|_|_|_|_|_|_|_|
voilà, et on continue comme ça...
Le chemin le plus long partira forcément du coin superieur gauche...


Sur ce principe, on peut faire des labyrinthes simplechemin de dimentions n*n en un temps proportionnel au nombre de cases (enfin je crois).