Discussion :

[yannoo95170]

Je suis parti d'un exemple trouvé sur Wikipédia et l'ai légèrement modifié pour tourner avec une map de 80x50

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
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
 
// Astar.cpp
// initial source from http://en.wikipedia.org/wiki/A*
// initial Compiler: Dev-C++ 4.9.9.2
// initial FB - 201012256
 
// modifications from Cyclone 21 october 2021 (g++ 7.5.0)
// change the default width and height from 60x60 to 80x25 (default screen page size)
// add the display of the map and displacments steps
// add the loading and saving of the map (default = default.map) 
 
// TODO : use width and height instead m and n 
// TODO : handle user specified width and height into .map files
// TODO : handle the loading/conversion of a picture file instead a .map file ?
// TODO : make a library from this than can be easily use it into another projet
// TODO : adapt it for the Arduino plateform  
 
 
#include <iostream>
#include <iomanip>
#include <queue>
#include <string>
#include <math.h>
#include <ctime>
#include <string.h>
using namespace std;
 
// const int n=60; // horizontal size of the map
// const int m=60; // vertical size size of the map
const int m = 80;
const int n = 50;
 
// static int map[n][m];
static char map[n][m];
static int closed_nodes_map[n][m]; // map of closed (tried-out) nodes
static int open_nodes_map[n][m]; // map of open (not-yet-tried) nodes
static int dir_map[n][m]; // map of directions
const int dir=8; // number of possible directions to go at any position
// if dir==4
//static int dx[dir]={1, 0, -1, 0};
//static int dy[dir]={0, 1, 0, -1};
// if dir==8
static int dx[dir]={1, 1, 0, -1, -1, -1, 0, 1};
static int dy[dir]={0, 1, 1, 1, 0, -1, -1, -1};
 
int Steps[n][m];
int nSteps = 0;
 
class node
{
    // current position
    int xPos;
    int yPos;
    // total distance already travelled to reach the node
    int level;
    // priority=level+remaining distance estimate
    int priority;  // smaller: higher priority
 
    public:
        node(int xp, int yp, int d, int p) 
            {xPos=xp; yPos=yp; level=d; priority=p;}
 
        int getxPos() const {return xPos;}
        int getyPos() const {return yPos;}
        int getLevel() const {return level;}
        int getPriority() const {return priority;}
 
        void updatePriority(const int & xDest, const int & yDest)
        {
             priority=level+estimate(xDest, yDest)*10; //A*
        }
 
        // give better priority to going strait instead of diagonally
        void nextLevel(const int & i) // i: direction
        {
             level+=(dir==8?(i%2==0?10:14):10);
        }
 
        // Estimation function for the remaining distance to the goal.
        const int & estimate(const int & xDest, const int & yDest) const
        {
            static int xd, yd, d;
            xd=xDest-xPos;
            yd=yDest-yPos;         
 
            // Euclidian Distance
            d=static_cast<int>(sqrt(xd*xd+yd*yd));
 
            // Manhattan distance
            //d=abs(xd)+abs(yd);
 
            // Chebyshev distance
            //d=max(abs(xd), abs(yd));
 
            return(d);
        }
};
 
// Determine priority (in the priority queue)
bool operator<(const node & a, const node & b)
{
  return a.getPriority() > b.getPriority();
}
 
// A-star algorithm.
// The route returned is a string of direction digits.
string pathFind( const int & xStart, const int & yStart, 
                 const int & xFinish, const int & yFinish )
{
    static priority_queue<node> pq[2]; // list of open (not-yet-tried) nodes
    static int pqi; // pq index
    static node* n0;
    static node* m0;
    static int i, j, x, y, xdx, ydy;
    static char c;
 
    char str[10];
    string path2, path3;
 
    pqi=0;
 
    // reset the node maps
    for(y=0;y<m;y++)
    {
        for(x=0;x<n;x++)
        {
            closed_nodes_map[x][y]=0;
            open_nodes_map[x][y]=0;
        }
    }
 
    // create the start node and push into list of open nodes
    n0=new node(xStart, yStart, 0, 0);
    n0->updatePriority(xFinish, yFinish);
    pq[pqi].push(*n0);
    open_nodes_map[x][y]=n0->getPriority(); // mark it on the open nodes map
 
    // A* search
    while(!pq[pqi].empty())
    {
        // get the current node w/ the highest priority
        // from the list of open nodes
        n0=new node( pq[pqi].top().getxPos(), pq[pqi].top().getyPos(), 
                     pq[pqi].top().getLevel(), pq[pqi].top().getPriority());
 
        x=n0->getxPos(); y=n0->getyPos();
 
        pq[pqi].pop(); // remove the node from the open list
        open_nodes_map[x][y]=0;
        // mark it on the closed nodes map
        closed_nodes_map[x][y]=1;
 
        // quit searching when the goal state is reached
        //if((*n0).estimate(xFinish, yFinish) == 0)
        if(x==xFinish && y==yFinish) 
        {
            // generate the path from finish to start
            // by following the directions
            string path="";
            while(!(x==xStart && y==yStart))
            {
                j=dir_map[x][y];
                c='0'+(j+dir/2)%dir;
                path=c+path;
 
		// sprintf(str, "(%2d,%2d) ", x, y );
		// path2 = string(str) + path2;
 
		// sprintf(str, "(%+d,%+d) ", -dx[j], -dy[j] );
		// path3 = string(str) + path3;
 
 
                x+=dx[j];
                y+=dy[j];
            }
 
            // garbage collection
            delete n0;
            // empty the leftover nodes
            while(!pq[pqi].empty()) pq[pqi].pop(); 
 
	    // sprintf(str, "(%2d,%2d) ", xStart, yStart );
    	    // path2 = string(str) + path2;
	    // cout << "Route : " << path2 << endl;
	    // cout << "Moves : " << path3 << endl;
 
            return path;
        }
 
        // generate moves (child nodes) in all possible directions
        for(i=0;i<dir;i++)
        {
            xdx=x+dx[i]; ydy=y+dy[i];
 
            if(!(xdx<0 || xdx>n-1 || ydy<0 || ydy>m-1 || map[xdx][ydy]==1 
                || closed_nodes_map[xdx][ydy]==1))
            {
                // generate a child node
                m0=new node( xdx, ydy, n0->getLevel(), 
                             n0->getPriority());
                m0->nextLevel(i);
                m0->updatePriority(xFinish, yFinish);
 
                // if it is not in the open list then add into that
                if(open_nodes_map[xdx][ydy]==0)
                {
                    open_nodes_map[xdx][ydy]=m0->getPriority();
                    pq[pqi].push(*m0);
                    // mark its parent node direction
                    dir_map[xdx][ydy]=(i+dir/2)%dir;
                }
                else if(open_nodes_map[xdx][ydy]>m0->getPriority())
                {
                    // update the priority info
                    open_nodes_map[xdx][ydy]=m0->getPriority();
                    // update the parent direction info
                    dir_map[xdx][ydy]=(i+dir/2)%dir;
 
                    // replace the node
                    // by emptying one pq to the other one
                    // except the node to be replaced will be ignored
                    // and the new node will be pushed in instead
                    while(!(pq[pqi].top().getxPos()==xdx && 
                           pq[pqi].top().getyPos()==ydy))
                    {                
                        pq[1-pqi].push(pq[pqi].top());
                        pq[pqi].pop();       
                    }
                    pq[pqi].pop(); // remove the wanted node
 
                    // empty the larger size pq to the smaller one
                    if(pq[pqi].size()>pq[1-pqi].size()) pqi=1-pqi;
                    while(!pq[pqi].empty())
                    {                
                        pq[1-pqi].push(pq[pqi].top());
                        pq[pqi].pop();       
                    }
                    pqi=1-pqi;
                    pq[pqi].push(*m0); // add the better node instead
                }
                else delete m0; // garbage collection
            }
        }
        delete n0; // garbage collection
    }
    return ""; // no route found
}
 
void MakeMap()
{
    // create empty map
    for(int y=0;y<m;y++)
    {
        for(int x=0;x<n;x++) map[x][y]=0;
    }
 
    // fillout the map matrix with a '+' pattern
    for(int x=n/8;x<n*7/8;x++)
    {
        map[x][m/2]=1;
    }
    for(int y=m/8;y<m*7/8;y++)
    {
        map[n/2][y]=1;
    }
}
 
void SaveMap( char *filename )
{
	FILE *f; 
 
	f = fopen(filename, "w");
	for( int y = 0 ; y < n ; y++ )
	{
		for( int x = 0 ; x < m ; x++)
		{
			fprintf(f, (map[x][y] ? "." : " ") );
		}
 
		fprintf(f, "\n");
	}
 
	fclose(f);	
}
 
void LoadMap( char *filename )
{
	FILE *f; 
	char  empty;
	char buffer[160];
	int len;
	int x = 0;
	int y = 0;
 
	f = fopen(filename, "r");
	while ( !feof( f ) )
	{
		fgets( buffer, 160, f);
		len = strlen(buffer) - 1;
 
		for( x = 0 ; x < len ; x++ )
		{
			map[x][y] = ( buffer[x] == ' ' ? 0 : 1);
		}  
 
		y++;
	}
	fclose(f);
}
 
 
int main( int argc, char **argv )
{
    int steps = 0;
 
    srand(time(NULL));
 
    if ( argc > 1 )
    {
	LoadMap( argv[1]  );
    }
    else
    {
    	MakeMap();
    	SaveMap( "default.map" );
    }
 
    // randomly select start and finish locations
    int xA, yA, xB, yB;
    switch(rand()%8)
    {
        case 0: xA=0;yA=0;xB=n-1;yB=m-1; break;
        case 1: xA=0;yA=m-1;xB=n-1;yB=0; break;
        case 2: xA=n/2-1;yA=m/2-1;xB=n/2+1;yB=m/2+1; break;
        case 3: xA=n/2-1;yA=m/2+1;xB=n/2+1;yB=m/2-1; break;
        case 4: xA=n/2-1;yA=0;xB=n/2+1;yB=m-1; break;
        case 5: xA=n/2+1;yA=m-1;xB=n/2-1;yB=0; break;
        case 6: xA=0;yA=m/2-1;xB=n-1;yB=m/2+1; break;
        case 7: xA=n-1;yA=m/2+1;xB=0;yB=m/2-1; break;
    }
 
    cout<<"Map Size (X,Y): "<<n<<","<<m<<endl;
    cout<<"Start: (" << xA << "," << yA << ")" << endl;
    cout<<"Finish:(" << xB << ", "<< yB << ")" << endl;
    // get the route
    clock_t start = clock();
    string route=pathFind(xA, yA, xB, yB);
    if(route=="") cout<<"An empty route generated!"<<endl;
    clock_t end = clock();
    double time_elapsed = double(end - start);
    cout<<"Time to calculate the route : " << time_elapsed * 1000 / CLOCKS_PER_SEC << " ms" << endl << endl;
 
    // follow the route on the map and display it 
    if(route.length()>0)
    {
        int j; 
	char c;
        int x=xA;
        int y=yA;
        map[x][y]=2;
        for(int i=0;i<route.length();i++)
        {
            c =route.at(i);
            j=atoi(&c); 
            x=x+dx[j];
            y=y+dy[j];
            map[x][y]=3;
	    Steps[x][y] = ++nSteps;
        }
        map[x][y]=4;
 
	// cout << "Number of steps " << nSteps << endl << endl; 
 
        // display the map with the route
        for(int y=0;y<m;y++)
        {
            for(int x=0;x<n;x++)
	    {
                if(map[x][y]==0)
                    // cout<<".";
		    cout << " ";
                else if(map[x][y]==1)
                    // cout<<"O"; //obstacle
		    cout << ".";
                else if(map[x][y]==2)
                    cout<<"S"; //start
                else if(map[x][y]==3)
                    // cout<<"R"; //route
		    cout << Steps[x][y] % 10;
                else if(map[x][y]==4)
                    // cout<<"F"; //finish
		    cout<<"E";
	    }
            cout<<endl;
        }
    }
 
    cout << endl << "Route(" << nSteps << ") : ";
    for(int i = 0;i<route.length();i++)
    {
	int j;
        char c;
	char str[10];
 
        c = route.at(i);
        j = atoi(&c); 
	// cout << "(" << dx[j] << "," << dy[j] << ") ";
	sprintf(str, "(%+d,%+d) ", dx[j], dy[j] );
	cout << str;  
    }
    cout << endl;
 
    // getchar(); // wait for a (Enter) keypress  
    return(0);
}

Ca semble vraiment super rapide sur mon PC, cf. entre 50 et 150 ms avec un processeur Intel Xeon à 3.3 Ghz
(le point de départ et d'arrivée sont choisis aléatoirement et la map par défaut en un simple grande croix au milieu de la salle)
[sans paramêtre, ça crée le fichier texte default.map que l'on peut recopier ou modifier pour l'utiliser en le mettant en argument du programme]

Ca se compile très simplement

Code :

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

1
2
 
g++ Astar.cpp -o Astar

Et ça donne quelque chose comme ça :
(on peux aussi recopier et légèrement transformer le fichier .map pour l'utiliser en rajoutant son nom en argument)
[par défaut, il construit et utilise le fichier default.map qui est une grande croix au milieu de la salle]
[il semble y avoir unee inversion entre les axes utilisés dans le fichier et ceux utilisés dans le programme mais ce n'est pas trop grave pour les premiers tests + programme converti très vite "à la volée"]

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
 
yannoo@cyclone ~/Dev/Chemins $ ./Astar
Map Size (X,Y): 50,80
Start: (0,0)
Finish:(49, 79)
Time to calculate the route : 120.371 ms
 
S                                                 
1                                                 
2                                                 
3                                                 
4                                                 
5                                                 
6                                                 
7                                                 
8                                                 
9                                                 
0                        .                        
1                        .                        
2                        .                        
3                        .                        
4                        .                        
5                        .                        
6                        .                        
7                        .                        
8                        .                        
9                        .                        
0                        .                        
1                        .                        
2                        .                        
3                        .                        
4                        .                        
5                        .                        
6                        .                        
7                        .                        
8                        .                        
 9                       .                        
 0                       .                        
 1                       .                        
  2                      .                        
  3                      .                        
   4                     .                        
   5                     .                        
   6                     .                        
    7                    .                        
    8                    .                        
     9                   .                        
     0.....................................       
      1                  .                        
       2                 .                        
        3                .                        
        4                .                        
         5               .                        
          6              .                        
           7             .                        
            8            .                        
            9            .                        
             0           .                        
              1          .                        
               2         .                        
                3        .                        
                 4       .                        
                  5      .                        
                  6      .                        
                   7     .                        
                    8    .                        
                     9   .                        
                      0  .                        
                       1 .                        
                        2.                        
                        3.                        
                        4.                        
                        5.                        
                        6.                        
                        7.                        
                        8.                        
                        9.                        
                         0                        
                          1                       
                           2                      
                            3456                  
                                78901             
                                     23456        
                                          789     
                                             012  
                                                3 
                                                 E
 
Route(94) : (+0,+1) (+0,+1) (+0,+1) (+0,+1) (+0,+1) (+0,+1) (+0,+1) (+0,+1) (+0,+1) (+0,+1) (+0,+1) (+0,+1) (+0,+1) (+0,+1) (+0,+1) (+0,+1) (+0,+1) (+0,+1) (+0,+1) (+0,+1) (+0,+1) (+0,+1) (+0,+1) (+0,+1) (+0,+1) (+0,+1) (+0,+1) (+0,+1) (+1,+1) (+0,+1) (+0,+1) (+1,+1) (+0,+1) (+1,+1) (+0,+1) (+0,+1) (+1,+1) (+0,+1) (+1,+1) (+0,+1) (+1,+1) (+1,+1) (+1,+1) (+0,+1) (+1,+1) (+1,+1) (+1,+1) (+1,+1) (+0,+1) (+1,+1) (+1,+1) (+1,+1) (+1,+1) (+1,+1) (+1,+1) (+0,+1) (+1,+1) (+1,+1) (+1,+1) (+1,+1) (+1,+1) (+1,+1) (+0,+1) (+0,+1) (+0,+1) (+0,+1) (+0,+1) (+0,+1) (+0,+1) (+1,+1) (+1,+1) (+1,+1) (+1,+1) (+1,+0) (+1,+0) (+1,+0) (+1,+1) (+1,+0) (+1,+0) (+1,+0) (+1,+0) (+1,+1) (+1,+0) (+1,+0) (+1,+0) (+1,+0) (+1,+1) (+1,+0) (+1,+0) (+1,+1) (+1,+0) (+1,+0) (+1,+1) (+1,+1)

Je pense que ça devrait tourner dans les 3.3 Ghz / 10 Mhz = 330x plus lentement sur l'ESP32 (10 Mhz pour l'ESP32 vs 3.3 Ghz pour le PC]
=> disons qu'avec une moyenne de 100 ms sur le PC, ça devrait donner dans les 330x plus lent sur l'ESP32, soit 330 * 100 ms = 33 000 ms = 33 secondes ...
==> le problème est cash ici mis en évidence car il est hors de question que l'ESP ne puisse effectuer qu'un déplacement toutes les 33 secondes, ce qui est très très loin du temps réel que je voudrais obtenir où la seconde est déjà une limite supérieure bien haute ...

Néanmoins, après réflexion, le problème est partiellement résolu car au bout de 33 secondes, c'est l'ensemble du chemin qui serait calculé, cf. les 94 mouvement indiqués après le "Route(94) :" , pas seulement un seul
=> 33 000 ms / 94 pas = environ 351 ms par pas donc ça devrait le faire avec l'algo Astar si j'arrive à le modifier afin qu'il donne les pas un par un, docn en gros toutes les 350 ms, et non pas tout le chemin en entier seulement à la fin au boût de 33 secondes
(mais j'ai un gros doute sur le sujet car l'algo semble bien plus fonctionner de façon globale pour donner seulement le chemin à la fin que de façon incrémentale pour me donner les déplacements à faire un par un ... )

De l'autre côté, si je gère ça en dynamique les points sources et destination ne seront jamais bien loin l'un de l'autre, les robots jouets partant à proximité du robot aspirateur et le suivront avec une distance relativement faible, donc ça devrait le faire
=> je ferais quelques tests les prochains jours en essayant d'ajouter à ce programme la gestion de plusieurs robots différents (les fantomes dans Pac Man) qui suivront systématiquement à relativement faible distance les déplacement du robot aspirateur (Pac Man)
==> avec un peu/beaucoup de bol, ça pourrait le faire assez vite en individuel sur chacun des ESP32 et je pourrais alors cloturer ce post

A noter qu'au pire, le PC semble déjà capable d'envoyer les ordres de déplacement à chacun des 4 robots jouets en 4 x 100 ms en moyenne = 400 ms en moyenne = largement 2 fois par seconde à chacun des 4 robots donc le post sera assez certainement cloturé vite fait
(m'enfin bon, vu que je suis vraiment hyper têtu, normal car breton , j'aimerais bien que chacun des robots puisse suivre son chemin de façon autonome même si le PC est éteint => mais ça se sera pour ma tronche et après avoir cloturé ce fil sur ce forum, j'irais sur un forum dédié aux Arduinos pour voir comment on peut optimiser ça pour cette plateforme )

[Bousk]

Ton code est en C++. Et franchement discutable.
Ici c'est le forum C.
Tu sais ce que tu fais depuis le début ?
D'abord tu te focalises sur une soit disant vitesse d'exécution sans jamais écrire la moindre ligne, ensuite tu connais pas A* qui est la base de recherche de chemin le plus court, et maintenant tu prends un code C++ alors que tu postes dans un forum C.
Kamoulox gagnant, je compile mon linker et j'exécute le préprocesseur en Rust.

const int & estimate est ridicule.
Des tableaux C partout, une collection d'include qui semble inutiles, des variables globales de partout, dont certains compteurs.
Des fuites mémoires énormes dans string pathFind, des allocations dynamiques inutiles.
Ma foi, si ça te plait, alors fais-toi plaisir avec ce code.

Ca semble vraiment super rapide sur mon PC, cf. entre 50 et 150 ms avec un processeur Intel Xeon à 3.3 Ghz

50-150ms pour... trouver un chemin dans une map de 50*80 ? On est loin d'un résultat correct, ton truc tourne à... ~3-10fps, juste pour trouver un chemin, dans une map de taille ridicule.

[dalfab]

Ca semble vraiment super rapide sur mon PC, cf. entre 50 et 150 ms avec un processeur Intel Xeon à 3.3 Ghz

Pas si rapide que cela si on tient compte de la puissance de ton CPU. Comment fait un petit GPS quand il doit trouver en quelques secondes un itinéraire parmi des millions de routes?

==> le problème est cash ici mis en évidence car il est hors de question que l'ESP ne puisse effectuer qu'un déplacement toutes les 33 secondes, ce qui est très très loin du temps réel que je voudrais obtenir où la seconde est déjà une limite supérieure bien haute ...

Néanmoins, après réflexion, le problème est partiellement résolu car au bout de 33 secondes, c'est l'ensemble du chemin qui serait calculé, cf. les 94 mouvement indiqués après le "Route(94) :" , pas seulement un seul
=> 33 000 ms / 94 pas = environ 351 ms par pas donc ça devrait le faire avec l'algo Astar si j'arrive à le modifier afin qu'il donne les pas un par un, docn en gros toutes les 350 ms, et non pas tout le chemin en entier seulement à la fin au boût de 33 secondes
(mais j'ai un gros doute sur le sujet car l'algo semble bien plus fonctionner de façon globale pour donner seulement le chemin à la fin que de façon incrémentale pour me donner les déplacements à faire un par un ... )

Oui le chemin est trouvé rapidement, mais oui ne ne peut le savoir qu'une fois que tous les chemins ont été évalués Tant que l'on n'a pas les 94 pas on n'a aucune idée où aller.

Le code que tu présentes semple pourtant optimisé, il utilise ce que l'on appelle un heuristique. L'idée est de tester en premier les itinéraires les plus plausibles (par exemple, aller vers la destination semble mieux que s'en éloigner), et aussi de savoir que l'itinéraire idéal a été trouvé avant de parcourir toutes les possibilités (par exemple, si on a trouvé un premier chemin de longueur L, tous les points où on a : longueur du chemin courant + distance restante en ligne droite qui dépasse L est forcément une piste a ne plus investiguer.) C'est l'heuristique de Dijkstra.

On peut aussi utiliser des heuristiques avec une forte probabilité d'avoir le meilleur chemin sans certitude que ça soit le meilleur. Dans ce cas c'est surement une bonne manière de faire. Je ne connais pas ces heuristiques mais ça doit pouvoir se trouver.

Mais il semble que découper la zone à parcourir en petits carrés, puis de se balader entre les carrés ne fait multiplier des points de calculs. C'est cela qui me semble être la cause de la lenteur. Là ça dépend surtout du format de tes données en entrées.
si on part de ton schéma; On ne va pas s'intéresser aux murs mais aux "portes". On recherche les éventuels points de passages obligés:

Code :

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

1
2
3
4
5
6
7
|---------------------------|
|    A                      |
|                  D        |
|---e ------g -------i ---- | 
|                           |
| B               C         |
|---------------------------|

Puis on essaie de rejoindre tous les points A,B,C,D,e,g,i en ligne droite, si ça traverse un mur c'est rejeté. Il reste alors la liste des possibilités: (A,e)(A,g)(A,i)(A,D)(D,e)(D,g)(D,i)(e,B)(e,C)(g,B)(g,C)(i,B)(i,C)(B,C) chacune ayant sa longueur. On voit que la solution pour A=>C en (A,g)(g,C) sera alors trouvée quasi-instantanément. S'il n'y a quelques dizaines de murs, la méthode sera nettement plus optimale.

[sambia39]

Bonsoir,

Si on prend le problème tel qu'il est, en ignorant les contraintes de mémoire et de vitesse, c'est-à-dire "trouver le meilleur chemin entre les points source et destination", cela reviendrait à trouver le plus court chemin d'un sommet à un autre sommet. Un algorithme admissible et simple comme celui de Dijkstra ou ses différentes variantes, seront en mesure de satisfaire vos attentes en fournissant une solution optimale.

Cependant, compte tenu de votre contrainte liée à la rapidité ; un algorithme heuristique comme A* (algorithme heuristique, car il va utiliser des méthodes de calcul dont le but est de fournir rapidement une solution qui n'est pas nécessairement optimale ou exacte.) semble être le choix le plus adapté. Sauf que vous avez ajouté au problème initial une autre contrainte qui est une contrainte spatiale (avoir une faible empreinte mémoire). Cela oblige l'utilisation d'une variante de l'algorithme A* puisqu'il n'est pas forcément adapté à une contrainte de faible empreinte mémoire ; car ce dernier (A*) peut nécessiter une mémoire exponentielle, puisqu'il doit explorer des chemins prometteurs. Heureusement, il existe des algorithmes heuristiques dérivées de l'algorithme 'A* qui utilisent une mémoire limitée ou fortement limitée, je pense par exemple à 'SMA*' ou IDA*.

D'un autre point de vue, il est tout à fait possible d'obtenir une solution adéquate sans utiliser des algorithmes heuristiques. Pour cela, il ne s'agit pas de repenser le problème en fonction d'un algorithme donné, mais de reconstruire la représentation de votre graphe de manière différente, dans un but précis d'optimisation spatiale et temporelle. En termes plus clairs, d'avoir une représentation des données qui satisfait à la fois les contraintes de vitesse et d’espace mémoire.

Ainsi, pour un gain d'espace et de rapidité, il faudra oublier les représentations de données des deux familles de représentation d'un graphe traditionnel, à savoir une matrice et une liste car la première famille (matrice) même si elle permet un accès rapide, elle a une forte empreinte mémoire (complexité spatiale) car, pour un graphe orienté ou non (à titre d’exemple une matrice d'adjacence), l'espace mémoire est de "N²" pour un graphe de taille "N" ce qui oblige à utiliser une représentation par liste. Sauf que la représentation par liste implique une perte de vitesse d'accès aux éléments et donc ne satisfait pas la contrainte liée à la vitesse.

La solution est alors une représentation du graphe sous la forme d'un tableau associatif dont les clés sont les sommets et les valeurs de chaque clé est un tableau qui représente uniquement le chemin optimal ou le prochain sommet optimal à atteindre, ce qui garantit la rapidité d'accès aux éléments du tableau en un temps constant avec une faible empreinte mémoire. Cette façon de faire oblige à ne garder que les chemins optimaux. Et la construction du graphe se fait en une seule fois.
Quant à la reconstruction des chemins optimaux dynamiquement (obtention de nouveaux chemins plus courts), elle n'est possible que dans des cas spécifiques exemples :
Si le graphe est étendu ; nouveau ou si l'ensemble des chemins optimaux est mis à jour. Et si en raison d'un événement (obstacle), il y a une mise à jour uniquement du chemin source actuelle vers le chemin destination.

Cela implique pour le dernier point mentionné précédemment, un partage d'informations entre différents agents (comme un robot explorateur qui partage sa solution avec tous les autres et que les autres n'ont pas besoin de recalculer toutes les solutions). Pour faire une analogie, c'est un peu comme si vous étiez sur la route 66 et qu'au kilomètre 25, il y avait un embouteillage ; soudain, le GPS vous suggère l'itinéraire alternatif optimal (contournant l'embouteillage) en suggérant de prendre la prochaine sortie avant d'être pris dans l'embouteillage et ceci grâce à l’événement déclencheur en amont.

Néanmoins, l'utilisation d'un algorithme heuristique basée sur A* reste le meilleur moyen de résoudre vos problèmes.

À bientôt.

[Sve@r]

Bonjour

La solution est alors une représentation du graphe sous la forme d'un tableau associatif dont les clés sont les sommets et les valeurs de chaque clé est un tableau qui représente uniquement le chemin optimal ou le prochain sommet optimal à atteindre, ce qui garantit la rapidité d'accès aux éléments du tableau en un temps constant avec une faible empreinte mémoire.

Manque de bol, les tableaux associatifs n'existent pas en C. On peut les recréer bien entendu (après-tout des langages comme Python ou bash qui connaiissent les tableaux associatifs sont écrits en C) mais quid de la mémoire nécessaire à créer ces outils ?

Et puis le PO demande "comment trouver le chemin" et ta réponse c'est "la solution est de créer un tableau associatif qui contient le sommet et le chemin". Ben oui mais il n'en reste pas moins que pour créer ce tableau contenant le chemin il faut d'abord le trouver ce chemin

[foetus]

Ben oui mais il n'en reste pas moins que pour créer ce tableau contenant le chemin il faut d'abord le trouver ce chemin

Il faut faire comme @dalfab

Il faut insérer 1 point temporaire par trou dans 1 mur. Et le poids d'1 segment, c'est la distance entre les 2 points.


Édit : 2 points sont reliés s'il n'y a pas de mur - il faut faire des tests intersection avec les murs, mais comme les murs sont fixes, il ne faut le faire qu'à l'initailisation je pense.

[sambia39]

Bonjour
Ben oui mais il n'en reste pas moins que pour créer ce tableau contenant le chemin il faut d'abord le trouver ce chemin

C'est au PO qu'incombe le choix de l'algorithme puisque c'est ce dernier (algorithme choisi) qui aura la lourde tâche de fournir la solution optimale.

[Bousk]

Ou alors, plutôt que de vouloir un truc parfait qui marche dans tous les cas imaginables mais qu'on va utiliser uniquement pour 3 cas simplistes, on adapte les données et on crée un algo précis pour ces 3 cas.

Code :

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

1
2
3
4
5
6
7
|---------------------------|
|    A                      |
|                  D        |
|---e ------g -------i ---- | 
|                           |
| B               C         |
|---------------------------|

Si ça c'est ta map, tu n'as pas besoin d'un truc hyper générique ou quoi que ce soit. Un algo ça s'adapte à la situation.
Tu poses et utilises e, g & i, et quand tu cherches un chemin, tu regardes si tu dois traverser le mur du centre ou pas, et si oui tu cherches lequel de ces 3 points est le plus proche.
Puis tu fais juste des lignes droites.

[yannoo95170]

Je vais rajouter les points de passage dans les murs, cf. e, g et i, aux points A, B, C et D pouvant de base entrer dans un des chemins possible

J'utiliserais alors uniquement les points existants A,B, C et D, ainsi que les points d'entrées dans les murs e, g et i, pour remplir le tableau des distances qui ne fera alors plus dans cet exemple qu'une matrice 7x7 (avec A,B,C,D + e ,g , i en abscisses et en ordonnées, et la distance pour les rejoindre à l'intersection de leur ligne/colonne), plutôt que d'utiliser le damier initial de 80x25 qui multiplie effectivement inutilement et très grandement la taille du tableau, le nombre possible de chemins et les temps de calcul pour rien

J'ai donné un exemple relativement basique afin de n'y présenter que quelques cas très simples, mais la map que j'utiliserais sera bien plus grande et complexe, soit de 80x50 plutôt que des seulement 29x7 dans l'exemple donné
=> je convertirais au préalable la map de 80x50 en un map bien plus petite qui ne contiendra que les points à prendre en compte dans les chemins + les entrées dans les murs
==> cela me permettra alors d'effectuer uniquement les recherches de chemins à partir de seuls points de départs/arrivés possibles, plutôt que de faire les recherches des chemins en prenant en compte toutes les cases du damier original
(dans l'exemple donné, cette conversion permettra de passer d'un tableau de 29x7 cases = 203 poids à un tableau de seulement 7x7 points = 49 poids, soit déjà un tableau 4x plus petit et des temps de calcul pour les recherches de chemins qui devraient en être très très fortement diminués de même)

Il faudra par contre que j'y ajoute une sorte de lancer de rayon pour déterminer si un point peut en rejoindre un autre en ligne droite sans avoir à traverser de murs, afin d'écarter des chemins possibles tous ceux traversersant des murs
=> je pense que c'est cette partie qui sera la plus difficile à mettre en place

[Sve@r]

=> je pense que c'est cette partie qui sera la plus difficile à mettre en place

Pas forcément. Un mur c'est une droite donc qui possède une équation de type y=ax+b (et en plus ici il semble horizontal donc ce sera plutôt de type y=b).
Et un trajet direct entre deux points c'est aussi une droite d'équation similaire y=a'x+b'. Suffit donc de calculer le point d'intersection qui soit

• existe et se trouve sur le segment de droite reliant les deux points
• existe mais se trouve en dehors du segment de droite reliant les deux points
• n'existe pas (cas particulier où a=a' donc ici où a'=1)

Or la formule qui donne le point d'intersection de deux droites n'est pas compliquée à trouver/retrouver => x=(b'-b)/(a-a') et une fois "x" on a directement "y"

[yannoo95170]

Pas forcément. Un mur c'est une droite donc qui possède une équation de type y=ax+b (et en plus ici il semble horizontal donc ce sera plutôt de type y=b).
Et un trajet direct entre deux points c'est aussi une droite d'équation similaire y=a'x+b'. Suffit donc de calculer le point d'intersection qui soit

• existe et se trouve sur le segment de droite reliant les deux points
• existe mais se trouve en dehors du segment de droite reliant les deux points
• n'existe pas (cas particulier où a=a' donc ici où a'=1)

Or la formule qui donne le point d'intersection de deux droites n'est pas compliquée à trouver/retrouver => x=(b'-b)/(a-a') et une fois "x" on a directement "y"

Le problème étant que la map seront bien plus compliquée que l'exemple donné et contiendra environs 10 salles avec une à deux entrées chacunes, soit de 10 à 20 murs et non seulement 5 comme dans l'exemple donné où il n'y a qu'un seul mur (+ les 4 du bord) entre seulement 2 salles

=> il faudra donc que j'arrive à détecter la présence et les équations des segments de murs à partir des suites de "pixels" contigües avec des | ou des - à l'horizontale ou à la verticale dans la map originale de 80x25
(la map originale n'indique pas la taille / orientation des murs, elle dit seulement si telle ou telle case contient un morceau de mur ou autre chose)

[foetus]

Si on regarde la carte de @dalfab, cela peut-être fourbe

Parce que A est peut-être relié directement à B et à C en passant par les trous.
Donc si tu rajoutes les points intermédiaires e, g, i, il faudra soit

• détecter que la distance AB est [presque] égal à Ae + eB -> et donc supprimer le segment AB
• faire 1 répartition de ta carte en fonction des murs [A D + e, g, i] et [B C + e, g, i] pour limiter les recherches des segments possibles (et ainsi éviter l'algo en (n - 1)² pour tester tous les segments et supprimer ceux qui passent par 1 mur)

=> il faudra donc que j'arrive à détecter la présence et les équations des murs à partir des suites de "pixels" contigües avec des | ou des - à l'horizontale ou à la verticale dans la map originale de 80x25

Arbre BSP ? (<- lien wikipedia en français)

[yannoo95170]

Si on regarde la carte de @dalfab, cela peut-être fourbe

Parce que A est peut-être relié directement à B et à C en passant par les trous.
Donc si tu rajoutes les points intermédiaires e, g, i, il faudra soit

• détecter que la distance AB est [presque] égal à Ae + eB -> et donc supprimer le segment AB
• faire 1 répartition de ta carte en fonction des murs [A D + e, g, i] et [B C + e, g, i] pour limiter les recherches des segments possibles (et ainsi éviter l'algo en (n - 1)² pour tester tous les segments et supprimer ceux qui passent par 1 mur)

je pense plutôt opter pour la version "détecter que la distance AB est [presque] égal à Ae + eB -> et donc supprimer le segment AB"
=> celà se fera automatiquement par la sorte de passe de tracé de rayon qui éliminera les chemins passant par un mur
(par exemple les chemins C -> i -> D et C -> g -> D resteront présents dans le tableau mais le chemin C -> D sera éliminé car passant par un mur)
[la passe de lancé de rayon utilisera une droite épaisse de plusieurs "pixels" pour tester la présence d'un ou plusieurs murs entre 2 points, et non pas seulement une droite hyper fine, cf. ce sera plus un algo de "tracé de cylindre" que de "tracé de rayon" ... et ça me permettra en plus de gérer le cas de robots de tailles/encombrements différents dans la foulée ]

+10 pour ton idée de passer via un arbre BSP, ça pourrait me permettre d'y gérer aussi les hauteurs (cf. map en 3D) en plus de la longueur et de la largeur (cf. map en 2D)
=> ça permettrait par exemple d'y ajouter la possibilité de passer sous les tables plutôt que de devoir systématiquement les contourner
(dans ce cas, ce serait alors plutôt la seconde version "faire 1 répartition de ta carte en fonction des murs pour limiter les recherches des segments possibles ..." qu'il faudra que j'y utllise, cf. construire et utiliser un arbre BSP plutôt qu'une map 2D convertie en un tableau 2D de poids)
[l'arbre BSP sera en 2D si je ne veux pas y gérer la possibilité de passer sous les tables/chaises, et sera en 3D s'il faut gérer ces cas]
==> m'enfin bon, je trouve que ça va faire "un peu beaucoup" de devoir passer via un arbre BSP sur un ESP32 et pense donc utiliser la version "lancé de cyclindre" en mode local sur les ESP lorsque le PC sera éteint, et la version BSP lorsque le PC sera allumé et fonctionnera alors en mode clients/serveur
(cf. si le PC est allumé, c'est lui qui enverra les ordres de déplacements aux robots via les calculs de chemins sur l'arbre BSP **MAIS** si il est éteint, se seront les robots qui devront tout faire en se limitant alors à une simple map et devrons alors communiquer entre eux pour mettre à jour leurs maps respectives pour trouver de façon autonome les "meilleurs" chemins pour aller d'un point à un autre tout en évitant les obstacles et les autres robot pouvant se trouver sur leur route)

[yannoo95170]

Après relecture de mon précédent post, je pense que je vais oublier la version BSP 3D en n'indiquant que les pieds de chaises/tables dans la map originale à la place de remplir entièrement les surfaces rectangulaires que représentent ces tables / chaises, afin de me limiter à des BSP 2D plutôt que 3D
(avec un peu de chance, les ESP32 seront peut-être capables de gérer des arbres BSP en 2D en local mais je doute assez fortement qu'ils puissent gérer des arbres BSP en 3D vu la très faible puissance de calcul et la faible empreinte mémoire qu'ils ont)

[yannoo95170]

Je pense avoir trouvé ce que je cherchais avec https://github.com/vmatare/sm-astar

Je n'ai eût qu'à relativement partiellement y modifier le code de la fonction FindPath() afin que l'affichage du chemin ne se fasse plus à chaque pas mais uniquement à la fin
=> seulement 9 millisecondes sur le PC pour moins de 40 Ko pris en mémoire avec sa map d'exemple de 39x20 : ça me va

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
 
yannoo@cyclone ~/Dev/Chemins/SMAstar $ time ./smastar
 012345678901234567890123456789012345678
#########################################
#S-#    .............#..#               # 0
#o-#   ..............#..#               # 1
#o-#  ...............#..#        T      # 2
#o-.# ...............#..#       -o-     # 3
#o-..#...............#..#       -o-     # 4
#o-...##############.#..#       -o-     # 5
#o-..................#..#       -o-     # 6
#o-.....###########..#..#       -o-     # 7
#o-.......# #...........#       -o-     # 8
#o-........#..########..#       -o-     # 9
#o-....###..............#       -o-     # 10
#o-....# ####################   -o-     # 11
#o-....#                         o-     # 12
#o-....#oooooooooooooooooooooooooo-     # 13
#o-....#o#############||||||||||||      # 14
#o-....#o#                              # 15
#o-....#o#                              # 16
#o-....#o#                              # 17
#oooooo#o#                              # 18
#|||||ooo#                              # 19
#########################################
 012345678901234567890123456789012345678
320 Nodes, 90 Leaves.
Path length: 68/600
Mem: 39.824 kB.
 
 
real	0m0,009s
user	0m0,006s
sys	0m0,003s

M'enfin bon, c'est du C++ qu'il va falloir que je porte sur une plateforme Arduino, qui ne supporte que partiellement le C++, donc je vais vous laisser tranquille et aller traîner un peu mes guêtres sur un forum Arduino maintenant