Algorithme A* : optimisation

Version imprimable

22/04/2013, 19h34
LiquidHuk

Algorithme A* : optimisation

Bonjour !

J'ai codé un algorithme A* qui fonctionne très bien, mais que j'aimerais optimiser car il devra à terme tourner sur une Raspberry Pi. Le temps d'initialisation (chargement de graphe par exemple) peut être long tant que les recherches de chemin derrière sont rapides. L'objectif serait d'obtenir une recherche de chemin sur une surface de 200*300 avec des pas de 20, en plus d'un lissage post A* afin d'éviter les déplacements saccadés. Est-ce réaliste de viser un temps de calcul de l'ordre de la demi-seconde ?

J'avais au départ une création à la volée des noeuds à chaque recherche de chemin, que j'ai modifié pour qu'ils soient tous créés dans le constructeur. J'ai rangé les noeuds dans un std::vector, et je les retrouve à l'aide de leur id.
Je me demandais si ce ne serait pas plus intéressant de créer un tableau à deux dimensions dans lequel je placerais les noeuds à la case correspondant à leur coordonnée sur la surface, quitte à diviser les coordonnées par 20 (le pas) afin d'éviter les cases de tableau vides ?

Afin d'assurer l'absence de fuite de mémoires, j'utilise des shared_ptr pour manipuler les noeuds, est-ce que cela allégerait notablement les calculs d'utiliser de simples pointeurs ?

Merci d'avance pour vos réponses !
23/04/2013, 11h12
ternel

Bonjour,

Attention, vector risque d'être trop lent, si tu fais juste un find.
Préfère au choix: un arbre ou un binary_search sur un vector trié.

La grille est envisageable, elle aussi, renseigne-toi sur le quad-tree.

Si tu as juste une liste constante, un vecteur de pointeurs nus, c'est plus rapide (moins de controles)
Si en plus, tous tes nœuds sont de la meme classe, un vecteur de nœud est encore mieux.
23/04/2013, 11h44
LiquidHuk

Merci pour tes conseils. Le quad_tree est vraiment intéressant.

Quand tu dis :

Citation:

Si en plus, tous tes nœuds sont de la meme classe, un vecteur de nœud est encore mieux.

Tu parles d'un std::vector<Noeud> au lieu de std::vector<Noeud*> ?
23/04/2013, 12h09
Iradrille

Citation:

Envoyé par leternel

Attention, vector risque d'être trop lent, si tu fais juste un find.
Préfère au choix: un arbre ou un binary_search sur un vector trié.

Ou un unordered_set vu que la recherche se fait par id.

(binary_search je connaissais pas, je recodais une recherche dichotomique dès que j'avais un vector trié, merci ça va m'éviter de refaire ça à chaque fois.)

Citation:

Envoyé par LiquidHuk

Tu parles d'un std::vector<Noeud> au lieu de std::vector<Noeud*> ?

Oui, un déréfencement de pointeur en moins à chaque accès.

(edit: bouh binary_search ne retourne pas d'itérateur sur l'élément trouvé. Une fonction équivalente existe retournant un itérateur ?)
23/04/2013, 13h17
LiquidHuk

Je suis désolé, mais je vais revenir sur l'idée de ma grille.

Il se trouve que quand je recherche un noeud, je possède ses coordonnées sur la surface (je calcule leur id en fonction des coordonnées). Si je range les noeuds de la manière suivante :

Noeud(x,y) dans grille[x/pas][y/pas].

Je n'aurais plus à parcourir la grille afin de trouver mon noeud : il me suffira à partir d'une coordonnée (x,y) sur la surface de faire noeud = grille[x/pas][y/pas].

Je ne vois pas comment parcourir un quad_tree pourrait être plus rapide ?

Par contre, je pense pencher pour le unordered_set pour les autres listes de noeuds. Je pense que lequad_tree pourrait être utile pour une gestion des obstacles dynamiques, dans le cas où les obstacles ne sont pas connus à l'avance (dans ce cas on vérifie à chaque noeud s'il est sur un obstacle).
23/04/2013, 13h28
ternel

C'est l'idée du quad-tree, en effet.

Si ta grille est pleine (math: pour tout (i,j) de la grille, grille(i,j) est un nœud) alors un tableau est rentable.
Dans ce cas, regarde cette entrée de la faq, et la suivante.

Sinon, une unsorted-map<Coord, Nœud> (de boost/C++11) permet un acces direct aux entrées.

Autre possibilité, en te basant sur le code de map que tu trouveras dans ton compilo, implémenter une map2D. Cependant, pour avoir essayez, c'est assez galère d'avoir une sémantique cohérente.

En fait, ton problème vient d'autre chose: tu n'as pas de classe ou conteneur adapté à ton besoin.
Cherche la sémantique et les usages voulus de ta grille, et écris l'interface d'une classe qui la proposerait.
Quand tu nous l'auras présentée, il sera bien plus facile de te guider.
23/04/2013, 16h34
LiquidHuk

Toutes les cases de la grille ne seraient pas utilisées car les cases censées contenir des nœuds positionnés sur des coordonnées où il y a un obstacle seront vides.
Par exemple si un obstacle empiète sur la coordonnée (40,40), la case grille[2][2] sera vide.
Je vais donc regarder les unordered_map.

Par curiosité, j'ai lu les deux articles de la FAQ mais il me reste une question. Sur l'exemple donné, la valeur de _data n'est pas stockée, le résultat retourné par matrix(x,y) est directement calculé en fonction des coordonnées. Si je veux stocker mes noeuds, j'utiliserais une structure de type tableau de tableau, non ?
24/04/2013, 11h05
victor_gasgas

Citation:

Envoyé par LiquidHuk

Bonjour !

J'ai codé un algorithme A* qui fonctionne très bien, mais que j'aimerais optimiser car il devra à terme tourner sur une Raspberry Pi. Le temps d'initialisation (chargement de graphe par exemple) peut être long tant que les recherches de chemin derrière sont rapides. L'objectif serait d'obtenir une recherche de chemin sur une surface de 200*300 avec des pas de 20, en plus d'un lissage post A* afin d'éviter les déplacements saccadés. Est-ce réaliste de viser un temps de calcul de l'ordre de la demi-seconde ?

Merci d'avance pour vos réponses !

Hum c'est bizarre mais la CPU utilisée, la taille de la carte et le lissage me font étrangement penser à la coupe de France de robotique :aie:

Connais-tu boost.graph, qui propose l'algo A*? Tu devrais voir s'il n'est pas plus rapide que ton implémentation maison!! http://www.boost.org/doc/libs/1_53_0...tar-cities.cpp
24/04/2013, 15h51
LiquidHuk

Citation:

Envoyé par victor_gasgas

Hum c'est bizarre mais la CPU utilisée, la taille de la carte et le lissage me font étrangement penser à la coupe de France de robotique :aie:

Je ne vois pas du tout de quoi tu veux parler ! :mrgreen:
J'ai participé l'an dernier et, même si je viendrais aussi cette année, j'ai très peu participé au projet. Je compte faire un pathfinding solide pour les années à venir :)

Je vais regarder boost.graph, merci !