Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
je ne comprend pas
3 views
Skip to first unread message
kurtz le pirate
Feb 25, 2012, 3:12:01 AM2/25/12
to
bonjour,
extrait d'un code trouvé sur le net :
http://taskboy.com/blog/static/Simple_maze_generation_in_Perl_.html
...
my $maze = [];
for (my $r=0; $r < $max_row; $r++) {
for (my $c=0; $c < $max_col; $c++) {
push @{$maze->[$r]},{'visited' => 0,'bottom' => 1,'right' => 1,};
}
}
...
...
if ($row == 0) {
push @found, [$row + 1, $col] unless $maze->[$row +
1]->[$col]{'visited'};
}
...
deux choses :
* on pousse dans le tableau 'found' /quelque chose/ sauf si dans le
$maze->[$row + 1]->[$col], la clé {'visited'} est à 1 ?
c'est bien ça ?
* je ne suis pas sur de comprendre ce qui est poussé dans le tableau.
ne faudrait-il pas écrire :
push @found, $maze[$row, $col] unless ...
ou
push @found, $maze->[$row]->[$col] unless ...
et c'est bien tout le hash qui est poussé ?
$found[x] = {'visited' => 0,'bottom' => 1,'right' => 1,}
J'aimerai bien comprendre :(
Merci de votre aide.
--
klp
Nicolas George
Feb 25, 2012, 4:21:45 AM2/25/12
to
kurtz le pirate , dans le message
<kurtzlepirate-CD4...@news-4.proxad.net>, a écrit :
> * on pousse dans le tableau 'found' /quelque chose/ sauf si dans le
> $maze->[$row + 1]->[$col], la clé {'visited'} est à 1 ?
> c'est bien ça ?
Oui.
> * je ne suis pas sur de comprendre ce qui est poussé dans le tableau.
> ne faudrait-il pas écrire :
> push @found, $maze[$row, $col] unless ...
> ou
> push @found, $maze->[$row]->[$col] unless ...
>
> et c'est bien tout le hash qui est poussé ?
> $found[x] = {'visited' => 0,'bottom' => 1,'right' => 1,}
Non, ce qui est poussé, c'est une référence sur un tableau de deux éléments
qui code les coordonnées de la case.
> J'aimerai bien comprendre :(
Ce code est assez médiocre à de nombreux points de vue (les structures de
données sont un gaspillage énorme, l'algorithme n'est pas implémenté de
manière très efficace, et il y a beaucoup de lourdeur dans le style.
Je te conseille plutôt de lire le paragraphe qui décrit l'algorithme (« the
real work happens in the next bit of code » et d'essayer d'implémenter
toi-même.
Au niveau structure de données, je te conseille ceci :
- Les coordonnées des cases vont de 1 à W et de 1 à H, avec x=0, x=W+1, y=0
et y=H+1 des rangées de fausses cases qui t'évitent les conditions de
bord (tu les marques comme déjà visitées au tout début, et c'est fini).
- La case (x, y) est codée par l'entier x+y*(W+2).
- Un tableau $visited[$n] qui te dit si la case $n est visitée.
Un second tableau $right[$n] qui te dit si tu as un mur à droite de la
case $n (et donc à gauche de la case $n+1).
Et un troisième tableau $down[$n] qui te dit si tu as un mur en dessous de
la case $n (et donc au dessus de la case $n+(W+2)).
<kurtzlepirate-CD4...@news-4.proxad.net>, a écrit :
> extrait d'un code trouvé sur le net :
> http://taskboy.com/blog/static/Simple_maze_generation_in_Perl_.html
Bof.
> http://taskboy.com/blog/static/Simple_maze_generation_in_Perl_.html
> * on pousse dans le tableau 'found' /quelque chose/ sauf si dans le
> $maze->[$row + 1]->[$col], la clé {'visited'} est à 1 ?
> c'est bien ça ?
> * je ne suis pas sur de comprendre ce qui est poussé dans le tableau.
> ne faudrait-il pas écrire :
> push @found, $maze[$row, $col] unless ...
> ou
> push @found, $maze->[$row]->[$col] unless ...
>
> et c'est bien tout le hash qui est poussé ?
> $found[x] = {'visited' => 0,'bottom' => 1,'right' => 1,}
qui code les coordonnées de la case.
> J'aimerai bien comprendre :(
données sont un gaspillage énorme, l'algorithme n'est pas implémenté de
manière très efficace, et il y a beaucoup de lourdeur dans le style.
Je te conseille plutôt de lire le paragraphe qui décrit l'algorithme (« the
real work happens in the next bit of code » et d'essayer d'implémenter
toi-même.
Au niveau structure de données, je te conseille ceci :
- Les coordonnées des cases vont de 1 à W et de 1 à H, avec x=0, x=W+1, y=0
et y=H+1 des rangées de fausses cases qui t'évitent les conditions de
bord (tu les marques comme déjà visitées au tout début, et c'est fini).
- La case (x, y) est codée par l'entier x+y*(W+2).
- Un tableau $visited[$n] qui te dit si la case $n est visitée.
Un second tableau $right[$n] qui te dit si tu as un mur à droite de la
case $n (et donc à gauche de la case $n+1).
Et un troisième tableau $down[$n] qui te dit si tu as un mur en dessous de
la case $n (et donc au dessus de la case $n+(W+2)).
Paul Gaborit
Feb 25, 2012, 4:46:34 AM2/25/12
to
À (at) Sat, 25 Feb 2012 09:12:01 +0100,
kurtz le pirate <kurtzl...@yahoo.fr> écrivait (wrote):
> ...
> my $maze = [];
> for (my $r=0; $r < $max_row; $r++) {
> for (my $c=0; $c < $max_col; $c++) {
> push @{$maze->[$r]},{'visited' => 0,'bottom' => 1,'right' => 1,};
> }
> }
> ...
> ...
> if ($row == 0) {
> push @found, [$row + 1, $col] unless $maze->[$row +
> 1]->[$col]{'visited'};
> }
> ...
>
> deux choses :
>
> * on pousse dans le tableau 'found' /quelque chose/ sauf si dans le
> $maze->[$row + 1]->[$col], la clé {'visited'} est à 1 ?
> c'est bien ça ?
exemple).
Au passage : la deuxième flèche ainsi que les apostrophes autour de
visited ne sont pas indispensables. On aurait pu écrire :
push @found, [$row + 1, $col]
> * je ne suis pas sur de comprendre ce qui est poussé dans le tableau.
> ne faudrait-il pas écrire :
> push @found, $maze[$row, $col] unless ...
> ou
> push @found, $maze->[$row]->[$col] unless ...
>
> et c'est bien tout le hash qui est poussé ?
> $found[x] = {'visited' => 0,'bottom' => 1,'right' => 1,}
tableau (anonyme) qui contient deux valeurs ($row+1 et $col).
--
Paul Gaborit - <http://perso.mines-albi.fr/~gaborit/>
Perl en français - <http://perl.mines-albi.fr/>
Nicolas George
Feb 25, 2012, 5:05:43 AM2/25/12
to
Nicolas George , dans le message
<4f48a828$0$23174$426a...@news.free.fr>, a écrit :
cases dans les cellules de coordonnées paires et les marques pour les murs
entre. Ça simplifie un peu le code.
Sans cette optimisation, voici mon implémentation :
#!/usr/bin/perl
use strict;
use warnings;
no warnings "recursion";
use integer;
my $w = 25;
my $h = 16;
my $s = $w + 2;
my @visited;
my @right;
my @down;
for my $x (0 .. $w + 1) {
$visited[$x] = $visited[$x + ($h + 1) * $s] = 1;
}
for my $y (0 .. $h + 1) {
$visited[$y * $s] = $visited[$w + 1 + $y * $s] = 1;
}
sub make_maze($);
sub make_maze($) {
my ($c) = @_;
while(1) {
my @next = grep { !$visited[$_] } ($c + 1, $c - 1, $c + $s, $c - $s);
last unless @next;
my $n = $next[int(rand @next)];
$visited[$n] = 1;
$right[$c] = 1 if $n == $c + 1;
$right[$n] = 1 if $n == $c - 1;
$down[$c] = 1 if $n == $c + $s;
$down[$n] = 1 if $n == $c - $s;
make_maze $n;
}
}
make_maze int(rand($w) + 1) + int(rand($h) + 1) * $s;
for my $y (0 .. $h) {
if($y > 0) {
my $c = $y * $s;
for my $x (0 .. $w) {
print " " if $x > 0;
print $right[$c++] ? " " : "|";
}
print "\n";
}
my $c = 1 + $y * $s;
for my $x (1 .. $w) {
print "+", $down[$c++] ? " " : "--";
}
print "+\n";
}
<4f48a828$0$23174$426a...@news.free.fr>, a écrit :
> - Un tableau $visited[$n] qui te dit si la case $n est visitée.
> Un second tableau $right[$n] qui te dit si tu as un mur à droite de la
> case $n (et donc à gauche de la case $n+1).
> Et un troisième tableau $down[$n] qui te dit si tu as un mur en dessous de
> la case $n (et donc au dessus de la case $n+(W+2)).
On peut fusionner les trois tableaux en un, en mettant les marques pour les
> Un second tableau $right[$n] qui te dit si tu as un mur à droite de la
> case $n (et donc à gauche de la case $n+1).
> Et un troisième tableau $down[$n] qui te dit si tu as un mur en dessous de
> la case $n (et donc au dessus de la case $n+(W+2)).
cases dans les cellules de coordonnées paires et les marques pour les murs
entre. Ça simplifie un peu le code.
Sans cette optimisation, voici mon implémentation :
#!/usr/bin/perl
use strict;
use warnings;
no warnings "recursion";
use integer;
my $w = 25;
my $h = 16;
my $s = $w + 2;
my @visited;
my @right;
my @down;
for my $x (0 .. $w + 1) {
$visited[$x] = $visited[$x + ($h + 1) * $s] = 1;
}
for my $y (0 .. $h + 1) {
$visited[$y * $s] = $visited[$w + 1 + $y * $s] = 1;
}
sub make_maze($);
sub make_maze($) {
my ($c) = @_;
while(1) {
my @next = grep { !$visited[$_] } ($c + 1, $c - 1, $c + $s, $c - $s);
last unless @next;
my $n = $next[int(rand @next)];
$visited[$n] = 1;
$right[$c] = 1 if $n == $c + 1;
$right[$n] = 1 if $n == $c - 1;
$down[$c] = 1 if $n == $c + $s;
$down[$n] = 1 if $n == $c - $s;
make_maze $n;
}
}
make_maze int(rand($w) + 1) + int(rand($h) + 1) * $s;
for my $y (0 .. $h) {
if($y > 0) {
my $c = $y * $s;
for my $x (0 .. $w) {
print " " if $x > 0;
print $right[$c++] ? " " : "|";
}
print "\n";
}
my $c = 1 + $y * $s;
for my $x (1 .. $w) {
print "+", $down[$c++] ? " " : "--";
}
print "+\n";
}
kurtz le pirate
Feb 25, 2012, 9:54:43 AM2/25/12
to
In article <wt962ev...@marceau.mines-albi.fr>,
c'est évident.
--
klp
Paul Gaborit <Paul.G...@invalid.invalid> wrote:
> À (at) Sat, 25 Feb 2012 09:12:01 +0100,
> kurtz le pirate <kurtzl...@yahoo.fr> écrivait (wrote):
>
> > ...
> > ...
> À (at) Sat, 25 Feb 2012 09:12:01 +0100,
> kurtz le pirate <kurtzl...@yahoo.fr> écrivait (wrote):
>
> > ...
> > * je ne suis pas sur de comprendre ce qui est poussé dans le tableau.
> > ne faudrait-il pas écrire :
> > push @found, $maze[$row, $col] unless ...
> > ou
> > push @found, $maze->[$row]->[$col] unless ...
> >
> > et c'est bien tout le hash qui est poussé ?
> > $found[x] = {'visited' => 0,'bottom' => 1,'right' => 1,}
>
> Ce qui est poussé, c'est [$row + 1, $col]. C'est une référence à un
> tableau (anonyme) qui contient deux valeurs ($row+1 et $col).
oui, c'est aussi ce que nicolas a répondu. maintenant que vous le dite,
> > ne faudrait-il pas écrire :
> > push @found, $maze[$row, $col] unless ...
> > ou
> > push @found, $maze->[$row]->[$col] unless ...
> >
> > et c'est bien tout le hash qui est poussé ?
> > $found[x] = {'visited' => 0,'bottom' => 1,'right' => 1,}
>
> Ce qui est poussé, c'est [$row + 1, $col]. C'est une référence à un
> tableau (anonyme) qui contient deux valeurs ($row+1 et $col).
c'est évident.
--
klp
kurtz le pirate
Feb 25, 2012, 10:02:06 AM2/25/12
to
In article <4f48b277$0$32645$426a...@news.free.fr>,
:( !!!
effectivement ça marche super bien,
mais la aussi je n'ai pas tout compris... je vais m'y mettre.
quand au premier exemple donné, avec ton explication et celle de Paul,
j'ai encore quelques points à éclaircir.
je vais étudier aussi ton implémentation car je vois deja un /truc/ que
je ne comprend pas : sub make_maze($){...} <- c'est quoi ce /$/ ?
merci a vous deux.
--
klp
effectivement ça marche super bien,
mais la aussi je n'ai pas tout compris... je vais m'y mettre.
quand au premier exemple donné, avec ton explication et celle de Paul,
j'ai encore quelques points à éclaircir.
je vais étudier aussi ton implémentation car je vois deja un /truc/ que
je ne comprend pas : sub make_maze($){...} <- c'est quoi ce /$/ ?
merci a vous deux.
--
klp
Nicolas George
Feb 25, 2012, 10:50:19 AM2/25/12
to
kurtz le pirate , dans le message
<kurtzlepirate-93C...@news-4.proxad.net>, a écrit :
> je vais étudier aussi ton implémentation car je vois deja un /truc/ que
> je ne comprend pas : sub make_maze($){...} <- c'est quoi ce /$/ ?
http://perldoc.perl.org/perlsub.html#Prototypes
> je ne comprend pas : sub make_maze($){...} <- c'est quoi ce /$/ ?
0 new messages