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;
}
} |
Partager