Recherche de chemin avec peu de mémoire

**yannoo95170** · 20/10/2021, 15h06

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** · 20/10/2021, 15h25

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** · 20/10/2021, 15h33

Envoyé par 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.

Bonjour.

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

**Bousk** · 20/10/2021, 15h38

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** · 20/10/2021, 15h43

Envoyé par gerald3d

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** · 20/10/2021, 15h44

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** · 20/10/2021, 15h59

Merci, Bousk

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

**yannoo95170** · 20/10/2021, 16h06

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** · 20/10/2021, 16h12

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** · 20/10/2021, 16h25

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)

Recherche de chemin avec peu de mémoire

C

Vue hybride

Discussions similaires

Partager

Partager