Pathfinding ?

[Byleth]

Je ne pense pas car tu dois avoir un cheminement pour compter le nombre de case ^^

[Studio Gamboo]

Oui c'est ce que je me suis dit aussi
J'ai testé ce script : http://pingouin.migrateur.free.fr/astar/astar.php.html mais il me donne beaucoup de mauvais résultat sur ma map, et est pas forcément trés clair dans sa construction donc bon

[keke]

Coucou studio Gamboo ^^.

J'ai repris le lien que tu as signalé, et j'ai fais des modifications en vrac pour afficher une carte plus petite mais avec plus de dénivelé. L'algo se comporte parfaitement ! Donc merci pour cette perle rare. Il m'a fallut 1 heure pour arriver à adapter l'algo à mon contexte, et il me faudra 6h pour l'incorporer dans mon code.

Je voulais savoir si c'était toi l'auteur du code ?

AUTEUR(S) : Alexandre AUPETIT
VERSION : 1.0
DATE : 22/10/2006
LICENCE : logiciel libre LGPL
Ce code source peut être utilisé dans une application GPL ou non, les modifications effectuées
à cette source doivent être rendue publiques aux utilisateurs de l'application l'utilisant.

Ou et comment dois-je rendre publique le code modifié ?

Kéké.

[naholyr]

Quite à déterrer le topic, tu trouveras une implémentation d'A* dans le sujet Déplacement de plusieurs cases.

[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é