Path Finding A* - Page 1

J'ai fait un path finding A* pour ceux que ça interresse.
-->Télécharger<--

Tout n'est pas terminé mais c'est déjà fonctionnel.


NOTA : ne cherchez pas des performances fulgurantes sur vos TI!
EDIT : mise à jour du lien

Hum... Ça s'utilise comment ? J'ai du ouvrir la source pour comprendre qu'il fallait 4 ou 6 entiers en paramètre, déjà, et j'ai pas vu l'ombre d'une map donc c'est pas spécialement impressionant :/

-

Vertyos :
Hum... Ça s'utilise comment ? J'ai du ouvrir la source pour comprendre qu'il fallait 4 ou 6 entiers en paramètre, déjà, et j'ai pas vu l'ombre d'une map donc c'est pas spécialement impressionant :/

J'ai tout expliqué dans la doc.

1 : tu précises si tu travails en 3D avec #define USE_3D_NODES
2 : c'est à toi de définir si ton point est 'accessible' ou non avec PATH_isGoodWay. C'est pour ça qu'il n'y a aucune map!
3 : tu initialise avec PATH_init (différent selon si tu est en 3D ou pas). Les arguments sont les coordonnées de ton point de départ et d'arrivée (x,y) ou (x,y,z)
4 : tu lances la recherche avec PATH_searchPath. renvoie TRUE si un chemin est trouvé
5 : PATH_quit dans tous les cas (ça libère la mémoire et évite les error memory).

La base de la fonction PATH_isGoodWay est

#ifndef USE_3D_NODES
int PATH_isGoodWay(int X, int Y)
#else
int PATH_isGoodWay(int X, int Y, int Z)
#endif
{
 #ifndef USE_3D_NODES

 #else

 #endif
}

EXEMPLE (repris de l'archive) : ta map est un un rectangle de 8x6 avec un mur aux coordonnées (4,1) (4,2) et (4,3)

#ifndef USE_3D_NODES
int PATH_isGoodWay(int X, int Y)
#else
int PATH_isGoodWay(int X, int Y, int Z)
#endif
{
 #ifndef USE_3D_NODES
  if (Y < 0 || Y > 5 || X < 0 || X > 7)
   return FALSE;
  if (X == 4 && (Y == 1 || Y == 2 || Y == 3))
   return FALSE;
  return TRUE;
 #else

 #endif
}

Rien de plus simple!

Si tu utilise une matrice de booléens (ligne,colonne) tu la définira comme ça :

#ifndef USE_3D_NODES
int PATH_isGoodWay(int X, int Y)
#else
int PATH_isGoodWay(int X, int Y, int Z)
#endif
{
 #ifndef USE_3D_NODES
  if (Y < 0 || Y >= ligne || X < 0 || X >= colonne)
   return FALSE;
  return ma_matrice[Y*colonne + X];
 #else

 #endif
}

Ok, donc si j'ai pas trouvé un simple .89z à envoyer/executer, c'était normal... Dommage j'aurais bien regardé à quoi ça ressemble ^^

Donc ta map est codée en dur, c'est ça ?

J'ai mis un exemple (celui avec le mur cité en #3), il doit y avoir un .89z (et .92z) normalement.
Promis je fais des démos (graphiques) pour vous monter

Je sais pas ce que tu veux dire par "codée en dure" puisqu'aucune map n'est codée, je laisse libre cours à votre imagination.
ce qu'il faut juste c'est que la fonction PATH_isGoodWay renvoie true si le point (x,y) ou (x,y,z) passé en argument est utilisable et renvoyer false dans le cas contraire.

J'aimerai bien pouvoir compter le nombre de points calculer par seconde, si quelqu'un sait comment faire et le tester (j'ai plus ma calc) son aide est la bienvenue

Ca veut dire que tu ne peux pas dynamiquement changer de carte, ce qui est ton cas, donc c'est une carte codée en dur.
Ensuite, est-ce que tu as la possibilité de mettre une pénalité de mouvement sur ta carte ? C'est une utilisation avec des cases carrées ?

Miles :
Ca veut dire que tu ne peux pas dynamiquement changer de carte, ce qui est ton cas, donc c'est une carte codée en dur.
Ensuite, est-ce que tu as la possibilité de mettre une pénalité de mouvement sur ta carte ? C'est une utilisation avec des cases carrées ?

C'est le cas dans l'exemple cité (où la map est un tableau de booléens), mais l'utilisateur peut implémenter PATH_isGoodWay de la façon qu'il veut ...

Miles :
Ca veut dire que tu ne peux pas dynamiquement changer de carte, ce qui est ton cas, donc c'est une carte codée en dur.
Ensuite, est-ce que tu as la possibilité de mettre une pénalité de mouvement sur ta carte ? C'est une utilisation avec des cases carrées ?

Il n'y a aucune carte codée ; case carrées, zones, points, ... c'est toi qui décide et c'est toi qui change dynamiquement de carte dans ton prog.
Dans mon exemple avec la matrice de booléen on peut imaginer que la variable ma_matrice a été chargée via un fichier externe (je ferai unexemple avec ce cas de figure).
Comme le dit Quesoft PATH_isGoodWay doit être implémentée par toi.
Les seules contraintes sont de respecter le prototype et de renvoyer un booléen.
C'est une fonction qui doit être optimisée car elle est exécutée très souvent!

Pour ce qui est de la pénalité, c'est prévu. Enfin si tu entends pénalité un changement de type de terrain par exemple (avancer sur un chemin != avancer sur du sable ou un marécage)

IroS :
Pour ce qui est de la pénalité, c'est prévu. Enfin si tu entends pénalité un changement de type de terrain par exemple (avancer sur un chemin != avancer sur du sable ou un marécage)

À mon avis, ce qu'il veut dire par pénalité c'est exemple : 'passer par le chemin de longueur égale en asphalte, au lieu de prendre celui en sable' (si le sable est considéré comme plus pénalisant). Je ne veux pas répondre à la place de IroS, mais comme PATH_isGoodWay retourne un booléen, je ne crois pas que des 'coûts' associés à la nature du terrain puissent être pris en compte en utilisant cet API.

Nan c'est faisable sans (trop de) problème.
Tout se joue dans la fonction PATH_setFGH. par défaut un déplacement horizontal "coute" 10*racine(dX²+dY²(+dZ²)) soit 10, 14 ou 17 (le dernier pour la 3D). Les valeurs sont précalculées pour aller plus vite et le 10* évite de travailler avec des flottant (1, 1.4 ou 1.7).
Il suffit simplement de mettre un coefficient supplémentaire provenant d'une matrice par exemple.

EXEMPLE :
avancer sur de l'asphalte en diagonale 2D : coeff=1, coût=14 => coût total=14
avancer sur du sable : coeff=1.5, coût=14 => coût total=21
avancer dans l'eau : coeff=2.5, coût=14 => coût total=35
on peut mettre des flottants pour le calcul du coût mais je pense qu'il faut éviter pour une utilisation sur TI

L'algo recherche le plus favorable (ici l'asphalte), il faudra estimer les coefficients au plus juste.

Ca me fait penser que non seulement il faut que j'implémente ça mais qu'en plus il faut préciser à l'algo s'il doit chercher le chemin le plus court, le plus favorable, ... (une nouveauté en ammène une autre!)

C'est bon c'est fait, j'ajoute les démos et je rediffuse le tout

Je diffuse même si les démos ne sont pas terminées.

J'ai changé beaucoup de choses :
plus de fonction isGoodWay, j'ai l'impression que son utilisation est plutôt mal comprise.

maintenant l'utilisation des fonctions est encore plus pratique (enfin j'espère!)

1-on créé une variable de type PATH, PATH est une structure créée pour l'occasion
2-on initialise cette variable avec PATH_init qui ne demande plus qu'un pointeur sur ce type
3-on lance PATH_search qui lui aussi ne demande qu'un pointeur
4-on fait notre traitement avec le résultat
5-on lance PATH_quit (avec encore le pointeur sur notre variable

La structure :

	typedef struct
	{
		unsigned long Xs,Ys;
		unsigned long Xe,Ye;
		unsigned int *map;
		unsigned long width;
		unsigned long height;
		#ifdef USE_3D_NODES
			unsigned long Zs,Ze;
			unsigned long deep;
		#endif
		unsigned int make_full_path, search_mode, use_hv_move_only;
		unsigned long node_number;
		NODE** list;
		NODE* end_node;
	}PATH;

où Xs,Ys(,Zs) sont les coordonnées du point de départ
Xe,Ye(,Ze) les coordonnées du point d'arrivée
width,height(,deep) les dimensions de la map
*map le pointeur sur des unsigned int constituant la carte. Les valeurs nulles sont considérés comme infranchissables, les autres sont les fameux coeff majorant le déplacement (1=pas de majoration,2=point vallant 2 points non-majorés)
search_mode précise si les coeff doivent être pris en compte (utilisez les enum PATH_best et PATH_short)
us_hv_move_only est un booléen qui précise que seules les déplacements en diagonale sont autorisés
make_full_path va sûrement être supprimé donc j'en parle pas

PS : J'ai changé le lien du post 0