Matrice carrée problème

Version imprimable

24/10/2010, 12h17
Chipseater

Matrice carrée problème
Bonjour, je suis un petit nouveau dans le monde de la programmation. Python est mon premier langage dans la matière.

Alors voila: dans le cadre d'un mini projet, je dois construire et afficher un labyrinthe sous forme de matrice carrée, et ensuite remplir l'intérieur du labyrinthe de façon aléatoire grâce à une donnée entrée par l'utilisateur.

Je dois donc avoir quelque chose qui ressemble à ceci:

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

J'arrive à afficher ceci:

0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

grâce a ce bout de code:
Code:

1 2 3 4 5 lab = [[0 for i in range(5)] for j in range(5)] for i in range(n): for j in range(n): print lab[i][j], print
Mais je n'arrive pas a remplacer mes zéros pour arriver au résultat montré en premier.

J'ai déjà essayé pas mal de trucs mais apparemment je dois mal comprendre comment ca fonctionne!

Si quelqu'un pouvait m'éclairer un peu la dessus ca m'aiderait beaucoup!
Merci.

Bonjour,

Une des solutions possibles:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
n = 5
lab = []
for i in range(n):
    lab.append([])
    for j in range(n):
        if i==0 or i==n-1 or j==0 or j==n-1:
            lab[-1].append(1)
        else:
            lab[-1].append(0)
 
for i in range(n):
    for j in range(n):
        print lab[i][j],
    print
 
1 1 1 1 1
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1
1 1 1 1 1

Tyrtamos

24/10/2010, 14h14
Chipseater

Merci beaucoup pour la réponse rapide et précise, c'est exactement ça!:)

Si j'ai encore une question je reviendrai;)

Au risque de paraître ridicule, je pose une dernière question.

J'ai donc :

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
def creer_labyrinthe(n,m):
    lab = []
    for i in range(n):
        lab.append([])
        for j in range(n):
            if i==0 or i==n-1 or j==0 or j==n-1:
                lab[-1].append('x')
            else:
                lab[-1].append(' ')
 
 
    for i in range(n):
         for j in range(n):
 
             print lab[i][j],
         print
    res = ''
    return res
 
 
 
 
 
 
dimension = raw_input("Donnez la dimension n du labyrinthe: \n")
n = int(dimension)
 
murs = raw_input("Donnez le nombre m de murs interieurs: \n")
m = int(murs)
 
print "Voici un tel labyrinthe:"
 
print creer_labyrinthe(n,m)

m étant le nombre de murs disposés de façon aléatoire à l'intérieur du labyrinthe. Il ne me manque plus que ça...Mais je n'y arrive pas plus:(

Bonjour,

Tout d'abord, tu ferais mieux de restructurer un peu ton code, en séparant la création du labyrinthe et son affichage en deux fonctions:
- la fonction creer_labyrinthe devrait retourner le labyrinthe créé (liste lab)
- une fonction afficher_labyrinthe qui reçoit le labyrinthe en argument et l'affiche.

Pour la création de murs aléatoires, j'imagine que tu penses à quelque chose comme ceci (en pseudo-code):
Code:

1 2 3 4 5 6 Répéter m fois: Répéter: choisir deux nombres (x et y) aléatoirement entre 1 et (n-2) inclus Tant qu il y a déjà un mur en lab[x][y] Mettre un mur en lab[x][y]
Pour les nombres aléatoires, il y a la fonction randint du module random.

Ce qui est un peu gênant avec l'algorithme ci-dessus, c'est que le nombre d'étapes n'est pas borné.

Cet autre algorithme ne présente pas ce problème:
Code:

1 2 3 4 5 6 Créer la liste des coordonnées de toutes les cases du labyrinthe: [(1,1), (1,2), .., (1,n-2), (2,1), .., (2,n-2), .., (n-2,n-2)]. Mélanger cette liste (fonction shuffle du module random) Extraire les m premiers éléments de la liste mélangée et mettre un mur à ces coordonnées
Les deux algorithmes sont équivalents au niveau du résultat, mais risquent de créer des zones déconnectées l'une de l'autres.
Pour éviter cela il existe d'autres algorithmes, permettant de créer des labyrinthes "parfaits", mais ils sont un peu plus complexes...

24/10/2010, 20h02
PauseKawa

Bonsoir,

Citation:

Envoyé par dividee

il existe d'autres algorithmes, permettant de créer des labyrinthes "parfaits"

Un exemple ou des liens ?

Bon code.
24/10/2010, 20h57
wiztricks

Google est ton ami :http://www.ilay.org/yann/articles/maze/
24/10/2010, 23h13
Chipseater

Rien à faire je me suis encore acharné dessus, mais je n'arrive vraiment pas cette partie.

Si m=1 je dois arriver par exemple à quelque chose comme ca:

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

Donc un mur par ligne, choisi aléatoirement par la fonction random.randint, mais il me retourne toujours des choses un peu bizarre...

J'ai bien compris pour la boucle permettant de répéter m fois l'opération(du mois j'espère, au sinon je suis desespérant), mais le reste pose encore problème:(
24/10/2010, 23h41
kevgen

j'ai EXACTEMENT le même problème ! ^^

je m'acharne dessus depuis ce matin, je suis parvenu a dessiner ma matrice carrée entourée de 1 remplie de 0, mais après pour avoir m murs par ligne ça devient corsé ...
si m=1 ça va il me met bien 1 mur par ligne sur une position aléatoire, mais si m=2 il ne me met pas systématiquement 2 murs , parfois un seul sur une ligne et sur la ligne d'après 2...
04/11/2010, 01h42
N.tox
Citation:

Envoyé par Chipseater

Si m=1 je dois arriver par exemple à quelque chose comme ca:
[...]
Donc un mur par ligne, choisi aléatoirement par la fonction random.randint, mais il me retourne toujours des choses un peu bizarre...

Je me dis que le raisonnement qui consiste à avoir m murs dans une ligne à des positions aléatoires, possède une faille majeure : on pourrais très bien se retrouver avec la chose suivante :

111111
101101
110111
110101
100011
111111

Or, à moins que les "déplacement diagonaux" soient autorisés, et quand bien même, on pourrais très facilement se retrouver avec des pièces isolées/bloquées... Et éviter cela en continuant sur ta lancée te mènera sûrement à une complexification assez inutile.

Le lien donné par Wiztricks est très bon, et donne des résultats probants. et l'algorithme cité ci-dessous est relativement simple à mettre en place. Mieux vaut quand même pour toi (pour l'instant) d'ignorer les termes de pointeurs et de bits, les premiers n'existant pas (vraiment) en python et les deuxièmes impliquant des manipulations ni naturelles, ni intuitives.

Citation:

Les structures de données
Le labyrinthe est composé de cellules et de murs. Ces deux concepts sont équivalents. Les cellules sont limitées par des murs et les murs limitent les cellules. Il nous faut donc choisir quel concept modéliser.

Étant donné que nous parcourons les pièces, il me parait plus simple, a priori de modéliser les cellules plutôt que les murs.

En première approche on pourrait comparer les ouvertures à des passages et de voir les portes comme des pointeurs vers d'autres cellules. Chaque cellule serait composée de 4 pointeurs. Une porte serait un pointeur vers une cellule voisine, et un mur un pointeur nul.

Cette démarche fonctionne à merveille, mais si l'on regarde de plus près, nous n'en avons pas besoin.

Nous avons besoin de coder l'état des murs Ouvert/Fermé. Il y a 4 portes par cellule, et chaque porte n'a que deux états. Nous n'avons donc besoin que de 4 bits par cellules.

http://www.ilay.org/yann/articles/maze/cell.png

Il nous faudra aussi vraisemblablement savoir si nous sommes déjà passés dans une cellule. Ce qui rajoute 1 bit.
Citation:
Méthode exhaustive
http://www.ilay.org/yann/articles/maze/algo2.gif

On part d'un labyrinthe ou toutes les portes sont fermées.
Chaque cellule contient une variable booléenne « state » qui indique si la cellule est rattachée au labyrinthe ou non. Toutes les variables sont à faux (0).
On choisi une cellule, on met son état à vrai (1).
Puis on regarde quels sont les cellules voisines disponibles et dont l'état est à 0 et on stocke la position en cours.
S'il y a au mois une possibilité, on en choisi une au hasard, on ouvre la porte et on recommence avec la nouvelle cellule.
S'il n'y en pas, on revient à la case précédente et on recommence.
Quand on est revenu à la case départ et que qu'il n'y a plus de possibilités, le labyrinthe est terminé
Je suis tenté de te montrer le code que j'ai pondu, qui est une application à la lettre de cet algorithme, mais j'ai peur qu'il te paraisse un brin obscur de par des utilisations de concepts intermédiaires, alors qu'on peut parfaitement y arriver avec les concepts basique que l'on apprend lorsque l'on débute. Déjà que la génération aléatoire d'un labyrinthe, d'après moi, n'est peut-être pas un choix des plus adapté pour un débutant... Mais cela est tout à ton honneur.