Discussion :

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

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 !

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

[LiquidHuk]

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

Quand tu dis :

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

[Iradrille]

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

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

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

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

[victor_gasgas]

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

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

[LiquidHuk]

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

Je ne vois pas du tout de quoi tu veux parler !
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 !