je ne comprend pas

kurtz le pirate , dans le message
<kurtzlepirate-CD45DD.09120125022012@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.

* 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)).

À (at) Sat, 25 Feb 2012 09:12:01 +0100,
kurtz le pirate <kurtzlepirate@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 ?

... si la valeur associée à la clé 'visited' est vraie (donc 1 par
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]
unless $maze->[$row + 1][$col]{visited};

* 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).

--
Paul Gaborit - <http://perso.mines-albi.fr/~gaborit/>
Perl en français - <http://perl.mines-albi.fr/>

Nicolas George , dans le message
<4f48a828$0$23174$426a34cc@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
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";
}

In article <wt962evkzyd.fsf@marceau.mines-albi.fr>,
Paul Gaborit <Paul.Gaborit@invalid.invalid> wrote:

À (at) Sat, 25 Feb 2012 09:12:01 +0100,
kurtz le pirate <kurtzlepirate@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,
c'est évident.


--
klp

In article <4f48b277$0$32645$426a74cc@news.free.fr>,
Nicolas George <nicolas$george@salle-s.org> wrote:

Nicolas George , dans le message
<4f48a828$0$23174$426a34cc@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
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";
}

:( !!!
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

kurtz le pirate , dans le message
<kurtzlepirate-93C412.16020625022012@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