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
|
struct noeud{
float cout_g, cout_h, cout_f;
pair<int,int> parent; // 'adresse' du parent (qui sera toujours dans la map fermée
};
typedef map< pair<int,int>, noeud> l_noeud;
class CClient : public CPosition // Point de raliement entre chaque deplacement de clients,... //
{
public:
CClient();
void CreateZone(TPaintBox *pBox, TMemo *aMemo, std::vector<CClient> &aClient, CClient *TClient, long X, long Y, int pWidth, int pHeight);
void Process(CClient *TClient);
void retrouver_chemin(CClient *pClient);
// void DisplayWay(CClient *pClient, pair<int,int>& p);
void ajouter_cases_adjacentes(CClient *pClient, pair<int,int>&);
bool deja_present_dans_liste(pair<int,int>, l_noeud&);
pair<int,int> meilleur_noeud(l_noeud&);
void ajouter_liste_fermee(CClient *pClient, pair<int,int>&);
int Rayon;
TPoint *Limited1; // Point de limitation //
TPoint *Limited2;
TPoint *arrivee;
pair <int, int> courant; // Courant = progression du point
noeud depart;
l_noeud liste_ouverte; // Points a retenir //
l_noeud liste_fermee;
list<TPoint> chemin; // CHemin de retour //
};
/////////////////////////////////////////////////////
void CClient::Process(CClient *TClient)
{
if( !((TClient->courant.first == TClient->arrivee->x) && (TClient->courant.second == TClient->arrivee->y))
&&
(!TClient->liste_ouverte.empty())
){
// on cherche le meilleur noeud de la liste ouverte, on sait qu'elle n'est pas vide donc il existe
TClient->courant = TClient->meilleur_noeud(TClient->liste_ouverte);
// on le passe dans la liste fermee, il ne peut pas déjà y être
TClient->ajouter_liste_fermee(TClient,TClient->courant);
TClient->ajouter_cases_adjacentes(TClient,TClient->courant);
pBoxTerre->Canvas->Pixels[TClient->courant.first ][TClient->courant.second] = clRed;
}
if ((TClient->courant.first == TClient->arrivee->x) && (TClient->courant.second == TClient->arrivee->y)){
TClient->retrouver_chemin(TClient);
}
else{
// PAS DE SOLUTION
}
}
void CClient::ajouter_cases_adjacentes(CClient *pClient, pair <int,int>& n)
{
noeud tmp;
// on met tous les noeud adjacents dans la liste ouverte (+vérif)
for (int i=n.first-1; i<=n.first+1; i++){
if ((i<pClient->Limited1->x) || (i>=pClient->Limited2->x)) continue;
for (int j=n.second-1; j<=n.second+1; j++){
if ((j<pClient->Limited1->y) || (j>=pClient->Limited2->y)) continue;
if ((i==n.first) && (j==n.second)) continue; // case actuelle n
//if (pBoxTerre->Canvas->Pixels[i][j] == StringToColor("0x00FFFFFF") || pBoxTerre->Canvas->Pixels[i][j]==clFire || pBoxTerre->Canvas->Pixels[i][j]==clFireC || pBoxTerre->Canvas->Pixels[i][j]==StringToColor("0x00BAA16F")) continue; // ACHANGER /*pBoxTerre->Canvas->Pixels[i][j]!=clWhite ||*/
// obstacle, terrain non franchissable
if (pBoxTerre->Canvas->Pixels[i][j]==clBlack) continue;
pair<int,int> it(i,j);
if (!pClient->deja_present_dans_liste(it, pClient->liste_fermee)){
/* le noeud n'est pas déjà présent dans la liste fermée */
tmp.cout_g = pClient->liste_fermee[n].cout_g + distance(i,j,n.first,n.second);
tmp.cout_h = distance(i,j,arrivee->x,arrivee->y);
tmp.cout_f = tmp.cout_g + tmp.cout_h;
tmp.parent = n;
if (pClient->deja_present_dans_liste(it, pClient->liste_ouverte)){
/* le noeud est déjà présent dans la liste ouverte, il faut comparer les couts */
if (tmp.cout_f < pClient->liste_ouverte[it].cout_f){
/* si le nouveau chemin est meilleur, on update */
pClient->liste_ouverte[it]=tmp;
}
/* le noeud courant a un moins bon chemin, on ne change rien */
}else{
/* le noeud n'est pas présent dans la liste ouverte, on l'ajoute */
pClient->liste_ouverte[pair<int,int>(i,j)]=tmp;
}
}
}
}
}
bool CClient::deja_present_dans_liste(pair<int,int> n, l_noeud& l){
l_noeud::iterator i = l.find(n);
if (i==l.end())
return false;
else
return true;
}
pair<int,int> CClient::meilleur_noeud(l_noeud& l){
float m_coutf = l.begin()->second.cout_f;
pair<int,int> m_noeud = l.begin()->first;
for (l_noeud::iterator i = l.begin(); i!=l.end(); i++)
if (i->second.cout_f< m_coutf){
m_coutf = i->second.cout_f;
m_noeud = i->first;
}
return m_noeud;
}
void CClient::ajouter_liste_fermee(CClient *pClient, pair<int,int>& p){
noeud& n = pClient->liste_ouverte[p];
pClient->liste_fermee[p]=n;
// il faut le supprimer de la liste ouverte, ce n'est plus une solution explorable
if (pClient->liste_ouverte.erase(p)==0)
{pClient->liste_ouverte.erase(p); }
return;
}
void CClient::retrouver_chemin(CClient *pClient){
// l'arrivée est le dernier élément de la liste fermée.
l_noeud::iterator i = pClient->liste_fermee.end();
i--;
noeud& tmp = i->second;
TPoint n;
pair<int,int> prec;
n.x = pClient->arrivee->x;
n.y = pClient->arrivee->y;
prec.first = tmp.parent.first;
prec.second = tmp.parent.second;
pClient->chemin.push_front(n);
while (prec != pair<int,int>(pClient->depart.parent.first,pClient->depart.parent.second)){
n.x = prec.first;
n.y = prec.second;
pClient->chemin.push_front(n);
tmp = pClient->liste_fermee[tmp.parent];
prec.first = tmp.parent.first;
prec.second = tmp.parent.second;
pBoxTerre->Canvas->Pixels[prec.first ][prec.second] = clBlue;
}
} |
2D C++ : Améliorer Recherche chemin le plus court
Répondre avec citation
Partager