Discussion :

[juloss]

Bonjour.
Mon problème est un peu complexe.
J'essai d'implémenter l'algorithme A* (pathfinding).
Pour cela j'ai une class 'Noeud' qui possède un pointeur vers une autre instance de la class 'Noeud'.
Dans la boucle de recherche j'utilise le conteneur 'Deque'.
Or quant on parcours la liste fermée une fois le chemain trouvé, on s'aperçoit que tous les éléments de la liste fermée ont leur pointeur respectif qui pointent tous vers le même élément (le dernier Noeud trouvé)


Le vous donne une version simplifiée du code...

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
 
class Noeud
{
public:
Noeud *Parent; //Parent est un pointeur sur le noeud parent.
 
//-----------Constructeur de recopie---------------------------------------
 Noeud (const Noeud &a)
       {
       Parent=a.Parent;     
       }    
//-----------Constructeur de recopie---------------------------------------
 
//++++++++++++++++opérateurs+++++++++++++++++++++++++++++++++
 
//operateur = surchargé
 Noeud & operator=( const Noeud &a )
 { 
 Parent=a.Parent;
 return (*this);
 }   
//operateur = surchargé
 
//operateur () surchargé
 Noeud & operator()( Noeud *B)
 { 
 Parent=B;
 return (*this);
 }   
//operateur () surchargé
//++++++++++++++++opérateurs+++++++++++++++++++++++++++++++++
};
 
 
 
class A_star
{
public:
 deque<Noeud> Open;   //Liste ouverte de la recherche.
 deque<Noeud> Closed; //Liste fermée de la recherche.
 
Noeud Depart, Arriver;         //Le départ et arrivée du chemain. 
 
 
//-----------Constructeur-------------------------------------------------
 A_star(int X_depart, int Y_Arriver, int X_fin, int Y_arriver) 
      : Depart(X_depart, Y_Arriver,1000), Arriver(X_fin, Y_arriver)
  {
  Depart.Parent=0;  //Depart est le seul Noeud à ne pas avoir de parent.
   }
//-----------Constructeur-------------------------------------------------
 
 
//********************************************************
 void Recherche_Chemain()
 {      
 Noeud Courant;
 Noeud *CC=&Depart;
 
 Open.push_front(Depart);
 
    while( !Open.empty() )//Boucle de la recherche.
   {
   Noeud Test(0,0,100000);//Création d'un Noeud avec un 'F' de 100000.
   Test.Parent=0;
 
      for(int i=0; i<Open.size(); i++)//On cherche le plus petit élément de Open
      {
        if( Open[i] < Test) //On se sert du poid F.
        Test=Open[i];      
      }
 
 
 
 
      for(int i=0; i<Open.size(); i++)//On suprime ce pluspetit élément de Open    
        if( Open[i]==Test)
        Open.erase( Open.begin()+i);
 
 
 
   Courant=Test;// Courant est le Noeud avec le 'F' le plus faible de 'Open'
   Closed.push_front(Courant); Et on le met dans Closed 
 
 
 
     if(Courant==Arriver)//Si on est arrivé.
     {
     return;             //On arrête de chercher.
     }
     else
     {
     CC=&Courant;// CC est un pointeur sur le Noeud courant.
//Au nord     
       Test(CC);//Opérateur ().
 
       Test.y-=1;//On change les coordonnées de Test pour calculer le poid de ce Noeud.
//Toutes les autres case sont analysée de la même manière, seules les coordonnées de Test changent.
       if(Les condition sont peu importantes)
       {
       Test.Calcul_F(Arriver);// On calcul le poid de la case.
       Open.push_front(Test); //On ajoute Test à la liste ouverte
       }   
 
 
    }
 
   }//Fin de la boucle de la recherche.
   cout<<"Pas de chemain"<<endl;
 
 }
//********************************************************
 
};
 
 
int main(int argc, char *argv[])
{
 
A_star A(1,1,9,9);
A.Recherche_Chemain();
 
    system("PAUSE");
    return EXIT_SUCCESS;
}

J'ai enlevé tous ce qui n'a pas de rapport avec les pointeur.
Si vous voyez une erreur, merci de me le dire

[r0d]

Bonjour,

ton problème est très classique lorsqu'on manipule des pointeurs. Il se situe dans ces 3 lignes de code:

Code :

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

1
2
3
4
Test=Open[i];
//...
Courant=Test;// Courant est le Noeud avec le 'F' le plus faible de 'Open'
Closed.push_front(Courant);

Ces trois lignes sont trois affectations de pointeurs. Quand tu affectes un pointeur, il faut le voir comme une zone mémoire. Donc quand tu fais:

Code :

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

Closed.push_front(Courant);

, si ensuite tu modifie Courant, alors ce que tu as mis dans Closed sera aussi modifié.

Pour résoudre ton problème, il faut que tu fasses des copies de tes pointeurs, plutôt que (c'est ce que tu fais là) ré-affecter toujours le même pointeur.

[juloss]

Merci, je vais essayer ta solution

[r0d]

Arf, en me relisant je me rend compte que mon explication n'est pas claire

Le mieux est un exemple:

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
struct Dum
{
	Dum(int n):num(n){}
	int num;
};
 
int main( int argc, char** argv )
{
	std::vector<Dum*> v;
	Dum* d1 = new Dum(1); // on crée un objet Dum avec num=1
	v.push_back( d1 );
	d1->num = 2; // on affecte 2 à notre pointeur
	v.push_back( d1 );
 
	std::cin.get(); // attend une touche
}

A l'aide du debuggeur ou en faisant une fonction pour afficher le contenu du vecteur, tu verras que à la fin, tous les pointeurs présents dans ton tableau on num=2. C'esr parce que ce ne sont que des pointeurs et ils pointent tous sur le même objet (ou la même zone mémoire).

J'espère que c'est un peu plus clair.

[juloss]

Je te remercie mais j'avais compris.
Mais j'arrive pas a copier les pointeur :
J'utilise new mais le ploblème c'est que chaque 'Noeud' a un Parent mais ce Parent n'a pas de parent (problème de récursivité)donc on ne peux pas reconstituer le chemain...

[r0d]

Je te remercie mais j'avais compris.
Mais j'arrive pas a copier les pointeur :
J'utilise new mais le ploblème c'est que chaque 'Noeud' a un Parent mais ce Parent n'a pas de parent (problème de récursivité)donc on ne peut pas reconstituer le chemin...

Bien, on s'approche du coeur du problème, qui, en réalité, est plus de l'ordre de la conception que de la syntaxe.

En fait, je me suis mal exprimé (je ne sais pas ce que j'ai aujourd'hui, je suis un peu brouillé), ce n'est pas le pointeur qu'il faut copier, c'est l'objet sur lequel il pointe.

Première remarque: on voit ici que l'utilisation de pointeur pose un problème. Il est typique en plus. Donc, question: ne pourrait-on pas se passer des pointeurs? Autrement dit, au lieu de faire un Deque<Noeud*>, faire un Deque<Noeud>.

Pour répondre (honnêtement) à cette question, vu le contexte, je pense qu'il va falloir réfléchir à la durée de vie de tes objets (ceux que tu met dans tes files), qui est un problème primordial en c++. Autrement dit: chaque objet que tu va stocker dans une file, quand vas-tu pouvoir les supprimer (dit autrement: quand n'en auras-tu plus besoin), et qui va les supprimer (autrement dit, où vont-ils être supprimé)? Et surtout, comment vont-ils être crées?

L'utilisation de pointeurs de donne entièrement la responsabilité de la durée de vie de tes objets: c'est toi qui fait les new et les delete. L'utilisation d'objets (sans pointeurs) te permet, en quelque sorte, de déléguer cette responsablité au compilateur.

[Noxen]

Première remarque: on voit ici que l'utilisation de pointeur pose un problème. Il est typique en plus. Donc, question: ne pourrait-on pas se passer des pointeurs? Autrement dit, au lieu de faire un Deque<Noeud*>, faire un Deque<Noeud>.

Quel pointeur ? Il a édité son post entre-temps ?

Code :

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

1
2
3
4
5
6
7
8
 
class A_star
{
public:
 deque<Noeud> Open;   //Liste ouverte de la recherche.
 deque<Noeud> Closed; //Liste fermée de la recherche.
 
Noeud Depart, Arriver;         //Le départ et arrivée du chemain.