Aller au contenu


Information tutoriel

  • Ajouté le: mai 31 2008 04:02
  • Date Updated: sept. 15 2014 03:21
  • Lectures: 13060
 


* * * * *
0 Notes

Exploration, pathfinding ... dans un labyrinthe

Posté par delfare-RX on mai 31 2008 04:02
Introduction


Dans ce tutoriel, je vais d'abord parler du pathfinding (recherche du plus court chemin entre 2 points).
Cet algorithme nécessite de connaître le labyrinthe où l'on se trouve.
Je vais donc ensuite expliquer comment explorer à 100% un labyrinthe inconnu.

  Pathfinding


Théorie

Je vais ici expliquer le pathfinding.
La méthode que je vais expliquer n'est pas la plus rapide à calculer mais est plus simple et donne le meilleur résultat (au niveau du chemin obtenu).

Imaginons un map de 5*5 cases :

0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

Nous allons maintenant placer un point de départ(A) et d'arrivée(Image IPB


0 0 0 0 0
0 A 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 B 0

Ensuite, nous plaçons des murs :

0 0 0 0 0
0 A | 0 0
0 0 | 0 0
0 0 | 0 0
0 0 | B 0

La technique simple qui consiste à faire une ligne droite est impossible dans cet exemple.
Nous allons remplir le tableau avec le temps qu'il faut pour atteindre la case.
Pour faire ça, nous allons mettre le temps 1 aux cases autour du point de depart :

0 1 0 0 0
1 A | 0 0
0 1 | 0 0
0 0 | 0 0
0 0 | B 0

Ces cases peuvent être parcourues en une unité de temps.
Maintenant, nous allons placer le temps 2 aux cases situées à côté de celles qui ont le temps 1.


2 1 2 0 0
1 A | 0 0
2 1 | 0 0
0 2 | 0 0
0 0 | B 0

Et nous continuons ça jusqu'à arriver à la case de fin:

2 1 2 3 4
1 A | 4 5
2 1 | 5 6
3 2 | 6 7
4 3 | B 0

La case B à une valeur de 7.

Maintenant, pour retrouver le chemin, il n'y a plus qu'à faire le parcours inverse :
B,6,5,4,3,2,1,A


0 1 1 1 0
0 A | 1 0
0 0 | 1 0
0 0 | 1 0
0 0 | B 0

Voila le chemin obtenu.

Programmation

Pour faire simple dans ce tuto, je vais partir du même tableau 5*5 que dans le tutoriel précédent.

Prérequis :


  • connaissance du C
  • connaissance des tableaux
  • connaissance des pointeurs
  • connaissance de l'allocation dynamique de mémoire avec malloc
  • connaissance de la récursivité(je ferais peut-être après une variante en itératif)


D'abord, nous créons le tableau 5*5 :
Code : C
 
int **tab;
int i,j;
tab = (int**)malloc(sizeof(int*)*5);
for(i=0;i<5;i++)
tab[i] = (int*)malloc(sizeof(int)*5);

ensuite, nous allons le remplir. pour simplifier le tuto, je vais le faire manuellement :

Code : C
 
tab[0][0] = 0; tab[1][0] = 0; tab[2][0] = 0; tab[3][0] = 0; tab[4][0] = 0;
tab[0][1] = 0; tab[1][1] = 0; tab[2][1] = -1; tab[3][1] = 0; tab[4][1] = 0;
tab[0][2] = 0; tab[1][2] = 0; tab[2][2] = -1; tab[3][2] = 0; tab[4][2] = 0;
tab[0][3] = 0; tab[1][3] = 0; tab[2][3] = -1; tab[3][3] = 0; tab[4][3] = 0;
tab[0][4] = 0; tab[1][4] = 0; tab[2][4] = -1; tab[3][4] = 0; tab[4][4] = 0;


Les cases -1 représentent des murs.

Nous spécifions ensuite le point de départ et d'arrivée :

Code : C
 
int Ax = 1, Ay = 1, Bx = 3, By = 4;


nous avons maintenant les données nécessaires pour commencer le remplissage du tableau.
nous allons créer une fonction remplissage, j'ai choisis ici de créer une fonction récursive :

Code : C
 
int remplissage(int width, int height, int **tab, int nb_points, int *listX, int *listY,int Bx, int By)
{
return 1;
}

tab est le tableau de la map.
listX et listY sont une liste de points qui ont été remplis au dernier tour(au premier appel, c'est juste le point A, au second appel, ce sont les points autour de A), nb_points est le nombre de points de la liste.
Bx et By sont les coordonnées du point final.

Nous allons maintenant remplir cette fonction :

D'abord, nous allons créer une nouvelle liste de points :
Nous allons allouer 4 fois le nombre de points de la liste actuelle(le maximum qu'on peut obtenir), ne vous inquiétez pas pour la mémoire, on gère ça en dynamique(allocation suivie de libération de la mémoire):

Code : C
 
int *new_listX = (int*)malloc(sizeof(int)*nb_points*4);
int *new_listY = (int*)malloc(sizeof(int)*nb_points*4);
int new_nb_points=0;

à chaque point que nous rajouterons, on incrémentera de 1 la variable new_nb_points.

Ensuite, on parcourt la liste de points :

Code : C
 
int i;
for(i=0;i<nb_points;i++)
{
//gestion des points
}

Nous allons créer une autre fonction que nous utiliserons dedans pour savoir si une case peut être remplie ou pas : cette case doit être dans le tableau et ne pas être déjà utilisée (x>=0, y>=0,x
Code : C
 
int test_case(int width, int height, int **tab, int x, int y)
{
if(x>=0 && y>=0 && x<width && y<height && tab[x][y] == 0)
return 1;
return 0;
}

Revenons maintenant à la boucle sur la liste des points :
On teste les cases autour de chaque case utilisée et on les ajoute à la liste si elles sont acceptées par la fonction test_case. on leur attribue le temps utilisé pour y accéder(le temps de la case precédente + 1)

Code : C
 
int i;
for(i=0;i<nb_points;i++)
{
if(test_case(width,height,tab,listX[i]+1,listY[i]))
{
new_listX[new_nb_points] = listX[i]+1;
new_listY[new_nb_points] = listY[i];
tab[new_listX[new_nb_points]][new_listY[new_nb_points]] = tab[listX[i]][listY[i]] + 1;
new_nb_points++;
}
if(test_case(width,height,tab,listX[i]-1,listY[i]))
{
new_listX[new_nb_points] = listX[i]-1;
new_listY[new_nb_points] = listY[i];
tab[new_listX[new_nb_points]][new_listY[new_nb_points]] = tab[listX[i]][listY[i]] + 1;
new_nb_points++;
}
if(test_case(width,height,tab,listX[i],listY[i]+1))
{
new_listX[new_nb_points] = listX[i];
new_listY[new_nb_points] = listY[i]+1;
tab[new_listX[new_nb_points]][new_listY[new_nb_points]] = tab[listX[i]][listY[i]] + 1;
new_nb_points++;
}
if(test_case(width,height,tab,listX[i],listY[i]-1))
{
new_listX[new_nb_points] = listX[i];
new_listY[new_nb_points] = listY[i]-1;
tab[new_listX[new_nb_points]][new_listY[new_nb_points]] = tab[listX[i]][listY[i]] + 1;
new_nb_points++;
}

Ensuite, nous libérons la première liste(puisqu'elle a déjà été utilisée)

Code : C
 
free(listX);
free(listY);


Et puis, nous finissons : si l'objectif est atteind, on renvoit 1, sinon, on relance la fonction avec la nouvelle liste de points :

Code : C
if(tab[Bx][By]!=0)
return 1;
else return remplissage(width, height, tab, new_nb_points, new_listX, new_listY,Bx, By);


Revenons maintenant dans le main :
on va initialiser la première liste et faire le remplissage puis on affiche le résultat

Code : C
 
int *listX = (int*)malloc(sizeof(int)*1);
int *listY = (int*)malloc(sizeof(int)*1);
listX[0] = Ax;
listY[0] = Ay;
tab[Ax][Ay] = 1;
remplissage(5, 5, tab, 1, listX, listY,Bx,By);

for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
printf("%d ",tab[j][i]);
printf("n");
}

Avec les valeurs choisies, j'obtiens :

Code : C
 
3 2 3 4 5
2 1 -1 5 6
3 2 -1 6 7
4 3 -1 7 8
5 4 -1 8 0

Il ne reste plus qu'à tester le chemin en partant de l'objectif(8,7,6,5,4,3,2,1).
Vous pouvez stocker ça dans un tableau ou une liste chainée(assez pratique car après, on fait chemin = chemin->next; pour avoir la position suivante)

Code complet :

Code : C
 
#include <stdio.h>
#include <stdlib.h>


int test_case(int width, int height, int **tab, int x, int y)
{
if(x>=0 && y>=0 && x<width && y<height && tab[x][y] == 0)
return 1;
return 0;
}

int remplissage(int width, int height, int **tab, int nb_points, int *listX, int *listY,int Bx, int By)
{
int *new_listX = (int*)malloc(sizeof(int)*nb_points*4);
int *new_listY = (int*)malloc(sizeof(int)*nb_points*4);
int new_nb_points=0;
int i;
for(i=0;i<nb_points;i++)
{
if(test_case(width,height,tab,listX[i]+1,listY[i]))
{
new_listX[new_nb_points] = listX[i]+1;
new_listY[new_nb_points] = listY[i];
tab[new_listX[new_nb_points]][new_listY[new_nb_points]] = tab[listX[i]][listY[i]] + 1;
new_nb_points++;
}
if(test_case(width,height,tab,listX[i]-1,listY[i]))
{
new_listX[new_nb_points] = listX[i]-1;
new_listY[new_nb_points] = listY[i];
tab[new_listX[new_nb_points]][new_listY[new_nb_points]] = tab[listX[i]][listY[i]] + 1;
new_nb_points++;
}
if(test_case(width,height,tab,listX[i],listY[i]+1))
{
new_listX[new_nb_points] = listX[i];
new_listY[new_nb_points] = listY[i]+1;
tab[new_listX[new_nb_points]][new_listY[new_nb_points]] = tab[listX[i]][listY[i]] + 1;
new_nb_points++;
}
if(test_case(width,height,tab,listX[i],listY[i]-1))
{
new_listX[new_nb_points] = listX[i];
new_listY[new_nb_points] = listY[i]-1;
tab[new_listX[new_nb_points]][new_listY[new_nb_points]] = tab[listX[i]][listY[i]] + 1;
new_nb_points++;
}
}

free(listX);
free(listY);
if(tab[Bx][By]!=0)
return 1;
else return remplissage(width, height, tab, new_nb_points, new_listX, new_listY,Bx, By);
}

int main(int argc, char *argv[])
{
int **tab;
int Ax = 1, Ay = 1, Bx = 3, By = 4;
int i,j;
tab = (int**)malloc(sizeof(int*)*5);
for(i=0;i<5;i++)
tab[i] = (int*)malloc(sizeof(int)*5);
tab[0][0] = 0; tab[1][0] = 0; tab[2][0] = 0; tab[3][0] = 0; tab[4][0] = 0;
tab[0][1] = 0; tab[1][1] = 0; tab[2][1] = -1; tab[3][1] = 0; tab[4][1] = 0;
tab[0][2] = 0; tab[1][2] = 0; tab[2][2] = -1; tab[3][2] = 0; tab[4][2] = 0;
tab[0][3] = 0; tab[1][3] = 0; tab[2][3] = -1; tab[3][3] = 0; tab[4][3] = 0;
tab[0][4] = 0; tab[1][4] = 0; tab[2][4] = -1; tab[3][4] = 0; tab[4][4] = 0;

int *listX = (int*)malloc(sizeof(int)*1);
int *listY = (int*)malloc(sizeof(int)*1);
listX[0] = Ax;
listY[0] = Ay;
tab[Ax][Ay] = 1;
remplissage(5, 5, tab, 1, listX, listY,Bx,By);

for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
printf("%d ",tab[j][i]);
printf("n");
}
system("PAUSE");
return 0;
}

Ce chapitre touche à sa fin Image IPB .

  le voyageur du commerce" par recuit simulé


Théorie

Dans ce tuto, je vais expliquer comment résoudre le problème du "voyageur du commerce" en utilisant l'algorithme recuit simulé.

Voyageur du commerce

Le problème du "voyageur du commerce" est un voyageur qui doit passer par plusieurs points en prenant le moins de temps possible. On pourrait penser faire ça en récursif mais pour 10 points, on atteind 10*9*8*7*6*5*4*3*2 = 3628800 chemins. Cela deviens vite impossible à gérer.

Recuit simulé

Le recuit simulé est un algorithme qui permet de s'approcher du chemin optimal en partant d'un chemin aléatoire qu'on améliore.

On choisit une valeur T de départ qui diminuera à chaque boucle et qui permet d'avoir une tolérance pour faire des modifications qui paraîssent mauvaises(allongent le parcours) car elles peuvent être nécessaires pour pouvoir ensuite diminuer plus fort.

Il y a différentes possibilités de changement du parcours :
pour une suite ABCD, on peut tester ACBD
pour une suite ABCDE, on peut tester ADCBE
pour 2 suites ABCD et EFGH, on peut tester AFGD et EBCH

Il suffit ensuite de faire ces test : si la modification rétrécit le parcours, on la fait. Sinon, on prend un nombre entre 0 et 1, si il est inférieur ou égal à exp(-taille_supplémentaire/T), alors on le fait quand même.
Régulièrement, on diminue T jusqu'à une certaine valeur et ça permet d'obtenir une solution assez proche de la solution optimale.


Sources :
comuweb
wikipedia
inria


Exploration d'une map inconnue

Théorie

Dans ce tuto, je vais expliquer comment explorer une map inconnue.

Prérequis pour comprendre ce tuto :
-avoir compris le tuto sur le pathfinding

L'exploration d'une map inconnue n'est pas très dure : il suffit d'effectuer le même algo de remplissage que dans le pathfinding et de s'arrêter dès qu'on arrive à une case inconnue.

On a donc :

?????
?????
??A??
?????
?????

Ensuite, on obtient :

?????
??A??
?? ??
?????
?????

?? A|
?? ??
?? ??
?????
?????

Ici, les cases inconnues sont à chaque fois à côté donc c'est trouvé directement mais on peut avoir ceci :

|
A||
|?

|||||

Ici, on génère le tableau de valeurs

0000|
00A||
000|?
00000
|||||

Ensuite, ça devient :

3212|
21A||
321|?
43234
|||||

On trouve un ? à côté du 4, on a donc trouvé une case à chercher et on connaît son chemin(?-4-3-2-1-A).

Voilà, c'est fini.