Algorithme Labyrinthe en c

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).

//*parcour.c
*fichier contenant l ensemble des fonctions permettant de parcourir le
*labyrinthe
*/
 
#include<stdio.h>
/* Médinoc:
La macro assert() permet de tester des invariants,
terminant le programme si une condition supposée toujours vraie est fausse.
*/
#include <assert.h>
 
/*#include"../../include/parcour.h"*/
//#include"../../include/affichage.h"
#define H 4
#define B 3
#define D 2
#define G 1
/* Médinoc : À quoi vont te servir ces diagonales, finalement ? */
#define HD 0
#define HG 5
#define BD 6
#define BG 8
 
/** la fonction avance permet d'avancer dans le labyrinthe
 
 
*/
void avance();
int case_droite();
int case_devant();
 
/* Médinoc:
Suppression de variables locales:
Utiliser des pointeurs à la place.
*/
void avance(int *pi, int *pj, int dir)
{
int i;
int j;
assert(pi != NULL);
assert(pj != NULL);
i = *pi;
j = *pj;
 
/* Médinoc:
Utiliser un switch() à la place de ce lot de if...
*/
switch(dir)
{
case H:
i--;
break;
case D:
j++;
break;
case HD:
i--;
j++;
break;
case HG:
i--;
j--;
break;
case B:
i++;
break;
case G:
j--;
break;
case BG:
i++;
j--;
break;
case BD:
i++;
j++;
break;
default:
/* Normalement, on ne passe jamais ici,
car dir a toujours l'une des huit valeurs testées. */
assert(0);
break;
}/* switch */
*pi = i;
*pj = j;
}
 
/*la fonction permet de se deplacer si c'est possible
*/
/* Médinoc:
Suppression de variables globales. */
int case_devant(intconst laby [][100], int i, int j, int dir)
{
switch(dir)
{
case H:
return laby[i-1][j];
case D:
return laby[i][j+1];
case HD:
return laby[i][j+1];
case B:
return laby[i+1][j];
case HG:
return laby[i-1][j-1];
case G:
return laby[i][j-1];
case BG:
return laby[i+1][j-1];
case BD:
return laby[i+1][j+1];
default:
/* Normalement, on ne passe jamais ici,
   car dir a toujours l'une des huit valeurs testées. */
assert(0);
return1;
}/* switch */
}
 
/* Médinoc:
Suppression de variables globales. */
int case_droite(intconst laby [][100], int i, int j, int dir)
{
/* Médinoc:
On peut faire plus simple en choisissant correctement les valeurs de dir,
mais j'expliquerai à part. */
switch(dir)
{
case H:
return laby[j-1][i];
case D:
return laby[j][i+1];
case HD:
return laby[j][i+1];
case B:
return laby[j+1][i];
case HG:
return laby[j-1][i-1];
case G:
return laby[j][i-1];
case BG:
return laby[j+1][i-1];
case BD:
return laby[j+1][i+1];
default:
/* Normalement, on ne passe jamais ici,
   car dir a toujours l'une des huit valeurs testées. */
assert(0);
return1;
}/* switch */
}
 

/*la fonction suivante permet de connaitre la possibilité de passage
*suivant une direction*/
/* Médinoc:
Nom de fonction oublié.

Ouah, ici, c'est vraiment, mais alors vraiment le bordel.
Tu fais tes boucles for sur tes variables globales, mais en même temps, tu les modifies avec avance()...

J'ai viré toutes les globales, mais il se passe dans cette fonction des choses vraiment pourries,
et je ne suis pas assez fort pour déboguer ça...
*/
void UneFonction(void)
{
int laby[100][100];
/*m.donnees=laby;*/
int i,j;
int dir = 0; /* Médinco: dir n'était pas initialisé. */
 
for(i=0 ; i<100 ; i++)
{
for(j=0 ; j<100 ; j++)//( i<100 && j<100 )
{
{
/* Médinoc:
Alors ça, c'est vraiment, mais alors vraiment VRAIMENT moche.
Avec tous ces if sans accolades, c'est pratiquement impossible de s'y retrouver.
Surtout qu'il manquait deux accolades à la fin du fichier...
*/
if( case_droite(laby, i, j, dir) == 0)
// on se tourne vers la droite
// un moyen plus simple est : dir = ( dir+1 ) % 4;
if( dir == G )
dir = H;
else
{
dir = dir + 1;
// puis on avance d'une case
avance(&i, &j, dir);
}
else
if( case_devant(laby, i, j, dir) == 0)
{
avance(&i, &j, dir);
}
else
// on a plus le choix,
// on se tourne vers la gauche
if( dir == H )
dir = G;
else
dir = dir - 1;
// le moyen plus simple était d'écrire : dir = ( dir-1 ) % 4;
}
}
}
}

sur un petit programme, tes remarques sont inutiles

fleura
je veux réaliser un jeux de labyrinthe mais je trouve des problèmes,si c'est possible j'ai besoin d'aide

BONJOUR TT LE MONDE JE CHERCHE UN PSEUDO CODE DE PROBLEME DE LABYRINDE AVEC ALGORITME GENETIQUE PAR C++ MERCI D'AVANCE
salut tout le monde