Discussion :

[Myrne]

il compte le nombre de cases autour qui sont un 1.

Cet algorithme est en effet plus performant que ce que j'essayais de te faire faire =)

Je te donne un exemple de ce qu'il te manquait pour t'assurer d'avoir supprimé toutes les impasses:

Labyrinthe de départ (celui donné dans ton exemple):
0 1 1 1 1 1 1 1 1
0 0 0 0 0 1 1 1 1
0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 0
0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0

Après une première passe (le résultat peut varier en fonction de l'ordre dans lequel tu parcours toutes tes cases:

0 1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1 1
0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0

Il faut que tu refasses une passe pour continuer à virer les cases, et ce jusqu'à ce que le labyrinthe avant la passe et le labyrinthe après la passe soient égaux (signe qu'il n'y a plus d'impasse).

le code à implémenter serait donc le suivant, notant X ton labyrinthe:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
X=[0 1 1 1 1 1 1 1 1
0 0 0 0 0 1 1 1 1
0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 0
0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0]
 
X2=[];
 
while(X!=X2)
 
   X2=X;
   X=suppressionimpasses(X);
end

je ne suis pas sûr qu'un simple X!=X2 suffise pour une matrice et je n'ai pas Matlab pour vérifier, mais avec ça tu as l'idée. suppressionimpasses est la méthode que tu as implémentée.

Mais restes en à la proposition de Maleaume, elle devrait faire le travail bien plus rapidement.

[scienceapart]

!= signifie différent ?

[Myrne]

Oui, mauvais langage...

[scienceapart]

La condition while X~=X2 me fait comme erreur :

Matrix dimensions must agree.

Error in ==> cheminlepluscourt at 11
while X~=X2

EDIT : Enfin oui c'est logique vu que la matrice [] est une matrice vide donc elle ne peut avoir de dimensions.

[scienceapart]

Si je regarde la proposition de Maleaume, je n'arrive pas à la retranscrire en language MATLAB. :s

[maleaume]

quelle partie te pose probleme sous matlab?

[scienceapart]

Ben traduire les void, les return, le DeleteDeadLock(x,y) etc. en MATLAB vu que tu a exprimé en language C si je me trompe pas.

[Myrne]

Les void tu t'en passes, pas utile pour Matlab, les return tu peux les utiliser, deletedeadlock sera une sous-fonction en Matlab, donc tu la définis avec

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

function paramètresdesortie=deletedeadlock(paramètresdentrée)

.

[maleaume]

j ai modifier une coquille dans le code ligne 29:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

if(Image(x + (y-1)*sizeX) == 0)

alors qu il falait

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

if(Image(x + (y+1)*sizeX) == 0)

sinon je viens de tester en C# un pettit programme qui prend en entree un labyrinthe selon ton format, et ca marche


oui l important ici c est lalgorithme, apres à toi de le transcrire dans le langages qui te convient

[maleaume]

tiens, le programme est telechargeable

http://www.megaupload.com/?d=AQWJ896D

tu renomme le fichier en enlevant l extansion ".remove" et tu l execute.
J ai ralenti la vitesse d execution pour que tu puisses voir le fonctionnement de l'algo

[Myrne]

à noter qu'avec cette méthode, si plusieurs chemin sont possibles pour arriver à la sortie, il ne restera à la fin que ces chemins mais tu ne sauras pas lequel des deux est l'optimal =)

[maleaume]

tout a fait, jallais meme le poster en commentaire, tu as été plus rapide!
Si il y a une boucle par exemple dans le labyrinthe (chemins qui se croisent) c pas dit que tu puisse sortir (tourner en rond). La dessus il faudrait rajouter un petit algo de calcul de longueur de chemin pour pouvoir eliminer des bouclages qui ne servent a rien et savoir prendre le chemin le plus court

[scienceapart]

Merci maleaume, je pense que le plus dur est de déterminer les chemins, après pour dire lequel est le plus court, c'est moins dur je pense. Juste une dernière question : sum++ se traduit comment en MATLAB?

[maleaume]

c est lincrementation d une variable
i = i+1;

[maleaume]

mais comme deja dit, tu peux supprimer tout ce qui concerne cette variable, car la condition de fin est toujours verifier.
donc le code se résume a

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 static  void DeleteDeadLock(int x, int y)
        {
	        int result = 0;
	        int sum = 0;
	        //regarde le pixel du dessus:
	        if(lab[x+(y-1)*N] == 0 )
		        result = 1;
 
	        //regarde a droite:
	        if(lab[x+1 + y*N] == 0)
	           if(result!= 0) return;  //on a deja trouver un 0, donc 2 zero ce n est //pas une impasse pas la peine de continuer
	           else result = 2;
 
 
	        //regarde en bas:
            if (lab[x + (y + 1) * N] == 0)
                if (result != 0) return;
                else result = 3;
 
	        //regarde a hauche:
	        if(lab[x-1 + y*N]== 0)
	           if(result!= 0) return;
	           else result = 4;
 
 
	        //en toute logique si on arrive ici, 
	        //c est que c est une impasse donc 3 pixel a 1 et 1 pxl a 0
			        lab[x+y*N] = 1;
 
			        switch(result)
			        {
			          case 1: DeleteDeadLock(x,   y-1); break;
			          case 2: DeleteDeadLock(x+1, y);break;
			          case 3: DeleteDeadLock(x,   y+1);break;
			          case 4: DeleteDeadLock(x-1, y);break;
			        }
        }

[scienceapart]

Finalement, je vais revenir à mon algo de départ parce que je comprend pas vraiment le tien maleaume. :s

Je fais un autre algo :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function X=testvoisins(X)
[n p]=size(X);
for i=2:(n-1)
    for j=2:(p-1)
        while X(i,j)==0
        if X(i,j)==0 && X(i,j-1)+X(i-1,j)+X(i,j+1)==3;
            X(i,j)=1;
        elseif X(i,j)==0 && X(i,j-1)+X(i+1,j)+X(i,j+1)==3;
            X(i,j)=1;
        elseif X(i,j)==0 && X(i,j+1)+X(i+1,j)+X(i-1,j)==3;
            X(i,j)=1;
        end
        end
    end
end
end

Mais bon le while fait planter et même en établissant un X2 comme a dit Myrne auparavant en mettant X2=[] ben cela marche pas.

[maleaume]

mon algo est recursif, c est peut etre cela qui te dérange.
Apres si c estun probleme de compréhension, je peut toujours t expliquer,
si c est un probleme de transcription de langage, ca ca peut toujours se travailler

de plus dans ton algo je vois

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 while X(i,j)==0
        if X(i,j)==0 && X(i,j-1)+X(i-1,j)+X(i,j+1)==3;
            X(i,j)=1;
        elseif X(i,j)==0 && X(i,j-1)+X(i+1,j)+X(i,j+1)==3;
            X(i,j)=1;
        elseif X(i,j)==0 && X(i,j+1)+X(i+1,j)+X(i-1,j)==3;
            X(i,j)=1;
        end
        end

tu repete trop de fois cette meme condition celle de ton while est suffisante.

pour ce qui suit G= Gauche, D = droite, H = haut, B = bas.
ton premier if regarde: le second le troisieme
--------- H--------------------H
------G . ------------------- . D-------------------G . D
-------- B------------------- B-------------------------B


il te manque une configuration.
de plus niveau opti c est pas le top ton if else calcule trop souvent la meme chose.
le miens fais juste compter combien de 0 j ai autour de moi et me donne ca position par rapport a ma position (x,y) courante. SI je trouve 1 fois le zero, j ia pas besoin de continuer

la fonction switch en C est comme un gros if else pour toi

[scienceapart]

Explique moi alors s'il te plait.

[scienceapart]

Avec le mien, on peut pas arranger ? Parce que le tien je comprend mais j'arrive pas à retranscrire.

[Myrne]

Il y a un switch en matlab que tu peux utiliser,

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

help switch

Il me semble que le code de Maleaume est bien commenté et compréhensible =)

En gros ce qu'il faut que tu fasses, en notant X ton labyrinthe et 'case' le couple de coordonnées (i,j) de la case en cours:

- Une fonction 'main' qui parcourt toutes les cases de ton tableau. Si la case est un zéro, elle appelle la fonction deletedeadlock de la façon suivante:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

X=deletedeadlock(X,case)

- Une fonction 'deletedeadlock' définie de la façon suivante:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
function X=deletedeadlock(X,case)
%code de la fonction

Dans cette fonction, tu définis une variable 'result' (initialisée à 0) qui permettra de savoir où sont situés les 0 autour de la case en cours.

D'abord on regarde en haut. Si c'est un zéro, on assigne 1 à 'result'.

Puis on regarde à droite, si c'est un zéro, on regarde la valeur de 'result' : si elle est à zéro, c'est qu'on a pas encore trouvé d'autres couloir, on assigne donc 2 à 'result'. Si elle n'est PAS à zéro, c'est qu'il y avait déjà un autre couloir, et donc la case en cours n'est pas une impasse, on peut arrêter le programme ici (fontion 'return').

On regarde en bas. Idem si c'est un zéro on regarde la valeur de 'result' et on agit de la même façon que précédemment.

Enfin, on regarde à gauche, même raisonnement.

Ensuite, si tu as fait toutes ces vérifs et que tu arrives jusque là, c'est que c'est bien une impasse. Tu peux donc assigner un 1 à la case en cours:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

X(case)=1;

Ensuite, tu sais dans quelle direction est le zéro de l'impasse dans laquelle tu te trouves: elle est définie par la valeur de 'result'.

Tu fais donc une itération en appelant de nouveau 'deletedeadlock' sur la nouvelle case définie par 'result', ceci avec la fonction switch:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
switch (result)
case 1
   X=deletedeadlock(X,caseaudessus);
case 2
   X=deletedeadlock(X,caseàdroite);
case 3
   X=deletedeadlock(X,caseendessous);
case 4
   X=deletedeadlock(X,caseàgauche);
end

Si tu ne vires pas les bords et gardes les murs de ton labyrinthes, et que tu parcours les cases intérieures (de 2 à L-1 et de 2 à C-1), tu effaceras ainsi toutes les impasses de ton labyrinthe sans avoir à t'embêter avec les conditions de bord.