Discussion :

[yannoo95170]

Je voudrais mettre en place un algorithme de recherche de chemin sur un Arduino, donc avec une faible empreinte mémoire et très peu de puissance CPU

Je viens juste de commencer ce projet et voudrait utiliser un simple fichier texte contenant le plan des salles, murs et les objets que je voudrais atteindre séquentiellement
(pour l'instant, je préfère développer l'algorithme sur mon PC afin de pouvoir le tester/débugger un max avant de porter ça sur une plateforme Arduino)

Le plan est pour l'instant tout simplement stocké dans une fichier texte tel que celui-ci
(où les + - et | indiquent les murs et les lettres les positions séquentielles par lesquelles passer]

Code :

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

1
2
3
4
5
6
7
8
9
 
 
|---------------------------|
|    A                      |
|                  D        |
|---  ------  -------  ---- | 
|                           |
| B               C         |
|---------------------------|

Et je voudrais utiliser ce style de programme en C afin de trouver le meilleur chemin afin de passer séquentiellement par les chemins A, B, C puis D

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
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h> 
 
 
#define WIDTH  80
#define HEIGHT 25
 
 
char Map[HEIGHT][WIDTH];
 
 
int LoadMap( char *mapname )
{
	FILE *file;
	int nLines = 0;
	char buf[80];
 
	file = fopen(mapname, "r" );
 
	if( file )
	{
		nLines = 0;
 
		memset(Map, 0, 80*25);
 
		while ( fgets( buf , 80, file) )
		{
			nLines++;
 
			strcpy(Map[nLines], buf); 
			printf("%s", Map[nLines] );
		}
 
		// printf("%d lines read \n", nLines);
		fclose(file);
	}
	else
	{
		printf("Cannot open the file %s :( \n", mapname);
		return -1;
	}
 
	return nLines;
}
 
 
int FindPosition( char object, int *xpos, int *ypos)
{
	int x, y;
	int xa, ya, xb, yb;
 
	// printf("Search the position of the object %c \n", object);
 
	// Search the src coordinates
	for ( y = 0 ; y < HEIGHT ; y++)
	{ 
		for( x = 0 ; x < WIDTH ; x++)
		{
			if( Map[y][x] == 0 ) break;
 
			if( Map[y][x] == object )
			{ 
				*xpos = x;
				*ypos = y;
 
				// printf("object %c finded at (%d,%d) \n", object, x, y); 
			}
		}
	}
}
 
int FindPath( char src, char dst)
{
	int xa, ya, xb, yb;
 
	// printf("Search the best path between %c and %c \n", src, dst);
	(void) FindPosition(src, &xa, &ya);
	(void) FindPosition(dst, &xb, &yb);
 
 
	printf("\tTODO : search the best path between %c(%d,%d) and %c(%d,%d) \n", src, xa, ya, dst, xb, yb);
 
 
	return 0;
} 
 
 
int FindPaths( char *paths )
{
	printf("Find the best path %s \n\n", paths);
 
	for( int i = 0 ; i < strlen(paths) - 1 ; i++ )
	{
		FindPath( paths[i] , paths[i+1] );
	}
}
 
 
int main( int argc, char **argv )
{
	printf("Pathfinding v0.0 by Cyclone \n\n");
 
	(void) LoadMap( argc > 1 ? argv[1] : "plan.map");
 
	// FindPath('A', 'B');
	FindPaths("ABCD");
 
	return 0;
}

Ce qui donne pour l'instant ceci, la recherche du plus court chemin n'y étant pas encore implémentée
(et c'est justement ce que je veux y faire ...)

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
 
Pathfinding v0.0 by Cyclone 
 
 
 
|---------------------------|
|    A                      |
|                  D        |
|---  ------  -------  ---- | 
|                           |
| B               C         |
|---------------------------|
 
 
 
Find the best path ABCD 
 
	TODO : search the best path between A(5,4) and B(2,8) 
	TODO : search the best path between B(2,8) and C(18,8) 
	TODO : search the best path between C(18,8) and D(19,5)

Le problème étant bien entendu d'implémenter correctement la fonction int FindPath( char src, char dst), cf. les TODO, afin qu'elle trouve le meilleur chemin entre le point src et le point dst en évitant bien sûr de jouer le passe-muraille, sinon ce serait trop simple

Mon idée première serait de calculer la droite entre les points source et destination, puis d'essayer de "coller" un maximum à cette droite en adaptant le chemin parcouru à chacun des pas en tenant compte des obstacles présents entre la position courante et le prochain déplacement avant/arrière/gauche/droite à faire afin de contourner les différents obstacles trouvés tout en cherchant à m'éloigner au minimum de cette droite idéale
(les obstacles sont pour l'instant simplement les murs représentés par des - et des | mais je pense y rajouter d'autres obstacles comme des chaises ou ds tables qui utiliseront d'autres symboles que les lettre alphabétiques que je réserve au différents points par lesquels je voudrais passer)

[skeud]

Le plus simple c'est d'affécter un poids à chacune des case en fonction de la distance de la case de départ. Dès que tu touches la case d'arrivée, pour déssiner ton chemin tu garde la case autour de toi qui possède la plus faible valeur:

situation de départ:

Code :

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

1
2
3
4
5
6
 
|-----
|A    |
|     |
|    B|
|-----|

on affecte les poids:

Code :

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

1
2
3
4
5
6
 
|-----
|A1234|
|12345|
|2345B|
|-----|

Et donc pour aller de A à B il existe deux chemins de même distance. Il ne te reste plus qu'à faire la même chose pour des maps plus complexes.

[gerald3d]

Le plus simple c'est d'affécter un poids à chacune des case en fonction de la distance de la case de départ. Dès que tu touches la case d'arrivée, pour déssiner ton chemin tu garde la case autour de toi qui possède la plus faible valeur:

situation de départ:

Code :

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

1
2
3
4
5
6
 
|-----
|A    |
|     |
|    B|
|-----|

on affecte les poids:

Code :

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

1
2
3
4
5
6
 
|-----
|A1234|
|12345|
|2345B|
|-----|

Et donc pour aller de A à B il existe deux chemins de même distance. Il ne te reste plus qu'à faire la même chose pour des maps plus complexes.

Bonjour.

Je n'ai pas dû bien comprendre ton explication. Pour moi il y a 9 chemins équivalents dans ton exemple.

[Bousk]

Implémente un simple A*, puis on verra si c'est pas assez efficace mais j'en doute.
https://en.wikipedia.org/wiki/A*_search_algorithm

[skeud]

Bonjour.

Je n'ai pas dû bien comprendre ton explication. Pour moi il y a 9 chemins équivalents dans ton exemple.

My bad, je pars toujours du principe de prendre le chemin avec le moins de "virage" possible. Mais oui il y en a plus sur cet exemple, comme il n'y a pas de mur ^^.

[yannoo95170]

J'ai pensé à ce systême de poids mais le problème est qu'il faudrait totalement remplir le tableau de poids à chaque recalcul de la trajectoire entre un point et un autre, cf. entre A et B puis B et C puis entre C et D, ce qui est très consommateur de ressources CPU en plus de demander pas mal de mémoire pour mémoriser ce tableau supplémentaire

D'où mon idée de ne recalculer les poids qu'à un minimum de cases en ne les recalculant que sur une "bande brisée" suivant le plus possible la ligne droite tout en tenant compte des obstacles
(ça ne résout pas grand chose au niveau de l'empreinte mémoire mais ça limiterait très considérablement les calculs à effectuer à chaque chemin cherché car uniquement les positions ayant une chance d'être visitées le seraient alors qu'il faut recalculer **ENTIEREMENT** le tableau des poids à chaque chemin A->B recherché, ce qui mutilplie en gros le nombre de calculs nécessaires au carré par rapport au nombre de calculs qui seraient seulement nécessaires si on se serait limité à seulement ceux des cases visitées par une ligne/bande brisée)
[c'est pour tourner su r un Arduino qui est hyper limité en puissance CPU, donc si je peux trouver un algo qui ne demande qu'une puissance de calcul minimum, ce serait plutôt "plus mieux" )

[yannoo95170]

Merci, Bousk

L'utilisation de l'algo A* me semble effectivement assez prometteuse

[yannoo95170]

Skeud,

Le problème est justement de gérer la présence de murs/obstacles, cf. mon "sinon ce serait trop simple"
(un simple calcul incrémental d'une ligne droite permettrait de calculer la position de chaque case séquentiellement visitée et serait amplement suffisant s'il n'y avait pas d'obstacles .. mais ce n'est pas du tout le cas que je veux gérer qui est exactement le contraire )

[skeud]

D'acc les deux solutions sont possibles du coup, une gourmande en mémoire et cpu (celle que je propose) mais facile à implémenter, et l'A* qui est hyper optimisée, mais plus difficile à prendre en main . A toi de voir vers quoi te diriger.

[yannoo95170]

Je viens de trouver ce code implémentant l'algorithme A* sur https://www.gamedev.net/forums/topic...hfinding-in-c/

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
 
//a star path finding take 2
 
//create a list struct for the path
struct list_s
{
	int x;
	int y;
	int f;
} path[10000];
 
struct NODE
{
	int walkable;
 
	int onopen;
	int onclosed;
 
	int g;
	int h;
	int f;
 
	int parentx;
	int parenty;
} node[MAPW][MAPH];
 
void initnodes()
{
	int x,y;
 
	for(x=0;x<MAPW;x++)
	{
		for(y=0;y<MAPH;y++)
		{
			node[x][y].walkable = getpixel(map,x,y);
			node[x][y].onopen = FALSE;
			node[x][y].onclosed = FALSE;
			node[x][y].g = 0;
			node[x][y].h = 0;
			node[x][y].f = 0;
			node[x][y].parentx = NULL;
			node[x][y].parenty = NULL;
		}
	}
}
 
int *findpath(int startx, int starty, int endx, int endy)
{
	int x=0,y=0; // for running through the nodes
	int dx,dy; // for the 8 squares adjacent to each node
	int currentx=startx, currenty=starty;
	int lowestf=10000; // start with the lowest being the highest
 
	// add starting node to open list
	node[startx][starty].onopen = TRUE;
 
	while (!node[currentx][currenty].onclosed) //stop when the current node is on the closed list
	{
		//look for lowest F cost node on open list - this becomes the current node
		for(x=0;x<MAPW;x++)
		{
			for(y=0;y<MAPY;y++)
			{
				node[x][y].f = node[x][y].g + node[x][y].h;
				if(node[x][y].onopen)
				if(node[x][y].f<lowestf) { currentx = x; currenty = y; lowestf = node[x][y].f;}
			}
		}
		// we found it, so now put that node on the closed list
		node[currentx][currenty].onopen = FALSE;
		node[currentx][currenty].onclosed = TRUE;
 
		// for each of the 8 adjacent node
		for(dx=-1;dx<=1;dx++)
		{
			for(dy=-1;dy<=1;dy++)
			{
				// if its walkable and not on the closed list
				if(node[currentx+dx][currenty+dy].walkable || !node[currentx+dx][currenty+dy].onclosed)
				{
					//if its not on open list
					if(!node[currentx+dx][currenty+dy].onopen) 
					{
						//add it to open list 
						node[currentx+dx][currenty+dy].onopen = TRUE; node[currentx+dx][currenty+dy].onclosed = FALSE;
						//make the current node its parent
						node[currentx+dx][currenty+dy].parentx = currentx;
						node[currentx+dx][currenty+dy].parenty = currenty;
						//work out G
						if(dx!=0 && dy!=0) node[currentx+dx][currenty+dy].g = 14; // diagonals cost 14
						else node[currentx+dx][currenty+dy].g = 10; // straights cost 10
						//work out H
						//MANHATTAN METHOD
						node[currentx+dx][currenty+dy].h = abs(endx-currentx+dy + endy-currenty+dy) * 10;
					}
					//otherwise it is on the open list
					else
					{
						if(dx==0 || dy==0) // if its not a diagonal
							if(node[currentx+dx][currenty+dy].g!=10) //and it was previously
							{ 
								node[currentx+dx][currenty+dy].g = 10; // straight score 10
								//change its parent because its a shorter distance
								node[currentx+dx][currenty+dy].parentx = currentx;
								node[currentx+dx][currenty+dy].parenty = currenty;
								//recalc H
								node[currentx+dx][currenty+dy].h = abs(endx-currentx+dy + endy-currenty+dy) * 10;
								//recalc F
								node[currentx+dx][currenty+dy].f = node[currentx+dx][currenty+dy].g + node[currentx+dx][currenty+dy].h;
							}
 
					}//end else
				}// end if walkable and not on closed list
			}
		}//end for each 8 adjacent node
	}//end while
 
	//put the parent nodes into a list ordered from highest to lowest f value
	//first count how many there are
	int count=0;
	for(x=0;x<MAPW;x++)
	{
		for(y=0;y<MAPY;y++)
		{
			if(node[x][y].onclosed) { path[count].x = x; path[count].y = y; path[count].f = node[x][y].f; count++; }
		}
	}
	//sort them
	qsort (path, count, sizeof(struct list_s), compare);
 
	return &path; //we're done, return a pointer to the final path;
}//end function
 
 
//sorting stuff
int compare (const struct list_s * a, const struct list_s * b)
{
  return ( a->f - b->f );
}

=> je vais essayer d'incorporer / adapter ça à mon code, l'accès au plan semblant simplement s'y faire via le node[x][y].walkable = getpixel(map,x,y)
(par contre, ça n'a pas du tout l'air d'être économe en mémoire, cf. le node[MAPW][MAPH] qui semble devoir prendre de l'ordre d'au moins 8x plus de mémoire que le plan car 8 champs y sont utilisés alors que seul l'équivalent du champ walkable est utilisé pour le plan => je rajoute ça dans mon code et vous tiendrais au courant de ce que ça donne au niveau consommation mémoire/CPU)

[yannoo95170]

Je vais néanmoins commencer par la proposition bien plus simple de Skeud, mais en y limitant par exemple les calculs à la zone rectangulaire englobant les 2 points à relier
(ça ne gèrera pas tous les cas, style quand il faudra passer en dehors de cette zone, mais ça devrait aller pour les cas les plus courants)

Par contre, pas trop compris comment on pouvait calculer le poids de chaque case en tenant compte des obstacles qui pourraient se trouver sur le chemin

[yannoo95170]

J'ai une autre idée : précalculer les différents mouvements possibles que l'on peut effectuer pour chaque case en y compactant tous les mouvement possibles sur 1 seul octet
(cf. un bit pour "possible à gauche', un autre pour "possible à droite", 1 autre pour "possible en haut", 1 autre pour "possible en diagonale gauche-haut", etc ... soit 8 bits pour savoir si tel ou tel déplacement à partir de la case courante est possible)
=> un seul tableau d'octets à rajouter = seulement x2 au niveau empreinte mémoire vs au moins 8x avec la méthode A* )

Ensuite, essayer de suivre le plus possible un ligne droite vers le point final tout en réadaptant le point de départ à chaque déplacement + en tenant compte des déplacement possibles qui auront été précalculés précédemment
(ça aurait de plus l'avantage de pouvoir gérer une scène dynamique en y rajoutant la gestion de la seule mise à jour des cases précalculées touchant celles qui ont été modifiées d'un instant t à l'instant t+1 suivant => ça me plait ça )

[yannoo95170]

Par exemple, pour aller du point D au point C

Code :

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

1
2
3
4
5
6
7
8
 
|---------------------------|
|    A                      |
|                  D1       |
|---  ------  -------2  ----| 
|                   3       |
| B               C4        |
|---------------------------|

0) Au point D, le plus court chemin est quasiment la ligne droite en descendant mais il y le mur qui fait obstacle
=> on peut aller à droite, à gauche ou en haut (en diagonale ou pas ) mais pas en bas (diagonale ou pas)
==> l'ouverture la ligne suivante la plus proche est à droite qui est un déplacement permis, donc à droite pour arriver en 1)

1) on ne peut toujours pas descendre directement en bas car le mur est là pour empêcher de le faire
=> on peut néanmoins arriver à la brêche dans le mur (une porte ouverte par exemple) en y allant en diagonale bas-droite pour arriver en 2)

2) la direction optimale permise pour aller de cette porte où on est maintenant arrivé et le point C est en diagonale bas-gauche pour arriver en 3)

3) encore une déplacement optimal permis diagonale bas-gauche pour arriver en 4

5) le déplacement optimal permis est à gauche et on est enfin arriver au point C


L'idée semble fonctionnelle, ne me manque plus qu'à essayer d'implémenter ça maintenant
(seulement 5 itérations et un tableau d'octets en +, c'est carrément "bien plus mieux" que WIDTH*HEIGHT itérations via l'algo simple ou taille du tableau x8 via l'algo A* ...)

[skeud]

ça pourrait marcher sauf que toi tu le vois avec tes yeux en regardant tout le tableau. Contrairement à l'ordinateur qui ne le verra pas en entier. Donc pour ton exemple ça fonctionne mais pour un exemple où il faudrait monter pour redescendre, là ça ne marchera plus.

Concernant la manière de remplir le tableau avec mon algo, c'est fait de la manière suivante:

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
 
int tab[][]; ton tableau qui contient ton jeux, pour l'instant avec des 0 partouts et des -1 là où tu peux pas passer
tab[a.y][a.x] = 1; // On met la valeur 1 sur A pour démarrer
tab[b.y][b.x] = -2; // on met la valeur -2 sur le point d'arriver pour le reconnaitre
bool stopBoucle = false;
while (!stopBoucle) // tant qu'on a pas trouvé un chemin
for (int y = 0; y < sizeY; y++)
{
  for (int x = 0; x < sizeX; x++)
  {
     if (tab[y][x] == 0) // c'est une case non rempli
     {
        // La je te laisse faire le code pour mettre la valeur la plus petite + 1 des cases autour (qui sont différente de 0)
     }
     if (tab[y][x] == -2)
    {
       // Je te laisse faire le code ici aussi pour savoir si une des cases autour possède une valeur > 0 et donc qu'un chemin a été trouvé
       if () // si un chemin existe
         stopBoucle = true;
    }
  }
}

Evidemment ce code n'est pas celui que tu dois implémenter car c'est un exemple vite fais pour te donner une piste, à toi de voir comment tu souhaite le faire (on pourrait parcourir le tableau X fois pour remplir d'abord tout les 1 puis tout les 2 puis tout les 3 etc .....). Ou le couplé à l'A* pour justement avoir un remplissage beaucoup plus rapide

[yannoo95170]

Je vois la ruse avec le while( !stopBoucle) qui permet de terminer quand on est arrivé à la fin du parcours, cf. tab[y][x] == -2
=> très bien

Par contre, c'est la double boucle imbriquée à l'intérieur qui me gène bien plus car SizeX * sizeY itérations à chaque passe
=> si le point de début et/ou le point de fin sont dans les dernières lignes par exemples, on est obligé de se coltiner toutes les lignes/colonnes avant : pas glop du tout ce style de truc sur un Arduino qui est hyper limité en puissance de calcul
(ou pareil s'ils sont dans les premières lignes => on doit se coltiner quasiment toutes celles qui sont après "pour rien")
[d'où une de mes idées initales de ne faire les mises à jour que dans la seule portion encadrée par (xD,yD) et (xC,yC) plutôt qu'encadrée entre (0,0) et (sizeX -1, sizeY -1) pour chercher le chemin entre D et C par exemple ... mais ça crée des problèmes car le chemin sort très souvent de cet encadrement, comme c'est d'ailleurs le cas dans mon exemple car il y a un mur comme obstacle entre les deux ]

[Bousk]

Est-ce que tu as déjà une implémentation fonctionnelle ?
Est-ce que tu bases tes commentaires sur du profiling qui te montre clairement où se situe le problème ?
Est-ce que ton profiling est bien fait et probant ?
Avant de tirer des plans sur la lune pour faire un truc mieux, fais un truc qui marche.

[yannoo95170]

Est-ce que tu as déjà une implémentation fonctionnelle ?
Est-ce que tu bases tes commentaires sur du profiling qui te montre clairement où se situe le problème ?
Est-ce que ton profiling est bien fait et probant ?
Avant de tirer des plans sur la lune pour faire un truc mieux, fais un truc qui marche.

Non, non et non

=> je vais déjà faire une implémentation basique sur mon PC et profiler/tester un peu ça avant de tirer des plans sur le Lune
(c'est vrai qu'avec un map de 80x25 ou 80x50, ça ne fait que 2000 ou 4000 itérations par passe après tout => je verrais après comment ça se comporte avec une taille de map bien plus grande car c'est le côté nombre d'itérations = carré de la taille de la map qui me fait peur => j'y préfererais largement qqchose avec un nombre d'itérations qui suive en linéaire en fonction de la taille de la map qu'en cubique)

C'est pour tourner sur un ESP32 à 10 Mhz avec 4 Mo de RAM et je pense travailler avec des maps de disons 1000x1000 = 1 million de cases = 1 Mo (1/4 de la RAM de l'ESP32) , soit 1 millions d'itérations à chaque passe avec l'algo classique
=> mon petit doigt me dit que l'ESP32 sera très loin de tenir la cadence si le chemin à trouver fait ne serait-ce qu'une dizaine de cases par exemple
(m'enfin bon, peut-être pas, on verra bien ... mais néanmoins quasiment sûr à 99% qu'il ne suivra pas la cadence vu qu'il n'y aura seulement qu'un cycle par itération avec disons 10 passes en moyenne si le chemin est à recalculer toutes les secondes)

C'est pour la commande dynamique d'un mini-robot et je veux pouvoir le faire changer de cible /direction à n'importe quel moment sans avoir à attendre des plombes qu'il n'ai fini le calcul d'il y a déjà plusieurs secondes ...

J'arrive déjà à commander les différents déplacements / actions du robot grâce à une diode émétrice gérée par l'ESP32 que j'ai mis dans un mini sac à dos placé dans le dos du robot, ESP32 commandé par des requêtes HTML que je peux lancer depuis mon PC
=> donc l'algo pourra au pire tourner sur un PC **MAIS** j'y préfererais largement que le robot puisse évoluer de façon autonome en ne recevant que des commandes lui indiquant de viser une autre emplacement, pas **TOUS** les déplacements unitaires à faire un par un
(4 robots à gérer en // => à mon avis, même le PC tirera la tronche à gérer tout ça en même temps avec un algo classique ....)

C'est pour escorter un aspirateur-robot à l'aide de 4 robots donc il faut qu'ils puissent réagir en temps-réel
(+ de façon relativement autonome si possible)

Bon OK, c'est effectivement un peu comme tirer des plans sur la Lune mais c'est justement ça qui me plaît bien
(j'ai déjà plusieurs fois tirer ce style de plans sur la Lune => par exemple, je commande déjà leurs déplacement/action depuis une simple page HTML et ils savent déjà se parler avec différentes styles comme homme/femme ou un débit de parole variable et commencent même à se faire la discute entre eux )
[bon OK, c'est carrément de la discussion "à la petit nègre / n'importe nawak" effectuées à partir de constructions sujet/verbe/complément/"fin de phrase/politesses" mais il peuvent aussi déjà me lire le contenu d'un paragraphe que je peux extraire d'un page http:// depuis mon PC pour ne leur en envoyer que le texte expurgé du code <HTML> qu'il y a, histoire de paraître intelligents de temps en temps en nous sortant la météo, l'horaire du prochain train ou la dernière news qui vient d'arriver sur https://news.google.com/topstories par exemples ]


https://www.amazon.fr/gp/product/B07...e?ie=UTF8&th=1

https://www.amazon.fr/gp/product/B08...e?ie=UTF8&th=1

[yannoo95170]

De l'autre côté, je peux tout aussi bien n'y gérer que des salles de disons 80x50 avec des portals représentants les portes pour passer d'une salle à l'autre
=> avec une dizaine de salles, ça ne ferait plus que 80x50 = 4000 cases par salle et disons une bonne dizaine de portals, soit un peu plus de 40 000 itérations (+ celles nécessaires pour gérer les portals) avec un cheminement moyen de 10 cases à l'avance, ça devrait là être assez facilement jouable

=> je pense avoir trouvé la solution après relecture de ce dernier post : l'ESP32 n'aura qu'à gérer les déplacements que dans une seule salle de 80x50 à la fois et ce sera le PC qui s'occupera de gérer les portals et lui envoyer le plan de la salle où il devra lui-même gérer les déplacement pour aller d'un point à un autre
==> pas trop de temps CPU ni de mémoire consommée pour rien sur l'ESP32 car se sera le PC qui gerera les portals et lui enverra les mises à jours de map et de points source-> destination nécessaires quand il faudra passer d'une salle à à une autre

Je pourrais alors ensuite voir si ça marche bien pour que la partie gestion des portals soit gérée directement sur les ESP32 car ça ne ferait alors que 10 maps de 40000 octets à stocker sur les ESP32 pour le stockage des 10 maps de salles représentant la maison/appartement/étage, ce qui est totalement envisageable et me permettrait même d'y gagner pas mal par rapport à mon envie initiale d'y gérer un énorme map de 1000x1000 par exemple
(reste à voir pour la granularité des maps car avec une taille de 80x50, ça fait déjà une granularité de 10x10 cm pour une salle de 8 mêtres x 5 mêtres = 40 mêtres carrées, ce qui me semble raisonnable bien que je préfèrerais plutôt m'approcher d'une précision/granularité de l'ordre du cm que de 10 cm => m'enfin bon, ne soyons pas plus royaliste que le roi non plus ]

Dans mon exemple initial, il n'y a que 2 salles, l'une contenant A et D et l'autre B et C + il y a 3 portals pour passer entre les deux salles
=> 80x50= 4000 itérations par salle et par passe + quelques itérations en plus s'il faut passer d'une salle à l'autre : ça c'est parfaitement totalement gérable même sur un Arduino pas puissant du tout
==> Lune me voilà ... même si ce ne sera que dans quelques semaines ou mois

[yannoo95170]

Je vais regarder du côté de vieux jeux style PAC-MAN voir comment ils gèrent le suivi et les coutournements d'obstacles, je pense que j'y trouverais de bonnes idées éprouvées pour tourner sur des machines pas trop puissantes et avec relativement peu de mémoire
(c'est typiquement ce que je voudrais faire, cf. gérer les déplacement de monstres qui te poursuivent, la différence étant ici que le héros du jeu de PAC MAN sera le robot aspirateur et que les monstres qui le poursuivront seront les robots jouets)

=> je pense que je vais m'inspirer de ce .pdf afin de me créer une base réaliste et ludique sur laquelle je pourrais ensuite m'appuyer pour y adapter/tester différents style d'algorithmes de suivi / contournement différents et de les comparer en eux, vu que c'est de la programmation objet
(ils y prévoient un planning sur 1 bon mois => ça me convient, bien que j'y préfèrerais que ce soit néanmoins bien plus court )
[je ne veux en tirer que la partie suivi / contournements d'obstacles, toutes les parties graphiques / interface m'y seront je pense inutiles]

http://poukie8.free.fr/ESIL/3%E8me%2...an_rapport.pdf

[yannoo95170]

1ère lecture rapide en diagonale du pdf : à première vue, ce sera un mix des fonctions PacManVisibleDepuis() et EloigneToiDePacMan() qu'il faudra que j'utilise afin que les robots jouets (= fantomes) suivent le robot aspirateur (=Pac Man) **MAIS** à une distance toujours raisonnable afin de ne jamais lui rentrer dedans, cf. ni trop loin ni trop prêt
(il faudra en plus que j'y rajoute la gestion des diagonales, seuls les trajets en ligne ou en colonne sont gérées dans ce pdf)

Pour la gestion des points, des vies et autres menus, pas trop besoin d'eux pour mon projet
=> ça me fait déjà direct quelques jours/semaine(s ?) de gagnés sur leur planning vu que je ne veux en utiliser que la partie suivi/contournement d'obstacles et absolument pas la portion interfacage/affichage
(je me limiterais à un affichage en mode texte => pas besoin d'utiliser des images, de simples lettre ASCII les remplaceront pour gérer l'affichage + les menus ce sera au niveau des arguments donnés au programme que ça se gèrera)
[cf. il n'y a que la case "Partie" du diagramme d’états présent à la page 11 que je pense réellement utiliser dans mon programme, soit une infime partie comparée au diagramme entier dont la majeure partie ne devrait pas m'être utile]