JeuWeb - Crée ton jeu par navigateur
Pathfinding ? - 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 : Pathfinding ? (/showthread.php?tid=1745)

Pages : 1 2


Pathfinding ? - Studio Gamboo - 12-09-2007

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 Smile


RE: Pathfinding ? - Pio154 - 12-09-2007

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
?>

Ensuite pour savoir si il y a un obstable, tu rajoute des structures if...elseif...else et à toi de trouvé la suite :p

Je n'ai pas été clair, je le sais, donc si tu à un problème post ici Wink


RE: Pathfinding ? - Byleth - 12-09-2007

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...


RE: Pathfinding ? - Pio154 - 12-09-2007

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


RE: Pathfinding ? - Loetheri - 12-09-2007

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 ;-))


RE: Pathfinding ? - Roworll - 12-09-2007

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*


RE: Pathfinding ? - Shidame - 12-09-2007

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


RE: Pathfinding ? - Byleth - 12-09-2007

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


RE: Pathfinding ? - Studio Gamboo - 12-09-2007

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 !


RE: Pathfinding ? - Studio Gamboo - 12-09-2007

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.