JeuWeb - Crée ton jeu par navigateur
[PHP] Déterminer le prochain point d'une spirale carrée dans une grille - Version imprimable

+- JeuWeb - Crée ton jeu par navigateur (https://jeuweb.org)
+-- Forum : Discussions, Aide, Ressources... (https://jeuweb.org/forumdisplay.php?fid=38)
+--- Forum : Programmation, infrastructure (https://jeuweb.org/forumdisplay.php?fid=51)
+--- Sujet : [PHP] Déterminer le prochain point d'une spirale carrée dans une grille (/showthread.php?tid=5640)

Pages : 1 2 3


[PHP] Déterminer le prochain point d'une spirale carrée dans une grille - Maz - 15-08-2011

Voici une fonction permettant de généré le prochain point d'un carré fictif dans une grille formant une spirale carrée.
La fonction prends en paramètre les coordonnées d'un des points du carré fictif précédent et la taille des carrés fictifs, calcul son origine (point supérieur gauche), et renvoi les coordonnées du point d'origine du carré fictifs suivant avec ou sans un niveau d'aléatoire.
Voir l'illustration ici de la fonction bouclé x300 pour des carrés fictifs de taille 21 avec un niveau d'aléatoire de 10: http://mazdesign.free.fr/spiralecarre/new.php
<?php
function nextPlace($x, $y, $size, $randomLevel = null) {
$denominateurX = floor($x/$size);
$denominateurY = floor($y/$size);

$currentCenter = array($denominateurX*$size, $denominateurY*$size);
if($denominateurX == $denominateurY){
$axe = "x";
$sens = ($denominateurX < 0)*2-1; // 1 si x<0, -1 si x>=0
} else if(abs($denominateurX) == abs($denominateurY)) {
$axe = ($denominateurY > 0) ? "x" : "y";
$sens = -($denominateurY > 0)*2+1;
} else if(abs($denominateurX) > abs($denominateurY)) {
$axe = "y";
$sens = ($denominateurX > 0)*2-1;
} else if(abs($denominateurY) > abs($denominateurX)) {
$axe = "x";
$sens = -($denominateurY > 0)*2+1;
}

$x = $denominateurX*$size;
$y = $denominateurY*$size;

$$axe += $size*$sens;
// Pour des valeurs aléatoires:
if (!is_null($randomLevel)) {
if($randomLevel >= $size)
$randomLevel = $size-1;
$x += rand(0, $randomLevel);
$y += rand(0, $randomLevel);
}
return array($x, $y);
}
?>
Petite illustration:
c x x 3 x x 4 x x 5 x x
x x x x x x x x x x x x
x x x x x x x x x x x x
x x x 2 x x 1 x x 6 x x
b x x x x x x x x x x x
x x x x x x x x x x x x
a x x 9 x x 8 x x 7 x x
x x x x x x x x x x x x
x x x x x x x x x x x x
Si l'on appel la fonction en donnant les coordonnée du point 1 avec un $size = 3, elle renverras celles du point 2, avec les coordonnées du point 2, elle renverras celles du point 3, etc...

L'utilité n'est pas évidente, personnellement je m'en sert pour généré la position de départ des joueurs dans un jeu de gestion de ville et ainsi positionner les joueurs de façon concentré avec un peu d'aléatoire (deux rand(0,3) pour généré les coordonnée x et y à ajouter au point d'origine du carré fictif pour placé aléatoirement le joueur dans le carré fictif).

Edit 15/08/2011 à 21h54: fix d'un bug et ajout du paramètre randomLevel permettant la génération aléatoire du point dans le carré fictif.
Edit 26/09/2011 à 22h35: amélioration du code, merci Xenos.


RE: Php: déterminer le prochain point d'une spirale carrée dans une grille - Akira777 - 15-08-2011

Merci pour le partage !


RE: Php: déterminer le prochain point d'une spirale carrée dans une grille - Xenos - 26-09-2011

Optimise un poil en utilisant +1 ou -1 pour le sens:

Code :
<?php
    function nextPlace($x, $y, $size, $randomLevel = null) {
        $denominateurX = floor($x/$size);
        $denominateurY = floor($y/$size);

        $currentCenter = array($denominateurX*$size, $denominateurY*$size);
        if($denominateurX == $denominateurY){
            $axe = "x";
            $sens = ($denominateurX < 0)*2-1; // 1 si x<0, -1 si x>=0
        } else if(abs($denominateurX) == abs($denominateurY)) {
            $axe = ($denominateurY > 0) ? "x" : "y";
            $sens = -($denominateurY > 0)*2+1;
        } else if(abs($denominateurX) > abs($denominateurY)) {
            $axe = "y";
            $sens = ($denominateurX > 0)*2-1;
        } else if(abs($denominateurY) > abs($denominateurX)) {
            $axe = "x";
            $sens = -($denominateurY > 0)*2+1;
        }

        $x = $denominateurX*$size;
        $y = $denominateurY*$size;

        $$axe = $$axe + ($size*$sens);
        // Pour des valeurs aléatoires:
        if (!is_null($randomLevel)) {
            if($randomLevel >= $size)
                $randomLevel = $size-1;
            $x += rand(0, $randomLevel);
            $y += rand(0, $randomLevel);
        }
        return array($x, $y);
    }
?>



RE: Php: déterminer le prochain point d'une spirale carrée dans une grille - Maz - 26-09-2011

(26-09-2011, 12:16 AM)Xenos a écrit : Optimise un poil en utilisant +1 ou -1 pour le sens:


<?php
function nextPlace($x, $y, $size, $randomLevel = null) {
$denominateurX = floor($x/$size);
$denominateurY = floor($y/$size);

$currentCenter = array($denominateurX*$size, $denominateurY*$size);
if($denominateurX == $denominateurY){
$axe = "x";
$sens = ($denominateurX < 0)*2-1; // 1 si x<0, -1 si x>=0
} else if(abs($denominateurX) == abs($denominateurY)) {
$axe = ($denominateurY > 0) ? "x" : "y";
$sens = -($denominateurY > 0)*2+1;
} else if(abs($denominateurX) > abs($denominateurY)) {
$axe = "y";
$sens = ($denominateurX > 0)*2-1;
} else if(abs($denominateurY) > abs($denominateurX)) {
$axe = "x";
$sens = -($denominateurY > 0)*2+1;
}

$x = $denominateurX*$size;
$y = $denominateurY*$size;

$$axe = $$axe + ($size*$sens);
// Pour des valeurs aléatoires:
if (!is_null($randomLevel)) {
if($randomLevel >= $size)
$randomLevel = $size-1;
$x += rand(0, $randomLevel);
$y += rand(0, $randomLevel);
}
return array($x, $y);
}
?>
Très intéressante façon d'utiliser la condition du sens effectivement. Mais dans ce cas là:
$$axe += $size*$sens suffis. Je met à jour le code, merci pour les personnes qui l'utiliseront.


RE: Php: déterminer le prochain point d'une spirale carrée dans une grille - Xenos - 27-09-2011

Exact pour le +=.

J'essayerai de plancher voir s'il n'existe pas de fonction non-récursive donnant les coordonnées (x;y) du N-e point de la spirale (et non une fonction donnant le prochain point comme celle si brillamment exposée). Les deux se complèteront alors Wink


RE: Php: déterminer le prochain point d'une spirale carrée dans une grille - Maz - 29-09-2011

(27-09-2011, 05:31 PM)Xenos a écrit : Exact pour le +=.

J'essayerai de plancher voir s'il n'existe pas de fonction non-récursive donnant les coordonnées (x;y) du N-e point de la spirale (et non une fonction donnant le prochain point comme celle si brillamment exposée). Les deux se complèteront alors Wink

Ayant déjà chercher à le faire, je te souhaites bien du courage pour le faire sans récursivité. J'ai beaucoup travailler cette forme de spirale pour obtenir la fonction proposée, dont voici les débuts de mes "études": ici, ici(amélioré), et là(amélioré++), dans le second et troisième exemple j'échappe la récursivité en passant par des variable qui font démarré les boucles à une certaines itération et non pas au point 0. Mais encore faut-il connaître la valeur que doivent prendre ces variables...

Je ne pourrais malheureusement pas t'aider car depuis je suis passer à la programmation Ruby.


RE: Php: déterminer le prochain point d'une spirale carrée dans une grille - Xenos - 30-09-2011

C'est parfaitement réalisable. Je ne l'ai qu'en C++, je passerai ca en php plus tard peut-être.
Le principe est simple: à partir de p, numéro absolu du point, on cherche combien de points sont dans les carrés des spirales précédentes (n). Ensuite, on sait combien de point il y a dans le carré (n+1), carré dans lequel se trouve le point p. De là, on a 4 cas (4 cotés), qui permettent de placer le point p dans le carré (n+1).
Bon, sans schéma, c'est trash... mais ca marche ^^

Voilà, en PHP:

Code :
<?php
    
    function calc($p)
    {
        if ($p != 0)
        {
            $n = floor((sqrt($p)-1.0)/2.0);        // n° du dernier carré remplis (je suis dans le n+1)
            $m = $n+1;                // n° du carré actuel dans lequel je suis
            $l = $p - (2*$n+1)*(2*$n+1);        // n° du point dans ce carré
            
            $lp = $l%(2*$m);            // numéro du point sur le coté courant du carré courant
            if ($l < 2*$m)
                $u = Array($m, $n-$lp, 0);
            else if ($l < 4*$m)
                $u = Array($n-$lp, -$m, 1);
            else if ($l < 6*$m)
                $u = Array(-$m, -$n + $lp, 2);
            else
                $u = Array(-$n + $lp, $m, 3);
        }
        else
            $u = Array(0, 0, 0);            // Cas aprticulier
        return $u;
    }

    $NMAX = 8;$MMAX = 2*$NMAX+1;
    $matrice = Array();
    for ($i=0;$i<$MMAX*$MMAX;$i++)
    {
        $v = calc($i);
        $matrice[$v[0]][$v[1]] = Array($i, $v[2]);
    }
    
    $c = Array("#000000", "#D00000", "#00D000", "#0000D0");
    echo('<table border=1>');
    for ($y=$NMAX;$y>=-$NMAX;$y--)
    {
        echo('<tr>');
        for ($x=-$NMAX;$x<=$NMAX;$x++)
        {
            echo('<td style="color:'.$c[$matrice[$x][$y][1]].';">' . $matrice[$x][$y][0] . '</td>');
        }
        echo('</tr>');
    }
    echo('</table>');
?>

La fonction "calc(p)" renvoie un tableau 3x1, avec:
u[0] => coordonnée x du point p
u[1] => coordonnée y du point p
u[2] => 0 si on est dans le triangle de droite (noir), 1 dans le triangle bas (rouge), 2 pour le triangle gauche (vert), et 3 pour le triangle du haut (bleu). Cette dernière valeur n'est pas franchement utile, mais elle permet de savoir quelle est la "direction" du prochain point:
si u[2] = 0, le prochain point est à y-1
si u[2] = 1, le prochain point est à x-1
si u[2] = 2, le prochain point est à y+1
si u[2] = 3, le prochain point est à x+1

p=0 désigne le point central de la spirale (0,0)
p=1 désigne le premier point.

Calcul non récursif (le "for", c'est pour calculer les coords de chaque point de la spirale pour afficher toute la spirale, elle ne fait pas aprtie de la fonction "calc()").

Libre à toi d'ajouter ensuite un "delta", de la forme x € ]-0.5 ; 0.5[ et y € ] -0.5 ; 0.5 [ pour que la forme de la spirale ait un peu d'aléatoire.


RE: Php: déterminer le prochain point d'une spirale carrée dans une grille - niahoo - 30-09-2011

Pourquoi vous tenez absolument à ne pas utiliser la récursivité, alors que ça semble très indiqué dans ce cas précis ?


RE: Php: déterminer le prochain point d'une spirale carrée dans une grille - Hideaki - 30-09-2011

Entièrement d'accord avec toi et puisque le php fait aussi de l'objet vous pouvez aussi le faire en objet ( utilise forcément la récursivité ).


RE: Php: déterminer le prochain point d'une spirale carrée dans une grille - Xenos - 30-09-2011

On préfère éviter car c'est nettement moins long à calculer sans récursivité. POur des spirales de 100, voir peut-être 1000 points, c'est pas lourd comme écart, mais arrivé à des spirales de 10.000 ou 1.000.000 de points (qui vont m'être utile deans un autre projet d'ailleurs), ca peut être très utile de ne pas faire de récursif