function labyrinthe(lar,hau,style)
global noeud laby
% construction d'un labyrinthe
if nargin==0
	lar=4;
	hau=4;
	style='2d';
end

laby.largeur=lar;
laby.hauteur=hau;
laby.nbre_murs=(laby.largeur-1)*laby.hauteur+laby.largeur*(laby.hauteur-1);

% murs verticaux
indice_cellule=1;
for li=1:laby.hauteur
	for co=1:laby.largeur-1
		no_mur=(li-1)*(laby.largeur-1)+co;
		mur(no_mur).cellule_1=indice_cellule;
		mur(no_mur).cellule_2=indice_cellule+1;
		mur(no_mur).ouvert=0;
		mur(no_mur).segment.x=[co co];
		mur(no_mur).segment.y=[li-1 li];
		indice_cellule=indice_cellule+1;
	end
	indice_cellule=indice_cellule+1;
end

% murs horitontaux
indice_cellule=1;
no_deb=no_mur;
for li=1:laby.hauteur-1
	for co=1:laby.largeur
		no_mur=(li-1)*(laby.largeur)+co+no_deb;
		mur(no_mur).cellule_1=indice_cellule;
		mur(no_mur).cellule_2=indice_cellule+laby.largeur;
		mur(no_mur).ouvert=0;
		mur(no_mur).segment.x=[co-1 co];
		mur(no_mur).segment.y=[li li];
		indice_cellule=indice_cellule+1;
	end
end

% définition du labyrinthe initial (murs fermés)
laby.murs=mur;

% définition des ensembles de Tarjan: chaque cellule au départ
% n'est connectée qu'à elle-même; elle pointe sur rien (-1)
nbre_cellules=laby.largeur*laby.hauteur;
noeud=zeros(1,nbre_cellules)-1;

% ouverture des murs

% on mélange les murs au hasard
[el_tries, indices]=sort(rand(1,laby.nbre_murs));
%%%% indices=[12 2 21 7 9 15 1 4 16 23 3 17 24 5 10 18 6 8 11 19 13 22 14 20];
for i=1:laby.nbre_murs
	% 2 cellules séparées par le mur
	cel_1=laby.murs(indices(i)).cellule_1;
	cel_2=laby.murs(indices(i)).cellule_2;
	% cellules non connectées
	if ~meme_ensemble(cel_1,cel_2)
		connecte(cel_1,cel_2,indices(i))
	end
end

% dessin de la grille initiale
if strcmp(style,'2d')
	dessiner2d(laby)
else
	dessiner3d(laby)
end
%%% fin

function dessiner2d(laby)
largeur=laby.largeur;
hauteur=laby.hauteur;

h=plot(0,0);
hold on
delete(h)

% murs 
for i=1:laby.nbre_murs
	if ~laby.murs(i).ouvert
		x=laby.murs(i).segment.x;
		y=laby.murs(i).segment.y;
		plot(x,y)
	end
end


% bordure
plot([0 largeur largeur],[0 0 hauteur-1],'linewidth',3)
plot([largeur 0 0],[hauteur hauteur 1],'linewidth',3)
axis equal
axis off
hold off
%%% fin dessiner2d

function dessiner3d(laby)
largeur=laby.largeur;
hauteur=laby.hauteur;

h=plot3(0,0,0);
hold on
delete(h)
couleur=[0.5 0.5 0.5];

% murs 
for i=1:laby.nbre_murs
	if ~laby.murs(i).ouvert
		x=laby.murs(i).segment.x;
		y=laby.murs(i).segment.y;
		X=[x fliplr(x)];
		Y=[y fliplr(y)];
		Z=[0 0 1 1];
		fill3(X,Y,Z,couleur)
	end
end


% bordure & fond
fill3([0 largeur largeur 0],[0 0 hauteur hauteur],[0 0 0 0],couleur+0.1)
fill3([0 largeur largeur 0],[0 0 0 0],[0 0 1 1],couleur)
fill3([largeur largeur largeur largeur],[0 hauteur-1 hauteur-1 0],[0 0 1 1],couleur)
fill3([0 0 0 0],[1 hauteur hauteur 1],[0 0 1 1],couleur)
fill3([0 largeur largeur 0],[hauteur hauteur hauteur hauteur],[0 0 1 1],couleur)
axis equal
axis off
hold off
set(gcf,'renderer','opengl','color','w')
rotate3d on
%%% fin dessiner3d

function res=meme_ensemble(cel_1,cel_2)
test_1=obtient_representant(cel_1);
test_2=obtient_representant(cel_2);
if  (test_1==test_2) 
	res=1;
else
	res=0;
end
%%% fin meme_ensemble

function connecte(cel_1,cel_2,i)
global noeud laby
test_1=obtient_representant(cel_1);
test_2=obtient_representant(cel_2);
noeud(test_1)=test_2;
laby.murs(i).ouvert=1;
%%% fin connecte

function cel_out=obtient_representant(cel_in)
global noeud
deb=noeud(cel_in);
if deb==-1
	cel_out=cel_in;
else
	avant=cel_in;
	while deb~=(-1)
		avant=deb;
		deb=noeud(deb);
	end
	cel_out=avant;
	% on optimise
	
	deb=noeud(cel_in);
	avant=cel_in;
	while deb~=(-1)
		noeud(avant)=cel_out;
		avant=deb;
		deb=noeud(deb);
	end
end
%%% fin obtient_representant
