Discussion :

[kump_]

Bonjour à tous

J'ai créé recement un algorithme A* sous python (et j'en suis extrèmement fier vu mon niveau de programmation ), 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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Matthieu Brucher]

Une distance, c'est toujours positif, pas dans le cas de ta fonction que tu proposes.

On utilises la distance euclidienne parce que c'est la distance naturelle quand tu traces une droite. Mais si tu n'en veux pas, tu peux prendre une distance valeur absolue ou max.

[kump_]

Ce n'est pas que je refuse d'utiliser la distance euclidienne seulement j'ai peur qu'utiliser des valeurs décimales fasse perdre trop de temps de calcul.

Si vous me dîtes que cela n'entraine qu'une perte minime je garde cette fonction évidemment

Une distance, c'est toujours positif, pas dans le cas de ta fonction que tu proposes.

Oups !

Bon alors :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
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 abs(distance);
}

[Matthieu Brucher]

C'est pas non plus une distance ça abs(x) + abs(y) oui.
Mais tu auras moins de chances d'obtenir une solution optimale avec cette fonction.

[kump_]

C'est pas non plus une distance ça abs(x) + abs(y) oui.

Rofl, j'aurai eu faux sur toute la ligne

Mais tu auras moins de chances d'obtenir une solution optimale avec cette fonction.

Ce qu'il faut savoir c'est que je compte utiliser cet algorithme dans un jeu, il me faut donc une vitesse d'execution la plus rapide possible. Ce n'est pas très grave de ne pas avoir la solution optimale.

Donc je réitère ma question, la fonction de l'auteur fait elle perdre trop de temps ?

[Matthieu Brucher]

Je te conseille de tester avec la fonction du tutoriel et si tu vois que tu as des problèmes avec, tu peux songer à changer la fonction, mais il existe de nombreuses autres possibilités (A* hiérarchique, progressif, ...)