Pathfinding ?

[Studio Gamboo]

Bonjour,
Je cherche un moyen de calculer une distance entre des cases sur un carte en php, mais en tenant compte des obstacles.
Connaissez vous un moyen simple et peu gourmand pour faire cela ?
Merci d'avance à tous

[Pio154]

J'ai pas trop compris mais je vais deviner :p

Quels distance entre les cases ? ( La distance au personnage ? )
Si ses sa alors j'ai peut être une idée pour toi.

Je ne sais pas comment tu fait passé tout les joueurs + les obstacles que tu rajoute...

Voici une map que je réalise pour créer un jeu php : http://bwork-design.fr.nf/mapv1/

Ici il n'y a pas d'obstacle, sauf que j'en rajouterai. Donc pour savoir si il y a un obstacle en x / y, il te faudra donc avoir toute les données dans un array.

Code PHP :

<?php



 $array = array(); // Création d'un tableau.



 // ta requête ici et ta boucle while ou for comme tu veu ;)

 // ensuite dans ta boucle il te faudra créer un sous array ect..



  while ()

{



 $array['sous_array']['colone_du_sous_array'] = 'b';



}



// Si tu a des problème, affiche si avec print_r()



echo '<pre>';

print_r($array)

echo '</pre>';



// Voici de ce que sa va t'afficher :

/*

Array

(

    [sous_array] => Array

        (

            [colone_du_sous_array] => b

        )



)

*/



Biensûre il ne faudra pas lui donnée un nom au harsard au colone, il te faudra donc une variable qui s'incremente : $variable++;



*/



/* pour voir dans un sous array ... : */

 echo $array[sous_array][colone_du_sous_array];

// Ceci va t'afficher b

?>

[Byleth]

Ce problème m'intéresse aussi (intelligence artificielle des monstres, il s'agit de trouver le chemin le plus court) mais je n'ai rien compris à ton explication ^^

Pourtant je maitrise tout ce que tu utilises...

[Pio154]

Pour te dire moi aussi je n'ai rien compris à ce que tu voulai dire. (Ps: sa veu dire coi Pathfinding ??)

[Loetheri]

Je n'ai rien compris à ce que tu as dis Pio154.

Par contre, une technique (normallement) est de parler en vecteurs. Je sais que ce n'est pas la façon la plus simple, hein ;-)
Mais tu crées un vecteur allant du point A (départ) au point B (arrivée). Tu regardes s'il y a un obstacle. Si oui, tu récupères toutes les données de cet obstacle afin d'en faire un vecteur. Tu calcules à partir de ton point d'impact/collision/touché, où se trouve le bord le plus proche. Le dernier point du bord le plus proche devient alors un point C (intermédiaire). Tu calculs la distance entre A et C et C et B. Tu refais le même calcul pour C-B que pour A-B. Mais tu dois vérifier qu'il n'est quand même pas possible d'aller plus vite en passant par l'autre bout de l'obstacle.

C'est naturellement pas super facile à mettre en place et pas des plus économiques en ressources. Cependant, pour avoir vu le projet d'Ingénieur Civile Électricité (Première Maîtrise), l'utilisation des vecteurs est une solution viable et utile ^^ (mais peut-être pas sous PHP ;-))

[Roworll]

Méthode A* dans Wikipedia
Lien vers un article de référence de la méthode A*
Page avec des sources téléchargeables (en flash) avec implémentation d'un algo de type A*

[Shidame]

Merci Roworll, cet algo a l'air plus performant que le bon vieux algorithme de Dijkstra. Je vais tenter une implémentation en php.

[Byleth]

Oui, ça a l'air très bien, je me plonge dedans directement

[Studio Gamboo]

J'ai déjà connaissance de l'algo A* et des ses variantes mais j'avoue que j'ai quelque peu de mal à comprendre se fonctionnement, et du même coup à l'adapter à mes besoin en php !

[Studio Gamboo]

Je tient d'ailleurs à préciser que mon objectif est simplement de compter le nombre de cases nécessaire, et non pas d'avoir un cheminement complet. Peut-être qu'il existe une alternative à A* dans ce cas la.