Discussion :

[NilsB]

Bonjour à tous,
je suis étudiant en première année de licence info et j'ai un projet à rendre.
Je dois créer un jeu où le but est de s'enfuir d'un labyrinthe créer aléatoirement.
Après deux jours d'essai, je n'ai pas réussi a créer moi même le labyrinthe. J'ai donc recherché sur internet et j'ai trouvé un superbe algorithme:

1. Initialisation :
— Une matrice L[N][M] donnée ;
—k←0 ;
— Pour i de 0 à N faire :
— Pour j de 0 à M faire :
— Si (i impair et j impair) alors :
—L[i][j]←k;
—k=k+ 1 ;
— Sinon :
—L[i][j]←-1 ;
— FIN “Si” ;
— FIN “Pour” ;
— FIN “Pour” ;
2. Pour NbCasesAZero, le nombre de cases `a 0 :
NbCasesAZero= 1 ;
3. Tant que NbCasesAZero < N×M faire :
— Prendre au hasard (x, y) tel que :
L[x][y] =−1 et (x impair ou y impair) ;
— Si x impair alors :
— d←L[x][y−1]−L[x][y+ 1] ;
— Si d >0 alors :
—L[x][y]←L[x][y+ 1] ;
— 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];
— Sinon, si d <0 alors :
— L[x][y]←L[x][y−1] ;
— 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];
— Sinon (y impair) :
— d←L[x−1][y]−L[x+ 1][y] ;
— Si d >0 alors :
—L[x][y]←L[x+ 1][y] ;
— Propager la valeur L[x+1][y] à partir du point (x-1, y) (en 4-connexité) pour les cases contenant la valeur L[x-1][y];
— Sinon, si d <0 alors :
— L[x][y]←L[x−1][y] ;
— Propager la valeur L[x-1][y] à partir du point (x+1, y) (en 4-connexité) pour les cases contenant la valeur L[x+1][y];
4. FIN “Tant que”.


Mais je n'ai absolument aucunes idées de ce que veux dire:
- "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];"
Et je n'ai rien trouvé sur internet. Si quelqu'un pourrait m'expliquer ce qu'il faut faire!
Merci d'avance

[NilsB]

Désolé pour l'indentation, j'avais essayé de mettre des espaces, mais visiblement le site ne les a pas pris en compte...

[Flodelarab]

Bonjour



Je croyais que faire une recherche Google était à la portée d'un élève de licence.
D'autant plus que la n-connexité est une entrée de wikipédia.

Le changement de valeur va faire tâche d'huile. Auprès des voisins. A partir de la case à l'opposé de la case courante.

[NilsB]

Merci de m'avoir, répondu, mais pas la peine d'être offensant. Pensez bien, que si j'avais compris ce que disais la page Wikipédia sur les n-connexité, je ne serais pas en train de poser la question. Cette notion n'est absolument pas de mon niveau.
De plus je n'ai absolument pas compris votre conseil. Que veux dire "va faire tâche d'huile"?
Et qu'appelez vous " la case opposé de la case courante"?

[Flodelarab]

Qu'est-ce que la 4-connexité ?
n-connexité avec n=4
Qu'est-ce que la n-connexité ?
"la n-connexité est une généralisation de la connexité par arcs"
Qu'est-ce que la connexité par arcs ? (en plus, il y a un lien hypertexte)
"(...) est dit connexe par arcs si deux points quelconques peuvent toujours être reliés par un chemin."

La 4-connexité est une façon snob de désigner 4 voisins.
C'est ça qui est hors de portée d'un étudiant en licence ? Faut pas pousser.

Et qu'appelez vous " la case opposé de la case courante"?

La case courante est évidemment celle de coordonnées (x,y).
Le code parle de L[x][y+ 1] donc de la case de coordonnées (x,y+1); celle du dessous, manifestement.
La case à l'opposé est donc celle du dessus (x,y-1) dans laquelle il faut propager la valeur de la case en (x,y+1), pour (x,y-1) et tous ces voisins ayant la même valeur.


Sur Wikipedia, comme dans le code, il suffit de lire.

[NilsB]

Merci bien pour ton aide, au final j'ai trouvé un autre moyen de générer aléatoirement le labyrinthe...

[Flodelarab]

Bonne nouvelle. Veux-tu partager cette solution ici ?