je ne comprend pas

Le
kurtz le pirate
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
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Nicolas George
Le #24278901
kurtz le pirate , dans le message
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)).
Paul Gaborit
Le #24278911
À (at) Sat, 25 Feb 2012 09:12:01 +0100,
kurtz le pirate
...
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 - Perl en français -
Nicolas George
Le #24278931
Nicolas George , dans le message
- 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";
}
kurtz le pirate
Le #24279431
In article Paul Gaborit
À (at) Sat, 25 Feb 2012 09:12:01 +0100,
kurtz le pirate
> ...
> ...
> * 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
kurtz le pirate
Le #24279471
In article Nicolas George
Nicolas George , dans le message
> - 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
Nicolas George
Le #24279571
kurtz le pirate , dans le message
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
Publicité
Poster une réponse
Anonyme