Questions autours du pathfinding

**valefor** · 22/07/2007, 15h43

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** · 23/07/2007, 08h34

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** · 23/07/2007, 13h15

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.