Probleme de lecture d'algo pour creer un labyrinthe

Version imprimable

14/01/2009, 16h43
Flow_75

Probleme de lecture d'algo pour creer un labyrinthe

Bonjour,

J'ai trouvé sur ce forum, un pdf de cours sur les structures de données expliquant comment créer un labyrinthe (http://www.ai.univ-paris8.fr/~amsi/S...ts/cours07.pdf)

J'ai reussi à faire les points (1) et (2).
Mais j'ai pas compris ce que voulais dire cette instruction :

Citation:

Propager la valeur L[x][y-1] à partir du point(x,y-1)(en 4-connexité) pour les cases contenant la valeur L[x][y-1]

c'est surtout l'expression "en 4-connexité" que je ne comprend pas trop....

Enfin, merci de votre aide.
Flo
15/01/2009, 10h04
ToTo13

Bonjour,

dans un espace discret (comme par exemple une image), l'espace est divisé en carreaux (pour l'image les pixels).
D'une manière générale, deux points sont connexes s'il existe un chemin permettant de les relier.
Dans le cas d'une image, il y a principalement deux types de connexité appelé aussi voisinage : 4-connexité (deux pixels sont voisins si s'ils se touchent par un coté) et 8-connexité (deux pixels sont connexes s'ils se touchent pas au moins un angle).

Donc dans ton cas tu t'intéressera aux voisins qui sont 4-connexes, c'est-à-dire ceux qui sont : au dessus, au dessous, à gauche et à droite.

Il y a une bonne explication de tout cela dans la thèse de Christophe Lohou.

Merci de ta réponse.

Après avoir essayer de traduire l'algorithme (voir pdf de mon premier post).
J'ai fais ce code ci dessous, mais, ca me donne n'importe quoi.
Pourtant j'ai vérifié si je ne faisais pas n'importe quoi...

Si quelqu'un peut m'aider....

Code:

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
int main( int argc, char** argv )
    {
    const int dimX = X;
    const int dimY = Y;
 
    int laby[dimX][dimY];
    int k = 0;
    int NbCaseAZero = 1;
 
    srand((unsigned)time(NULL));
 
    for(int i = 0; i < dimX; i ++)
        {
        for(int j = 0; j < dimY; j ++)
            {
            if(i%2 == 1 && j%2 == 1)
                laby[i][j] = k++;
            else laby[i][j] = -1;
            }
        }
 
    for(int i = 0; i < dimX; i ++)
        {
        for(int j = 0; j < dimY; j ++)
            {
            if(laby[i][j] == -1)
                std::cout << "*";
            else std::cout << " ";
            }
        std::cout << std::endl;
        }
 
    while(NbCaseAZero < N * M)
        {
        int x,y;
        do{
            x = alea(dimX - 2) + 1 ;
            y = alea(dimY - 2) + 1;
 
            if(laby[x][y] == -1)
                break;
            }while(true);
 
        if(x%2 == 1)
            {
            int d = laby[x][y-1] - laby[x][y+1];
 
            if(d>0)
                {
                if(laby[x][y+1] == 0)NbCaseAZero +=3;
                laby[x][y] = laby[x][y+1];
                laby[x][y-1] = laby[x][y+1];
 
                if(laby[x-1][y-1] == laby[x][y-1])laby[x-1][y-1] = laby[x][y+1];
                if(laby[x+1][y-1] == laby[x][y-1])laby[x+1][y-1] = laby[x][y+1];
                if(laby[x][y-2]   == laby[x][y-1])laby[x][y-2]   = laby[x][y+1];
                }
 
            if(d<0)
                {
                if(laby[x][y-1] == 0)NbCaseAZero +=3;
                laby[x][y] = laby[x][y-1];
                laby[x][y+1] = laby[x][y-1];
 
                if(laby[x-1][y+1] == laby[x][y+1])laby[x-1][y-1] = laby[x][y-1];
                if(laby[x+1][y+1] == laby[x][y+1])laby[x+1][y-1] = laby[x][y-1];
                if(laby[x][y+2]   == laby[x][y+1])laby[x][y-2]   = laby[x][y-1];
                }
            }
 
        if(y%2 == 1)
            {
            int d = laby[x-1][y] - laby[x+1][y];
 
            if(d>0)
                {
                if(laby[x+1][y] == 0)NbCaseAZero +=3;
                laby[x][y] = laby[x+1][y];
                laby[x-1][y] = laby[x+1][y];
 
 
                if(laby[x-1][y+1] == laby[x-1][y])laby[x-1][y+1] = laby[x+1][y];
                if(laby[x-2][y]   == laby[x-1][y])laby[x-2][y] = laby[x+1][y];
                if(laby[x-1][y-1] == laby[x-1][y])laby[x-1][y-1] = laby[x+1][y];
                }
 
            if(d<0)
                {
                if(laby[x-1][y] == 0)NbCaseAZero +=3;
                laby[x][y] = laby[x-1][y];
                laby[x+1][y] = laby[x-1][y];
 
                if(laby[x+1][y+1] == laby[x+1][y])laby[x+1][y+1] = laby[x-1][y];
                if(laby[x+1][y-1] == laby[x+1][y])laby[x+1][y-1] = laby[x-1][y];
                if(laby[x+2][y]   == laby[x+1][y])laby[x+2][y]   = laby[x-1][y];
                }
            }
        }
    }

ps : la fonction "int alea(int n)" me renvoi un nombre aléatoire entre 0 et n.

Merci d'avance de votre aide.
Flo.

salut, c'est très simple:

en gros l'algo part d'un labyrinthe avec que des murs
à chaque itération on casse un mur, jusqu'à que toutes les cases du labyrinthe soient accessibles

je te montre l'algo tourner sur un petit exemple:
Code:

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 on part d'un labyrinthe avec "que des murs": ##### # m # #m#m# # m # ##### on casse un des m: ##### # # #m#m# # m # ##### puis encore un: ##### # # #m# # # m # ##### jusqu'à que toutes les cases soient accessibles: ##### # # # # # # m # #####