Algorithme Labyrinthe en c

Question

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 http://ilay.org/yann/articles/maze )
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.

mcdajjal · Accepted Answer

Bonjour,

Je relance ce post pour trouver de l'aide.
J'ai repris une partie du programme ci-dessus en modifiant certaines choses 
neanmoins je n'arrive pas a definir totalement un decoupage en 3 parties

(Main.c Labyrinthe.c Labyrinthe.h)

quelqu'un pourrait il m'aider a y voir plus clair

coucou747 · Answer

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

tiquent · Answer

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.

coucou747 · Answer

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

coucou747 · Answer

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).






  ______________________________________________________________________________
 |____ |______    __ |  ____ |__  ____  ___________________|  ____ |  __   |  _|
 |   |______ |_|__ |___|  _|__ |__ |  _|  __ |  __ |  ____ | |   |  _|  _| |   |
 | |______ |__ |  _|__ |  __ |__ |_|   | | |___| |___|  _|___| | |__ | |__ |_| |
 | |  _______| | |  ___| |  __ |__ |_|____ |__  __ |   |  _____|__ |_|__ |____ |
 | |______ |  _| |  __ | | |_____|______ |_____|__ |_| |____ |__  _|  ___|  _| |
 | |  __ |___|  _|__ | | |__ |  ____  _| |  ____ |__ |  __ |__ |__ | |   |  ___|
 |___|  _|    _|  ___|___| |___|   |__ |___|  ___| |___|  ___| |  _|  _| |__ | |
 |  _| |__ |__ |____ |  ____ | | |  _|  ___|____ |____ | |  ___|__ |___| |  _| |
 |__ |__ | | | |   |___|   | |___|__ |____ |   |__ |  _| | |__  _|__ |  _|__ | |
 |  ___| | | |___| | |  _|___|  __ |__  _| | |_____|__ | |__ |   |  ___|   | | |
 |  _____| |  ___| | |_________| |__ |   | | |__  __ |___|  _|_|___|   | |_| | |
 | |  _____|__ |  _|__  __ |  ____ | |_| | |__ |__ |__ |  _|   |  ___| |  ___| |
 | | |____    _| |   | |_____|  ___|____ |_____|  _|  _| |  _| | | |  _| |__  _|
 | | |   | | |  _| | |______ |__  ____ |______ | | | |  _____|_____| | |__ |   |
 | |___|___|_| |__ |______  _|___|   |____ |  _| |  _|_|   |  _______|  ___| | |
 |_____________|  _|   |  _|  __ | | |  _| | |__ |_______|___|__ |  ___|____ | |
 |  _|  __ |   |  ___| |__ | | |___| |  ___|_____|  ________ |  _|__ |  __ |_| |
 |__ | | | | | | |  _|__ |_| |  __ | |___|  __ |  ____ |   | |____ |___| | |   |
 |  _|__ |___| | |____ |_____| |  _|__  ___|  _|__ |  _| | |____ |  ____ |___| |
 |   |  _|    _|____ |__   |__ | |   |__ | |__ |  _|_____|__ | |  _|__ | | |  _|
 | |_____| | |  _____|  _|_____| | |__ |____ | | | |    _|  _|___|   |_____|__ |
 |__ |  ___|_|______ |__ |  _____| |____ |___| | | | | |  _|  _____|__ |   |  _|
 |  _|____________ |__ | |__ |  _|____ | |  ___| |___| |__ | |__  __ |___| | | |
 | | |    __ |   |  _|___|  _|__    _| | |____ |______ | | |_____| |____ |___| |
 | |___| | | | |_|__  ___| |__  _| |   |______ |  ___|__ |________  ___| |  __ |
 |_______| |__ |   |____ | |  _|  _| |_|   |__ | |   |  _|   |   |_______| | | |
 |________ |  _| |____  _|___| |__ |____ |__ | | | | | |__ | | |____ |  ___| | |
 |  __ |  _| | | |   |_|  _________|   | |  _|__ | | |_____| |   | | |__ |  _| |
 |   | |_______|___|___________|   | | |_| |_____| |_________| | | |_____|__ | |
 |_| | |  __ |   |  ____  _______|__ |_____|  _____|  __ |   | | |____    ___| |
 |  _| |__ |___| | |_____|   |______ |  __ |__ |  ___|  _| |_| | |   | | |   | |
 | |_______|  _| | |  _____|______ |_|__ |_____|  __ | |______ |___| | |_| | | |
 |  __ |__ |  ___| |__ | |    ___|_______|  __ | |  _| |  __ |__  _| |__ | |___|
 |__ |__ |__ |__   | | |___|__    __ |____ |  _| |__ | |__ | |___|  _|  _|____ |
 | | | |__ |_____|__ |______ | |__ |__ |  _|__ |__ | |__ | |_______| |     |  _|
 |  _| |  _|   |  _| |  _____|___| |  _| |   |__ |_| | | | |____   | | | |_| | |
 |__ | |__ | | |__  _|____ |__  ___|_____| |_|  _|  _| | | |  ___|___| |__ |__ |
 | |____ |___|__ |_____|  _|  _| |  __ |  _____|__ |  ___| |   |  __ |__ |__ | |
 |_____________|_____________|_______|_____________|_______|_|_____|_______|___|

kartajtn · Answer

//*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 
 
/*#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;
}
}
}
}

coucou747 · Answer

sur un petit programme, tes remarques sont inutiles

fleura2905 · Answer

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

yakouta86 · Answer

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

coucou747 · Answer

Bonjour,

J'ai lu un email que tu as envoyé à un autre administrateur CodeS-SourceS...
Tu veux que l'on fasse ton tp à ta place ?

Quel est ton soucis avec le découpage en trois parties ? Tu ne donnes aucun détail sur ce qui te pose problème là... la seule façon de t'aider est de faire ton projet à ta place, et ce n'est pas dans ma politique.

Cordialement,

Maxime

mcdajjal · Answer

J'ai trouvé les solutions a mes problemes c'est bon

Cordialement

McDajjal

Algorithme Labyrinthe en c

11 réponses

Votre réponse

Discussions similaires