Pathfinding A* quelques questions
Bonjour à tous :D
J'ai créé recement un algorithme A* sous python (et j'en suis extrèmement fier vu mon niveau de programmation :aie:), et j'ai décidé de le recoder en C++.
Pour celà je me suis (fortement) inspiré de ce tutoriel : http://khayyam.developpez.com/articles/algo/astar/
Or il y a deux trois choses que j'aimerai ammeliorer/comprendre :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| void A_Star::ajouter_cases_adjacentes(std::pair<int,int> &n)
{
noeud tmp;//noeud temporaire
/* On met tous les noeuds adjacents dans la liste ouverte en verifiant si
ce ne sont pas des obstacles ou si la case n'existe pas */
for (int i=n.first-1; i<=n.first+1; i++)
{
if ((i<0) || (i>=largeur_map)) /* en dehors de la map, on oublie */
continue;
for (int j=n.second-1; j<=n.second+1; j++)
{
if ((j<0) || (j>=hauteur_map)) /* en dehors de la map, on oublie */
continue;
if ((i==n.first) && (j==n.second)) /* case actuelle n, on oublie */
continue;
if ( map[(i*hauteur_map)+j] == OBSTACLE)
/* obstacle, terrain non franchissable, on oublie */
continue; |
Dans cette partie du code, on est censé éliminer toutes les cases adjacentes qui ne sont pas aptes à être analyser.
Comment faire pour que mon code n'analyse pas les cases en diagonal ? Je comprend bien que c'est du aux double boucle for, mais je n'ai pas d'idée de comment ne pas les analyser.
Dans le tuto, pour savoir la distance entre deux cases l'auteur utilise cette fonction :
Code:
1
2
3
4
5
6
7
8
9
| /* calcule la distance entre les points (x1,y1) et (x2,y2) */
float A_Star::calcul_distance(int x1, int y1, int x2, int y2)
{
/* distance euclidienne */
return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
/* carré de la distance euclidienne */
/* return (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2); */
} |
Cette fonction utilise t'elle beaucoup plus de temps calcul qu'une fonction de ce type ?
Code:
1
2
3
4
5
6
7
8
9
10
|
int A_Star::calcul_distance(int x1, int y1, int x2, int y2)
{
int abscisse=x2-x1;
int ordonnee=y2-y1;
distance = abscisse+ordonnee;
return distance;
} |
Si j'utilise cette fonction l'algorithme sera t'il toujours viable ?
De plus, l'auteur utilise cette fonction pour le cout h et le cout g du noeud. Ma fonction peut elle aussi s'appliquer au cout g ?
Merci d'avance :D
