Pathfinding ?

[exopi]

J'ai fait le meme genre de script, voila le code source de la fonction :

Code :

inclure('is_passable');
function  tableau_deplacement($xd,$yd,$nb,$xmax,$ymax,$rayon=3){
    $xmin=max(1,$xd-$rayon);
    $xmax=min($xmax,$xd+$rayon);
    $ymin=max(1,$yd-$rayon);
    $ymax=min($ymax,$yd+$rayon);

    $sort['xmin']=$xmin;
    $sort['ymin']=$ymin;
    $sort['xmax']=$xmax;
    $sort['ymax']=$ymax;

    // definir le relief
    for($x=$xmin;$x<=$xmax;$x++){
        for($y=$ymin;$y<=$ymax;$y++){
            if (false==is_passable($x,$y)){
                $sort[$x.'/'.$y]=-1;
            }else{
                $sort[$x.'/'.$y]=255;
            }
        }
    }
    $sort[$xd.'/'.$yd]=0;

    //demarer l'algo
    for($i=1;$i<=$nb;$i++){
        $verif=0;
        for($x=$xmin;$x<=$xmax;$x++){
            for($y=$ymin;$y<=$ymax;$y++){
                if ($sort[$x.'/'.$y]==$i-1){
                    $verif=1;
                    // ecrire les cases adjacentes
                    if ($sort[$x.'/'.min($y+1,$ymax)]>$i){
                        $sort[$x.'/'.min($y+1,$ymax)]=$i;
                    }
                    if ($sort[$x.'/'.max($y-1,$ymin)]>$i){
                        $sort[$x.'/'.max($y-1,$ymin)]=$i;
                    }
                    if ($sort[min($x+1,$xmax).'/'.$y]>$i){
                        $sort[min($x+1,$xmax).'/'.$y]=$i;
                    }
                    if ($sort[max($x-1,$xmin).'/'.$y]>$i){
                        $sort[max($x-1,$xmin).'/'.$y]=$i;
                    }
                }
            }
        }
        if ($verif==0){break;}
    }

    //finaliser le tableau
    for($x=$xmin;$x<=$xmax;$x++){
        for($y=$ymin;$y<=$ymax;$y++){
            if ($sort[$x.'/'.$y]==255){
                $sort[$x.'/'.$y]=-1;
            }
        }
    }

    return $sort;
}

La fonction is_passable renvoi true si la case n'est pas un obstacle, false dans le cas contraire

(xd,yd) corespond à la case centrale ( nombre de case pour y acceder : 0 )
nb correspond au nombre de déplacement élémentaires à effectuer ( 5 fait faire 5 ittérations de l'algorythme )

(xmax,ymax), ben la taille max de la carte...

rayon : la taille max autour de (xd,yd) à calculer[/code]


en ce qui concerne de la complexité, elle est en O(n.nb), avec n = (rayon*2+1)², ce qui fait une trés bonen complexité, car généralement, elle est de O(nb) car pour remplir n au pire il faut nb=n/2, ce qui n'arrive jamais. Deplus en choisist le facteur nb, on controle directement la complexité