Discussion :

[valefor]

Bonjour.

Premiere question, à propos de la mesure de l'efficacité d'un algo que j'ai implémenté en c++.
Quels sont les indicateurs qui me montreront qu'il est plus ou moins adapté qu'un autre ? Dois-je utiliser un "time" dans mon code pour calculer le temps pris et le comparer au résultat d'un autre avec les même données en entrée ?
Faut-il que je détermine sa complexité ?
Esiste-til un standard de codage et d'intreface pour le comparer à d'autre ?

Deuxième question, à propos de A*.
Cet algo fut mon pire cauchemard des cours d'IA que j'ai subit. Chaque fois que quelqu'un dit je veux fairte du pathfinding on lui répond sans hésiter "A*". Mais je me demandais si avec des contraintes telles que :
- trouver un chemin le plus vite possible (pas necessairement le plus court) ou dire qu'il n'en existe pas
- considerer que toutes les cases ont un coût de parcours égal
on ne pourrait pas imaginer un truc différent, plus intuitif qu'une recherche tout azimut jusqu'à trouver le meilleur chemin ?

Comme je pense avoir une solution, j'aimerai vous la proposer sans pour autant avoir l'air d'avoir ré-inventé le fil à couper le beurre. Faudrait pas que ça en énnerve quelques un

Merci de votre lecture.

[leghola]

Hello,

Personnellement je serai interressé et heureux de lire ta reflexion...

A* et Drijksta (imprononçable ce nom ! :p) sont bien sur les plus connus mais ce n'est pas pour ca que c'est forcément les plus puissants. En fait je voulais juste dire qu'il y a désormais peut etre de nouvelles solutions plus adaptés en vue des nouvelles découvertes ...

Donc moi perso je suis impatient de lire ca

a++
Nico

[valefor]

Après un petit nettoyage de code voici le résultat.

Le pseudo code est le suivant

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
21
22
23
24
25
26
27
28
29
30
31
32
33
 
 
Paramètres d'entrée
  point de départ
  point d'arrivée
 
Paramètres de sortie
  liste de points
 
Initialisation
  point courant <- point de départ
  liste de points += point courant
 
Corps
  tant que l'arrivée n'est pas atteinte
    si aucun obstacle 
      aller en ligne droite de point courant jusqu'à l'arrivée
      liste de points += point courant
      si point courant == point d'arrivée 
        c'est fini
      sinon 
        détermination de la face, du sens, et du critère de sortie pour contourner l'obstacle
      fsi
    sinon
      contournement de l'obstacle par une face
      liste de points += point courant
      si critère de contournement ok
        aucun obstacle
      sinon
        contournement par la face suivante déterminée par le sens de contournement
      fsi
    fsi
  ftq

Pour compiler le source, il y a quelques infos dans l'entête (à l'origine l'extension du source est .cc).

Pour lancer l'exécutable, il faut passer un fichier bmp avec deux couleurs : du blanc pour les zones navigables, et du noir pour les "murs". A titre d'exemple j'ai joins un fichier test à dé-zipper.

Pour utiliser le programme, il faut taper la touche 'a' à l'endroit où voulez partir, et 'b' à l'endroit où vous voulez arriver.


L'algo peut fonctionner avec des murs courbes (escargot par exemple). Mais il n'est pas trop fait pour cela à l'origine. Pour essayer il faut augmenter la valeur de la variable 'ttl'.


Merci de me donner votre avis sur la pertinence de cette idée.

[leghola]

Hello,

tu n'aurais pas un code compilé stp car je n'ai que vb.net express sous la main et je ne peux donc pas le tester

a++
nico

[valefor]

Désolé je n'ai pas ça !

[PRomu@ld]

Si tu as besoin d'informations sur l'algorithme A*, tu peux regarder éventuellement ici :

http://khayyam.developpez.com/articles/algo/astar/

[Matthieu Brucher]

Ton algorithme, c'est l'A* avec des poids 0 ou 1. Maintenant, que fais-tu si les valeurs sont continues entre 0 et 1 ?

[valefor]

Je ne souhaite pas gérer les nuances. Pour mon besoin, c'est soit un mur soit un passage.

De plus, il me semblait que A* gérait une liste de plusieurs possibilité qui font que si une solution se retrouve dans un cul de sac, une autre solution stockée dans les listes sera favorisée au fur et à mesure du déroulement de l'algo.
Au final quand on regarde les pixels qui ont été testés par A* il y en a beaucoup plus que ceux par lesquels on passe effectivement à la fin.

Et c'est bien ce que je dis, dès qu'on parle de pathfinding tous le monde dit A* parce qu'il s'est tellement fait chier à comprendre comment ça marche que c'est dommage de ne pas l'utiliser . Je ne renie pas le fais qu'il soit supporté par une théorie solide qui fonctionne dans tous les cas. Mais cela m'ennuie qu'on saute dessus systématiquement.

En tout cas merci de votre lecture, et de votre temps pour exprimer ces retours.

[Matthieu Brucher]

Dans ce cas, ton algop, c'est du A*, c'est tout.

[valefor]

Bon, d'accord.

[Matthieu Brucher]

Ben oui, tu cherches le chemin le plus court et tu considères toujours la ligne droite comme le chemin le plus rapide, tout comme l'A*. Quand tu arrives à un obstacle, tu choisis un point autour de toi proche de l'obstacle et tu continues, c'est exactement ce que fait l'A* (peut-être que dans des ca splus complexes, l'A*s'en sort tout de même mieux car il cherche avec une bonne heuristique tandis que tu restes toujours collé au mur)

[valefor]

En fait dans le code j'ai rajouter quelques trucs qui font qu'on prend des raccourcis quand c'est possible. Quand j'ajoute un point, je scanne la liste des points déjà présent pour regarder si je ne peut pas aller en ligne droite jusqu'à ce nouveau point. Auquel cas ça me fait sauter tous les méandres (et cela fait que je ne reste pas "toujours collé au mur").

Ce qui me semblait pas très intuitif dans A* c'est la zone explorée.
Par exemple sur cette image
on voit que la zone explorée par A* est large.
Dans mon cas je n'explore que le long des murs et des lignes droites (d'ailleurs je vais faire un truc dans mon code pour colorer les zones explorées).

As-tu essayé le code que j'ai joins, ou ce forum suggère qu'on discute uniquement sur l'algo ?

[Matthieu Brucher]

Un A* ne parcourt pas l'espace que tu montres, il parcourt exactement les pointillés uniquement.

Par rapport au code, mieux vaut ouvrir un sujet spécifique dans le forum C++

[valefor]

Le chemin final est effectivement représenté par les pointillés. Mais les "pixels" testés sont bien ceux qui sont colorés non ?

Je vais aller poster le code à un endroit mieux adapté.

Encore merci pour le dialogue !

[Matthieu Brucher]

Non, ce n'est pas le cas. Il est possible que A* commence en montant la grille plutôt qu'en allant à gauche, mais une fois qu'il est parti sur cette ligne à gauche, il va trouver ta solution. Par exemple, les cases coloriées à l'intérieur du U ne seront jamais testées puisqu'elles s'éloignent de la solution (il est vrai que les cases testées qui sont dans la liste ouverte sont celles qui son tjuste autour du chemin au moins, donc un peu plus que le chemin réel, mais même pour toi, tu dois tout de même tester si tu t'éloignes ou non de l'arrivée).

[valefor]

Oké merci !