Implémentation de l'algorithme A*

**ludo2612** · 26/03/2009, 21h04

Bonjour j'essaie d'implémenter l'algorithme A* qui recherche des chemins entre deux points en prenant en compte les obstacles.

J'arrive à calculer le chemin mais je ne peux pas le retrouver car mes Noeud qui sont censés contenir les Coordonnées du Noeud précédent (une liste chaînée) ne contiennent pas les bonnes coordonnées.

Voici mon code en C++, pouvez-vous m'aider SVP?

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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
/*
 * AStar.cpp
 *
 *  Created on: 22 mars 2009
 *      Author: Ludovic
 */
 
#include <iostream>
#include <utility>
#include "AStar.h"
 
AStar::AStar(Damier& d) :
	damier(d) {
 
}
 
AStar::~AStar() {
}
 
int AStar::distance(Coordonnee a, Coordonnee b) {
	return ((a.getX() - b.getX()) * (a.getX() - b.getX()) + (a.getY()
			- b.getY()) * (a.getY() - b.getY()));
}
 
bool AStar::deja_present_dans_liste(Coordonnee n,
		map<Coordonnee, Noeud>& l_noeuds) {
	map<Coordonnee, Noeud>::iterator i;
	for (i = l_noeuds.begin(); i != l_noeuds.end(); i++) {
		if (n.equals(i->first)) {
			return true;
		}
	}
	return false;
}
 
void AStar::ajouter_cases_adjacentes(Coordonnee& n) {
	Noeud *tmp = new Noeud();
	for (int i = n.getX() - 1; i <= n.getX() + 1; i++) {
		if (!(i < 0) && !(i >= this->damier.getNbRows())) {
			for (int j = n.getY() - 1; j <= n.getY() + 1; j++) {
				if (!(j < 0) && !(j >= this->damier.getNbColumns())) {
					Coordonnee* it = new Coordonnee(i, j);
					if (!n.equals(*it)) {
						if (this->damier.getElement(i, j) == NULL) {
							this->damier.elements[i][j] = new Element(
									&(this->damier), it);
							if (!this->damier.getElement(i, j)->isObstacle()) {
								if (!deja_present_dans_liste(*it, listeFermee)) {
									tmp->setCoutG(listeFermee[n].getCoutG()
											+ distance(*it, n));
									tmp->setCoutH(distance(*it,
											*(this->arrivee)));
									tmp->setCoutF(tmp->getCoutG()
											+ tmp->getCoutH());
									tmp->setParent(&n);
									if (deja_present_dans_liste(*it,
											listeOuverte)) {
										if (tmp->getCoutF()
												< listeOuverte[*it].getCoutF()) {
											listeOuverte[*it] = *tmp;
										}
									} else {
										Coordonnee c(i, j);
										listeOuverte.insert(make_pair(c, *tmp));
									}
								}
 
							}
						}
 
					}
				}
			}
		}
	}
}
 
Coordonnee AStar::meilleur_noeud(map<Coordonnee, Noeud>& l) {
	int m_coutf = l.begin()->second.getCoutF();
	Coordonnee m_noeud(l.begin()->first);
	map<Coordonnee, Noeud>::iterator i;
	for (i = l.begin(); i != l.end(); i++) {
		if (i->first == *(this->arrivee)) {
			m_noeud = i->first;
			break;
		}
 
		if (i->second.getCoutF() < m_coutf) {
			m_coutf = i->second.getCoutF();
			m_noeud = i->first;
		}
	}
	return m_noeud;
}
 
void AStar::ajouter_liste_fermee(Coordonnee& c) {
	Noeud& n = listeOuverte[c];
	// TODO Set Parent du dernier noeud de la liste fermee
 
	listeFermee[c] = n;
 
	if (listeOuverte.erase(c) == 0) {
		cerr << "Erreur le noeud n'apparait pas dans la liste ouverte" << endl;
	} else {
		cout << "Noeud apparait bien dans liste ouverte" << endl;
	}
}
 
void AStar::retrouver_chemin() {
	cout << "*** retrouver chemin ***" << endl;
	Noeud& tmp = listeFermee[Coordonnee(this->arrivee->getX(),
			this->arrivee->getY())];
 
	// Initialisation
	Coordonnee* n = Coordonnee::createRandomCoordonnee();
	Coordonnee prec = *(Coordonnee::createRandomCoordonnee());
 
	cout << "Fin initialisation" << endl;
 
	// Fonctionnement d'une liste chainée
	n->setX(this->arrivee->getX());
	n->setY(this->arrivee->getY());
	prec.setX(tmp.getParent()->getX());
	prec.setY(tmp.getParent()->getY());
	this->chemin.push_front(n);
 
	cout << "affichage de prec" << endl;
	prec.afficher();
 
	cout << "affichage du depart" << endl;
	this->depart->afficher();
 
	while (!(prec == (*(this->depart)))) {
		cout << "*****tmp.parent******" << endl;
		Coordonnee c = *(tmp.getParent());
		c.afficher();
		system("pause");
 
		cout << "*****n*****" << endl;
		n->afficher();
		system("pause");
 
		cout << "*****prec*****" << endl;
		prec.afficher();
		system("pause");
 
		n->setX(prec.getX());
		n->setY(prec.getY());
		chemin.push_front(n);
 
		tmp = listeFermee[*(tmp.getParent())];
 
		prec.setX(tmp.getParent()->getX());
		prec.setY(tmp.getParent()->getY());
 
		if(prec==*(this->depart))
			cout << "Le chemin a ete retrouve\n\n\n" << flush;
		else
			prec.afficher();
			cout << "pas encore arrive\n\n\n" << flush;
	}
}
 
void AStar::calculer_chemin(Agent& agent, Noeud& depart, Coordonnee& arrivee) {
 
	this->depart = agent.getCoordonnees();
	this->arrivee = &arrivee;
 
	depart.afficher();
 
	Coordonnee courant(*(depart.getParent()));
	cout << "affichage" << endl;
	courant.afficher();
 
	// Ajout de courant dans la liste ouverte
	listeOuverte.insert(make_pair(courant, depart));
	courant.afficher();
	listeOuverte[courant].afficher();
	ajouter_liste_fermee(courant);
	ajouter_cases_adjacentes(courant);
 
	// Tant que la destination n'a pas été atteinte
	while (!courant.equals(*(this->arrivee)) && !(listeOuverte.empty())) {
		cout << "courant=";
		courant.afficher();
		cout << endl;
		cout << "arrivee";
		(*(this->arrivee)).afficher();
		cout << endl;
		// On cherche le meilleur noeud de la liste ouverte
		this->arrivee->afficher();
		cout << "*** meilleur noeud ***" << endl;
		system("pause");
		courant = meilleur_noeud(listeOuverte);
		system("pause");
		cout << "*** ajout liste fermee ***" << endl;
		ajouter_liste_fermee(courant);
		system("pause");
		cout << "*** ajouter cases adjacentes ***" << endl;
		ajouter_cases_adjacentes(courant);
		system("pause");
		cout << "courant en fin=";
		courant.afficher();
		cout << endl;
	}
 
	cout
			<< "*******************************************************************"
			<< endl;
 
	// Si la destination est atteinte on remonte le chemin
	if (courant.equals(arrivee)) {
		retrouver_chemin();
		// On insere le chemin dans celui de l'agent
		agent.setChemin(this->chemin);
	} else {
		cout << "Pas de solution" << endl;
	}
 
}

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
/*
 * Noeud.cpp
 *
 *  Created on: 22 mars 2009
 *      Author: Ludovic
 */
 
#include "Noeud.h"
#include <iostream>
 
Noeud::Noeud() {
	// TODO Auto-generated constructor stub
 
}
 
Noeud::~Noeud() {
	// TODO Auto-generated destructor stub
}
 
int Noeud::getCoutG() const {
	return this->coutG;
}
 
int Noeud::getCoutH() const {
	return this->coutH;
}
 
int Noeud::getCoutF() const {
	return this->coutF;
}
 
Coordonnee* Noeud::getParent() const {
	return this->parent;
}
 
void Noeud::setCoutG(int coutG) {
	cout << "***Entree dans setCoutG()***" << endl;
	this->coutG = coutG;
}
 
void Noeud::setCoutH(int coutH) {
	this->coutH = coutH;
}
 
void Noeud::setCoutF(int coutF) {
	this->coutF = coutF;
}
 
void Noeud::setParent(Coordonnee *parent) {
	this->parent = parent;
}
 
void Noeud::afficher() {
	cout << "Cout F =" << this->getCoutF() << endl;
	cout << "Cout G = " << this->getCoutG() << endl;
	cout << "Cout H = " << this->getCoutH() << endl;
	cout << "X Parent = " << this->getParent()->getX() << endl;
	cout << "Y Parent = " << this->getParent()->getY() << endl;
}
 
Noeud& Noeud::operator =(Noeud& n2) {
	if (this != &n2) {
		this->coutG = n2.coutG;
		this->coutH = n2.coutH;
		this->coutF = n2.coutF;
		this->parent = new Coordonnee(*(n2.parent));
	}
	return *this;
 
}

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
/*
 * Coordonnee.cpp
 *
 *  Created on: 6 mars 2009
 *      Author: Ludovic
 */
 
#include <cstdlib>
#include <iostream>
#include "Coordonnee.h"
 
Coordonnee::Coordonnee(int x, int y) {
	this->x = x;
	this->y = y;
}
 
Coordonnee::~Coordonnee() {
 
}
 
//Coordonnee::Coordonnee(const Coordonnee & copie) {
//	this->x = copie.x;
//	this->y = copie.y;
//}
 
int Coordonnee::getX() const {
	return this->x;
}
 
int Coordonnee::getY() const{
	return this->y;
}
 
Coordonnee* Coordonnee::createRandomCoordonnee() {
	int x = 0 + (int) ((double) rand() / ((double) RAND_MAX + 1) * 10);
	int y = 0 + (int) ((double) rand() / ((double) RAND_MAX + 1) * 10);
	return new Coordonnee(x, y);
}
 
void Coordonnee::setX(int x) {
	this->x = x;
}
 
void Coordonnee::setY(int y) {
	this->y = y;
}
 
bool Coordonnee::equals(Coordonnee c) {
	return ((c.getX() == this->x) && (c.getY() == this->y));
}
 
bool Coordonnee::operator==(Coordonnee c) const {
	return ((c.getX() == this->x) && (c.getY() == this->y));
}
 
Coordonnee & Coordonnee::operator=(const Coordonnee & c2) {
	if (this != &c2) {
		this->x = c2.x;
		this->y = c2.y;
	}
	return *this;
}
 
bool Coordonnee::operator<(const Coordonnee & c) const {
	if (this->x != c.x) {
		return (this->x < c.x);
	} else {
		return (this->y < c.y);
	}
 
}
 
void Coordonnee::afficher() {
	cout << "X=" << this->getX() << ",Y=" << this->getY() << endl;
}

**lcfseth** · 27/03/2009, 06h07

Je peux me tromper, mais dans ta fonction, AStar::ajouter_cases_adjacentes.

Tu declare

Code :

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

Noeud *tmp = new Noeud();

avant les deux boucles de recherche des voisins.
Sauf erreur de ma part, dans ce cas la modification d'un des voisins, modifie automatiquement les autres. Je donne un exemple :

1 2 3 4 5
6 7 8 9 A
B C D E F

La case 8 est à la fois un voisin de 9 et de 7.
Si dans un premier temps, on passe par la case 9, on aura 9 comme parent de 3 4 5 8 A D E F.
Maintenant si on passe par 7 et que le cout de 8 par 7 est inferieur à celui de 8 par 9, on modifiera le parent de 8 qui deviendra 7.
Mais aussi, on va modifier le parent de tous les voisins 9, puisqu'il pointent tous vers le meme noeud.
donc on aura la case A (ainsi que 3 4 5 8 D E F) dont le parent devient 7 alors qu'on voit bien que A et 7 sont distant de 3 cases.

Enfin, je te conseille d'implementer ta liste ouverte en tant qu'arbre binaire, qui te retournera le meilleur noeud avec une complexité de O(1) ( suffit de prendre la racine de l'arbre ), ta liste fermé en tant que tableau de bool de la taille de la map, qui la aussi te donnera l'etat d'une case en O(1).

Aussi, quand c'est possible et sans augmentation de la charge memoire, faut eviter d'utiliser les pointeurs en c++, ca evite les problemes de modification involontaire des variables.
Dans le cas de l'A* tu peux utiliser un entier ( voir un byte) pour referencer un parent.

035
1x6
247

Pour retrouver un parent tu utilise un tableau appelé direction :

Coordonne [] direction
{ (-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1) };

**3DArchi** · 27/03/2009, 12h43

Bonjour,
D'un point de vue C++, il y a des choses qui ne vont pas ... et peut être sont à l'origine de ton problème :
1/ :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
	for (int i = n.getX() - 1; i <= n.getX() + 1; i++) {
		if (!(i < 0) && !(i >= this->damier.getNbRows())) {
			for (int j = n.getY() - 1; j <= n.getY() + 1; j++) {
				if (!(j < 0) && !(j >= this->damier.getNbColumns())) {
					Coordonnee* it = new Coordonnee(i, j);
					if (!n.equals(*it)) {
						if (this->damier.getElement(i, j) == NULL) {
							this->damier.elements[i][j] = new Element(
									&(this->damier), it);
							if (!this->damier.getElement(i, j)->isObstacle()) {
								if (!deja_present_dans_liste(*it, listeFermee)) {

--> 9 niveaux d'imbrication (+ encore 2 en dessou) = illisible + in-maintenable.
Il y a des choses que tu peux clairement simplifier :

Code :

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

1
2
3
 
for (int i = n.getX() - 1; i <= n.getX() + 1; i++) {
   if (!(i < 0) && !(i >= this->damier.getNbRows())) {

C'est équivalent à :

Code :

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

1
2
 
for (int i = MAX(n.getX() - 1,0; i <= MIN(n.getX() + 1,this->damier.getNbRows()); i++) {

2/

Code :

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

1
2
 
Noeud *tmp = new Noeud();

J'ai bien l'impression que ce pointeur se perd -> fuite mémoire
D'un façon plus globale, tu peux avoir beaucoup de fuite mémoire car tes pointeurs sont rarement libérés...

3/

Code :

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

1
2
3
4
5
	for (i = l_noeuds.begin(); i != l_noeuds.end(); i++) {
		if (n.equals(i->first)) {
			return true;
		}
	}

Tu as beaucoup de boucles de ce genre. Tu gagnerais à exploiter plus la STL:

Code :

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

return l_noeuds.find(n)!=l_noeuds.end();

En plus, ça allègerait ton code.

4/ Ne définit pas de constructeur qui ne font rien sauf si ta classe sera dérivée.
5/ Ne définit pas des opérateurs d'assignation ou des constructeurs par copie qui se contentent de faire une copie des membres. Le compilateur génère par défaut ces méthodes avec exactement ce comportement.

6/ Pourquoi définir des méthodes equals qui font exactement la même chose que la surcharge de l'opérateur == implémenté ? Un des 2 est redondant (au pire un des 2 devrait faire appel à l'autre).

En fait, je pense qu'en travaillant à simplifier ton code, ton erreur t'apparaîtra plus clairement.

**ludo2612** · 27/03/2009, 18h50

Je tiens à vous remercier pour tous vos commentaires sur ce code.
Ils m'ont vraiment paru important les uns autant que les autres.

Ceci est le fruit d'un projet scolaire qui a été fait avec précipitation c'est pourquoi il n'a souvent pas été réfléchi. Vos remarques sont donc tout à fait justifiées.

Pour information, ce projet a été rendu et la recherche de chemin fonctionne correctement. Cependant, je pense qu'il peut-être largement amélioré notamment d'un point de vue qualité.

Pour mon développement personnel je pense que je vais retoucher ce code d'ici peu pour le rendre beaucoup plus propre.

Encore merci!

Implémentation de l'algorithme A*

Intelligence artificielle

Discussions similaires

Partager

Partager