Bonjour, je suis actuellement en train de coder un petit jeu en c sur codeblock avec la librairie SDL2. Je cherche à élaborer un petit code pour effectuer un pathfinding qui analysera chaque pixel autour d'une image (prenons des cases : le programme doit analyser les 8 cases adjacentes et identifier celles où l'image peut se déplacer, sachant que cette dernière ne doit pas empiéter sur un obstacle - un pixel noir par exemple : les collisions sont basées sur la couleur des pixels - et ne peut revenir sur la case où elle se trouvait précédemment) qui se déplacera d'un point A à un point B en prenant le chemin le court possible bien sûr.
Mon idée est d'analyser les 8 pixels autour du pixel de l'image (càd les pixels autour de (image.x ,image.y) : (image.x+1 ,image.y),(image.x-1 ,image.y),(image.x ,image.y+1),(image.x ,image.y-1),(image.x-1 ,image.y-1),(image.x+1 ,image.y+1),(image.x-1 ,image.y+1) et (image.x+1 ,image.y-1) tout en vérifiant la couleur de chacun de ces pixels, si un ou plusieurs de ces pixels génère(nt) une collision, ce(s) dernier(s) doit/doivent être ignoré(s) dans la recherche du chemin le plus court.
Je ne veux pas qu'on me donne la solution mais juste une piste pour m'aider à progresser dans le code de ce jeu.
Si vous avez des idées je suis preneur.
Merci d'avance
PS : je maîtrise mal le c++ et le java mais vous pouvez les afficher si ça peut m'aider, idem pour les pseudo-codes.
Merci d'avoir répondu à mon post. J'ai recherché de mon côté concernant ce fameux algo pot de peinture mais en vain. D'après ce que j'en ai tiré avec ma propre compréhension cet algo consiste à analyser absolument toutes les cases (les pixels dans mon cas) puis en fonction des obstacles et de la distance entre le point de départ et celui d'arrivée cet algo permet au personnage de parcourir le plus vite possible cette distance entre les deux points.
Seulement, si ça consiste à étudier toutes les cases du tableau d'image ça risque de faire beaucoup de calculs et je ne sais pas si SDL2 peut supporter autant. Mon idée qui consiste à analyser les 8 cases adjacentes à celle de mon personnage n'est valable que sur la proximité à moins que je parviennes à mettre en place un second programme qui calculera au début la distance séparant le personnage et son objectif, cette valeur devra ensuite être testée à chaque fois que le personnage devra se déplacer et ensuite ce programme devra relancer cette même boucle.
Après ton idée est sans doute meilleure que la mienne, après on peut en faire une nouvelle avec ces deux idées : penses-tu qu'analyser chaque cases avec ton algo ainsi que la couleur de chacune de ces cases - puisque je gère les collisions entre récupérant la couleur des pixels - pour dire au programme si oui ou non le personnage peut se rendre sur ce pixel peut être une solution ?
Autre petite question, je souhaiterais faire en sorte d'annuler les déplacements en biais en retenant la touche de déplacement précédemment utilisée : càd que le personnage ne pourra se déplacer que dans 4 directions (haut, bas, droite, gauche).
Bonjour, je me permet de revenir vers vous après étude de l'algorithme Astar (A*) et j'ai un peu de mal.
Je m'explique, mon image connaît déjà son objectif et détecte aussi les collisions par analyse de la couleur des pixels, seul un détail m'échappe encore : si l'image rencontre un obstacle, comment je fais pour que le jeu calcule le chemin le plus court ?
J'ai bien essayé de comprendre et de traduire en c l'algorithme Astar trouvé sur Wikipédia mais je bloque :
// Permet de récupérer les données des cases
typedef struct
{
int x, y;
int cout_f, heuristique; // cout_f : cout pour aller du point de départ au noeud considéré
// heuristique : cout pour aller du noeud considéré au point de destination
}noeud;
// Permet de comparer les données de 2 cases
void Comparaison_between_2_locations(noeud n1,noeud n2)
{
if(n1.heuristique < n2.heuristique)
{
return 1;
}
else if(n1.heuristique == n2.heuristique)
{
return 0;
}
else
{
return -1;
}
}
// Permet de calculer le chemin le plus court en fonction des données des cases comparés
void Shortest_path_to_destination(unsigned int tab[17][17],noeud objective,noeud departure)
{
}
// Placer les différentes cases de l'image dans deux tableaux pour séparer les cases où on peut se déplacer
// et celles où on ne peut pas se déplacer selon leur couleur
// Pseudo Code de la fonction
/*Fonction cheminPlusCourt(g:Graphe, objectif:Nœud, depart:Nœud)
closedList = File()
openList = FilePrioritaire(comparateur=compare2Noeuds)
openList.ajouter(depart)
tant que openList n'est pas vide
u = openList.depiler()
si u.x == objectif.x et u.y == objectif.y
reconstituerChemin(u)
terminer le programme
pour chaque voisin v de u dans g
si v existe dans closedList ou si v existe dans openList avec un cout inférieur
neRienFaire()
sinon
v.cout = u.cout +1
v.heuristique = v.cout + distance([v.x, v.y], [objectif.x, objectif.y])
openList.ajouter(v)
closedList.ajouter(u)
terminer le programme (avec erreur)*/
J'ai bien compris que dans mon cas je dois placer les cases (ici des pixels) dans deux tableaux différents (un pour les pixels où je peux me déplacer et un autre pour ceux où je ne peux pas aller), puis faire en sorte de calculer le trajet le plus mais je ne comprends pas comment faire pour cette dernière étape.
Si vous avez des idées, s'il vous plaît faites en moi part.
Edit : j'ai plus ou moins compris le code, il y a encore des irréductibles : j'ai compris que "u" est la case où se trouve l'image et "v" représente les 8 cases adjacentes de "u" mais lors de la comparaison de 2 nœuds dans la fonction "cheminPlusCourt", quels sont les points à comparer ? ceux dans openlist ou simplement départ et objectif ?
- Edité par ReunanBeauvois 24 juin 2019 à 23:55:59
J'ai recherché de mon côté et voilà ce que ça donne :
typedef struct
{
int x, y;
int cout_f, heuristique; // cout_f : cout pour aller du point de départ au noeud considéré
// heuristique : cout pour aller du noeud considéré au point de destination
}noeud;
// Permet de comparer les données de 2 cases
void Comparaison_between_2_locations(noeud n1,noeud n2)
{
if(n1.heuristique < n2.heuristique)
{
return 1;
}
else if(n1.heuristique == n2.heuristique)
{
return 0;
}
else
{
return -1;
}
}
// Permet de calculer le chemin le plus court en fonction des données des cases comparés
void Shortest_path_to_destination(unsigned int tab[17][17],noeud objective,noeud departure,SDL_Rect *rect,SDL_Surface*surface)
{
unsigned int Close_tab[462400][4];
unsigned int Open_tab[462400][4];
noeud a;
noeud b1,b2,b3,b4,b5,b6,b7,b8;
int i;
int k;
for(i=0;i<462400;i++)
{
if((SDL_GetPixel32(surface,rect->x,rect->y)==SDL_MapRGB(surface->format,0,0,0))||(SDL_GetPixel32(surface,rect->x,rect->y)==SDL_MapRGB(surface->format,2,0,0)))
{
a.x=rect->x;
a.y=rect->y;
Close_tab[i][0]=a.x;
Close_tab[i][1]=a.y;
Close_tab[i][2]=a.cout_f;
Close_tab[i][3]=a.heuristique;
}
if((SDL_GetPixel32(surface,rect->x,rect->y)!=SDL_MapRGB(surface->format,0,0,0))||(SDL_GetPixel32(surface,rect->x,rect->y)!=SDL_MapRGB(surface->format,2,0,0)))
{
a.x=rect->x;
a.y=rect->y;
Open_tab[i][0]=a.x;
Open_tab[i][1]=a.y;
Open_tab[i][2]=a.cout_f;
Open_tab[i][3]=a.heuristique;
}
//Utiliser la fonction de comparaison entre les points de Open_tab avant d'ajouter departure
if((Open_tab[i+1][0]==0)&&(Open_tab[i+1][1]==0)&&(Open_tab[i+1][2]==0)&&(Open_tab[i+1][3]==0))
{
Open_tab[i+1][0]=departure.x;
Open_tab[i+1][1]=departure.y;
Open_tab[i+1][2]=departure.cout_f;
Open_tab[i+1][3]=departure.heuristique;
}
}
for(k=0;k<462400;k++)
{
while((Open_tab[k+1][0]!=NULL)&&(Open_tab[k+1][1]!=NULL))
{
//Regarder le premier point de Open_tab et le retirer pour le placer temporairement dans Close_tab
if((Open_tab[0][0]==objective.x)&&(Open_tab[0][1]==objective.y))
{
//tracer chemin de u qui est la case où l'image se trouve actuellement
return 1;
}
//Vérifier chacune des cases adjacentes de la position actuelle :
//rect.x+1 et rect.y
//rect.x-1 et rect.y
//rect.x et rect.y+1
//rect.x et rect.y-1
//rect.x+1 et rect.y+1
//rect.x+1 et rect.y-1
//rect.x-1 et rect.y+1
//rect.x-1 et rect.y-1
b1.x=Open_tab[0][0]+1;
b1.y=Open_tab[0][1];
b2.x=Open_tab[0][0]-1;
b2.y=Open_tab[0][1];
b3.x=Open_tab[0][0];
b3.y=Open_tab[0][1]+1;
b4.x=Open_tab[0][0];
b4.y=Open_tab[0][1]-1;
b5.x=Open_tab[0][0]+1;
b5.y=Open_tab[0][1]+1;
b6.x=Open_tab[0][0]+1;
b6.y=Open_tab[0][1]-1;
b7.x=Open_tab[0][0]-1;
b7.y=Open_tab[0][1]+1;
b8.x=Open_tab[0][0]-1;
b8.y=Open_tab[0][1]-1;
if(((Close_tab[k][0]==b1.x)&&(Close_tab[k][1]==b1.y))||((Close_tab[k][0]==b2.x)&&(Close_tab[k][1]==b2.y))||((Close_tab[k][0]==b3.x)&&(Close_tab[k][1]==b3.y))||((Close_tab[k][0]==b4.x)&&(Close_tab[k][1]==b4.y))||((Close_tab[k][0]==b5.x)&&(Close_tab[k][1]==b5.y))||((Close_tab[k][0]==b6.x)&&(Close_tab[k][1]==b6.y))||((Close_tab[k][0]==b7.x)&&(Close_tab[k][1]==b7.y))||((Close_tab[k][0]==b8.x)&&(Close_tab[k][1]==b8.y)))
{
//Ne pas oublier de vérifier s'il existe un b dans open_tab avec un cout_f inferieur
return 0;
}
else
{
//Apres verification de b avec le cout le plus faible :
//exemple avec b1 :
b1.cout_f = Open_tab[0][2]+1;
b1.heuristique = b1.cout_f + sqrt(((objective.x-b1.x)*(objective.x-b1.x))+((objective.y-b1.y)*(objective.y-b1.y)));
if((Open_tab[k][0]!=b1.x)&&(Open_tab[k][1]!=b1.y)&&(Open_tab[k][2]!=b1.cout_f)&&(Open_tab[k][3]!=b1.heuristique))
{
Open_tab[k][0]=b1.x;
Open_tab[k][1]=b1.y;
Open_tab[k][2]=b1.cout_f;
Open_tab[k][3]=b1.heuristique;
}
if((Close_tab[k][0]!=Open_tab[0][0])&&(Close_tab[k][1]!=Open_tab[0][1])&&(Close_tab[k][2]!=Open_tab[0][2])&&(Close_tab[k][3]!=Open_tab[0][3]))
{
Close_tab[k][0]=Open_tab[0][0];
Close_tab[k][1]=Open_tab[0][1];
Close_tab[k][2]=Open_tab[0][2];
Close_tab[k][3]=Open_tab[0][3];
}
}
return -1;
}
}
}
Je ne sais pas si tel quel mon programme est en mesure d'ajouter un élément dans un tableau et uniquement un seul, par exemple si j'ai :
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
unsigned int tab[5]={1,2,3,0,0};
//Ainsi, seuls trois éléments sur cinq sont
//différents de 0.
//Maintenant il faut que lors de l'ajout d'un nouvel
//élément dans le tableau, seul tab[3] soit influencé.
//Par exemple :
printf("\nEntrez la valeur de l'element à ajouter : ");
scanf("%d",&tab[3]);
printf("\n%d",tab[0]);
printf("\n%d",tab[1]);
printf("\n%d",tab[2]);
printf("\n%d",tab[3]);
printf("\n%d",tab[4]);
return 0;
}
Ici c'est facile car c'est fait manuellement, mais si je veux que ce soit fait automatiquement grâce à une boucle for, cette dernière doit d'abord vérifier si les éléments sont différents de 0 et modifier le premier élément identifié comme tel après la liste des valeurs déjà présentes :
Par exemple, tab[10]={12,10,45,75,563,454,0,0,0,0} est un tableau à dix éléments, ici la valeur que je souhaite modifier est uniquement la valeur de tab[6], celles des trois dernières ça m'est égal.
L'exemple suivant fait ce que je demande seulement si la boucle d'analyse du tableau est arrêtée comme ça :
#include <stdio.h>
#include <stdlib.h>
#define N 6
int main(void)
{
unsigned int tab2[6]={1,2,3,0,0,0};
int i=0;
int t=0;
printf("\nApercu de la liste avant l'ajout de nouveaux elements :");
printf("\n");
printf("\n%d",tab2[0]);
printf("\n%d",tab2[1]);
printf("\n%d",tab2[2]);
printf("\n%d",tab2[3]);
printf("\n%d",tab2[4]);
printf("\n%d",tab2[5]);
printf("\n");
for(i=0;i<N;i++)
{
if((tab2[i]==0)&&(t==0))
{
printf("\nEntrer la valeur que vous voulez ajouter : ");
scanf("%d",&tab2[i]);
printf("\n%d",tab2[i]);
t=1;
}
}
printf("\n");
printf("\nApercu de la liste apres l'ajout de nouveaux elements :");
printf("\n");
printf("\n%d",tab2[0]);
printf("\n%d",tab2[1]);
printf("\n%d",tab2[2]);
printf("\n%d",tab2[3]);
printf("\n%d",tab2[4]);
printf("\n%d",tab2[5]);
return 0;
}
Si je dois faire comme ça, il faut que je remette à 0 la valeur de t plusieurs fois jusqu'à ce que le pathfinding soit terminé.
Là où je piétine, c'est lorsque Open_tab a été rempli, je dois comparer des nœuds mais je dois bien comparer chaque nœud de cette liste entre eux, on est d'accord ?
En attendant une réponse, je vais continuer à vérifier si je n'ai pas fait d'erreur dans ce code.
Merci d'avance
PS : quand ce code marchera à la perfection, je le laisserai ici.
- Edité par ReunanBeauvois 26 juin 2019 à 20:23:21
Désolé Mais il y a tellement de copier coller dans ton code. Je vais essayer de prendre des fragments de code et te dire des trucs qui vont pas
typedef struct
{
int x, y;
int cout_f, heuristique; // cout_f : cout pour aller du point de départ au noeud considéré
// heuristique : cout pour aller du noeud considéré au point de destination
}noeud;
/* ... */
{
unsigned int Close_tab[462400][4];
/* ... */
Close_tab[i][0]=a.x;
Close_tab[i][1]=a.y;
Close_tab[i][2]=a.cout_f;
Close_tab[i][3]=a.heuristique;
Pourquoi ne pas avoir fait tout simplement un tableau de noeud ?
typedef struct
{
int x, y;
int cout_f, heuristique; // cout_f : cout pour aller du point de départ au noeud considéré
// heuristique : cout pour aller du noeud considéré au point de destination
}noeud;
/* ... */
{
noeud Close_tab[462400];
/* ... */
Close_tab[i] = a;
Comme ça c'est beaucoup plus clair, on sait ce qu'on manipule.
Si par la suite t'as vraiment besoin de convertir ta structure en tableau d'entiers (je ne vois pas trop pourquoi tu voudrais faire ça mais tu as peut-être tes raisons ?), tu peux utiliser memcpy. Mais faut faire super attention quand on fait ça, à cause du padding parfois inséré dans les structures. Par exemple, si tu mets dans ta structure un int, un char, puis un int, tu auras peut-être du padding juste après le char à cause de contraintes d'alignements sur 4 octets. (je prends ici le cas où le char est sur 1 octet, le int est sur 4 octets, et l'alignement de la machine est sur 4 octets).
Pourquoi tu veux utiliser la valeur des pixels ? Si je relis tes posts précédents apparemment tu veux faire un algo du plus court chemin sur.. des pixels.. pourquoi pas, mais quelle en est l'utilité ? T'es sûr que c'est bien ce que tu veux faire ? Un pixel c'est petit - si dans ton jeu ton personnage ne fait qu'un seul pixel, le joueur ne va pas y voir grand chose.
Les algos de plus court chemin ça peut servir dans certains jeux oui, mais en général ces algos vont être faits sur des choses de plus haut niveau, comme par exemple une grille. Par exemple, si j'ai un labyrinthe, on pourrait imaginer que je représente mon labyrinthe par une grille de 50x50, chaque élément de cette grille étant un entier (énumération) m'indiquant si c'est un sol ou un mur. Et à partir de cette grille de 50x50 je pourrai faire du pathfinding - mais surtout pas à partir des pixels ! Si je le fais à partir des pixels ça veut dire que plus ma résolution augmente plus ça devient difficile de faire du pathfinding - tu complexifies le problème pour rien.
A part si t'as vraiment besoin de faire du pathfinding sur des pixels, parce que tu te recodes une sorte de Paint/GIMP ?
b1.x=Open_tab[0][0]+1;
b1.y=Open_tab[0][1];
b2.x=Open_tab[0][0]-1;
b2.y=Open_tab[0][1];
b3.x=Open_tab[0][0];
b3.y=Open_tab[0][1]+1;
b4.x=Open_tab[0][0];
b4.y=Open_tab[0][1]-1;
b5.x=Open_tab[0][0]+1;
b5.y=Open_tab[0][1]+1;
b6.x=Open_tab[0][0]+1;
b6.y=Open_tab[0][1]-1;
b7.x=Open_tab[0][0]-1;
b7.y=Open_tab[0][1]+1;
b8.x=Open_tab[0][0]-1;
b8.y=Open_tab[0][1]-1;
if(((Close_tab[k][0]==b1.x)&&(Close_tab[k][1]==b1.y))||((Close_tab[k][0]==b2.x)&&(Close_tab[k][1]==b2.y))||((Close_tab[k][0]==b3.x)&&(Close_tab[k][1]==b3.y))||((Close_tab[k][0]==b4.x)&&(Close_tab[k][1]==b4.y))||((Close_tab[k][0]==b5.x)&&(Close_tab[k][1]==b5.y))||((Close_tab[k][0]==b6.x)&&(Close_tab[k][1]==b6.y))||((Close_tab[k][0]==b7.x)&&(Close_tab[k][1]==b7.y))||((Close_tab[k][0]==b8.x)&&(Close_tab[k][1]==b8.y)))
{
//Ne pas oublier de vérifier s'il existe un b dans open_tab avec un cout_f inferieur
return 0;
}
Okay, et maintenant imagine qu'on rajoute une dimension pour faire du pathfinding en 3D : bon courage
On est des programmeurs, on a des outils qui permettent de répéter des calculs en faisant un minimum de copier coller. Ici, comment tu pourrais faire ?
Tu as 2 dimensions, chacune ayant 2 directions possibles. Tu pourrais imaginer itérer sur deux variables : dx qui te donne le déplacement en x (soit 1, soit -1), et dy, qui te donne le déplacement en y. Soit 1, soit -1.
Ton code devient alors quelque chose du genre :
for (dx = -1 ; dx <= 1 ; dx += 2){
for (dy = -1; dy <= 1; dy += 2){
b.x = Open_tab[0].x + dx;
b.y = Open_tab[0].y + dy;
if (Close_tab[k].x == b.x && Close_tab[k].y == b.y){
return 0;
}
}
}
Si je ne me suis trompé ça fait la même chose que ton bout de code. C'est 3-4 fois plus court, beaucoup plus lisible, plus maintenable, et aussi plus naturel.
En fait, à chaque fois que tu fais du copier/coller, pose toi la question : est-ce que tu pourrais éviter de faire ce copier coller ? Si la réponse est oui, tu devrais le faire. Moins de lignes copiées/collées = moins d'erreurs - et puis c'est plus agréable à écrire aussi, plutôt que de recopier à la main les 8 cas..
Sinon je ne comprends pas le reste de ce que tu as écris Je ne sais pas à quoi correspond 0, tes listes, Open_tab, close_tab..
ça sera peut être plus simple à comprendre si tu nous indiques quel pseudo code tu essaies d'implémenter ? Et quelle variable de ton code C est l'implémentation de quelle variable du pseudo code ?
- Edité par potterman28wxcv 26 juin 2019 à 23:23:15
for (dx = -1 ; dx <= 1 ; dx += 1){
for (dy = -1; dy <= 1; dy += 1){
b.x = Open_tab[0].x + dx;
b.y = Open_tab[0].y + dy;
if (Close_tab[k].x == b.x && Close_tab[k].y == b.y){
return 0;
}
}
}
Me permet d'analyser 9 cases (la case où se trouve l'image et ses 8 cases voisines) est utile dans la mesure d'une tilemap (le cas échéant pour moi).
Avec le code ci-dessous je parviens à remplir deux listes avec les éléments d'une grille en fonction de la valeur des éléments compris dans la grille.
Avec cet exemple, les cases font 40 pixels/40 pixels :
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
unsigned int graphe[4][4]={
{4,0,2,0},
{4,1,1,0},
{0,1,1,3},
{5,3,0,0}};
unsigned int numbers_accepted[3]={1,2,3};
unsigned int numbers_denied[3]={0,4,5};
int i,j,k;
for(i=0;i<4;i++)
{
for(j=0;j<4;j++)
{
for(k=0;k<3;k++)
{
if(graphe[i][j]==numbers_accepted[k])
{
tab[i][j].x=j*40;
tab[i][j].y=i*40;
}
if(graphe[i][j]==numbers_denied[k])
{
tab2[i][j].x=j*40;
tab2[i][j].y=i*40;
}
}
printf("\nPosition d'un element de Open_list : (%d,%d,%d,%d) ",tab[i][j].x,tab[i][j].y,tab[i][j].cout_f,tab[i][j].heuristique);
}
}
}
J'obtiens ces résultats :
Position d'un element de Open_list : (0,0,0,0)
Position d'un element de Open_list : (0,0,0,0)
Position d'un element de Open_list : (80,0,0,3)
Position d'un element de Open_list : (0,0,0,0)
Position d'un element de Open_list : (0,0,0,0)
Position d'un element de Open_list : (40,40,0,75)
Position d'un element de Open_list : (80,40,0,22)
Position d'un element de Open_list : (0,0,0,0)
Position d'un element de Open_list : (0,0,0,0)
Position d'un element de Open_list : (40,80,0,45)
Position d'un element de Open_list : (80,80,0,1)
Position d'un element de Open_list : (120,80,0,61)
Position d'un element de Open_list : (0,0,0,0)
Position d'un element de Open_list : (40,120,0,38)
Position d'un element de Open_list : (0,0,0,0)
Position d'un element de Open_list : (0,0,0,0)
Le code a presque bien fait ce que je veux car les éléments (0,0,0,0) ne m’intéresse pas (et heureusement car mes tilemap ne contiendront jamais de positions où moi ou les autres entités pourront aller en (0,0)) mais j'aurais aimé avoir des résultats dans ce genre :
Position d'un element de Open_list : (80,80,0,1)
Position d'un element de Open_list : (80,0,0,3)
Position d'un element de Open_list : (80,40,0,22)
Position d'un element de Open_list : (40,120,0,38)
Position d'un element de Open_list : (40,80,0,45)
Position d'un element de Open_list : (120,80,0,61)
Position d'un element de Open_list : (40,40,0,75)
Position d'un element de Open_list : (0,0,0,0)
Position d'un element de Open_list : (0,0,0,0)
Position d'un element de Open_list : (0,0,0,0)
Position d'un element de Open_list : (0,0,0,0)
Position d'un element de Open_list : (0,0,0,0)
Position d'un element de Open_list : (0,0,0,0)
Position d'un element de Open_list : (0,0,0,0)
Position d'un element de Open_list : (0,0,0,0)
Position d'un element de Open_list : (0,0,0,0)
Avec le code ci-dessous j'ai quelque chose intéressant :
void tricroissantdeuxdimension(noeud tab[][4], int tab_size, int tab_size2) //indispensable pour le pathfinding
{
int i,j,k;
int tmp=0;
int tmp2=0;
int tmp3=0;
int tmp4=0;
for(i = 0; i < tab_size; i++) //On veut remplir la case i du tableau
{
for(j = 0; j < tab_size2; j++) //On vérifie s'il n'y a pas de nombre inférieur
{
for(k=j+1;k<tab_size2;k++)
{
if(tab[k][i].heuristique < tab[j][i].heuristique)
{
tmp = tab[j][i].x; //Si c'est le cas on intervertit les cases
tab[j][i].x = tab[k][i].x;
tab[k][i].x = tmp;
tmp2 = tab[j][i].y; //Si c'est le cas on intervertit les cases
tab[j][i].y = tab[k][i].y;
tab[k][i].y = tmp2;
tmp3 = tab[j][i].cout_f; //Si c'est le cas on intervertit les cases
tab[j][i].cout_f = tab[k][i].cout_f;
tab[k][i].cout_f = tmp3;
tmp4 = tab[j][i].heuristique; //Si c'est le cas on intervertit les cases
tab[j][i].heuristique = tab[k][i].heuristique;
tab[k][i].heuristique = tmp4;
}
//printf("\ntab[%d][%d].x=%d",i,k,tab[i][k].x);
}
printf("\nPosition d'un element de Open_list : (%d,%d,%d,%d)",tab[j][i].x,tab[j][i].y,tab[j][i].cout_f,tab[j][i].heuristique); //Dans les cases suivantes
}
}
}
Mais j'obtiens ces résultats :
Position d'un element de Open_list : (0,0,0,0)
Position d'un element de Open_list : (0,0,0,0)
Position d'un element de Open_list : (0,0,0,0)
Position d'un element de Open_list : (0,0,0,0)
Position d'un element de Open_list : (0,0,0,0)
Position d'un element de Open_list : (40,120,0,38)
Position d'un element de Open_list : (40,80,0,45)
Position d'un element de Open_list : (40,40,0,75)
Position d'un element de Open_list : (0,0,0,0)
Position d'un element de Open_list : (80,80,0,1)
Position d'un element de Open_list : (80,0,0,3)
Position d'un element de Open_list : (80,40,0,22)
Position d'un element de Open_list : (0,0,0,0)
Position d'un element de Open_list : (0,0,0,0)
Position d'un element de Open_list : (0,0,0,0)
Position d'un element de Open_list : (120,80,0,61)
La comparaison a marché mais le problème des matrices c'est que c'est des tableaux de tableaux simples, la comparaison a lieu uniquement dans les tableaux simples de la matrices.
Si quelqu'un a des idées pour me sortir de cette impasse, je lui en serais reconnaissant.
PS : Je maîtrise assez mal le java mais je peux le comprendre, évitez le c++ car je ne le maîtrise pas, si c'est des codes en python ou en c ou même des algo ça me va.
C'est bon, j'ai réussi ! Le code marche presque parfaitement, à quelques détails près :
Lorsque la fonction est appelée, l'application SDL est très lente et parfois deux emplacements ont la même heuristique - souvent la plus petite - ce qui pose problème pour trouver le chemin le plus court. Comment résoudre ces 2 problèmes ?
Tout ça est codé sur Code Blocks en C sous Windows 10, est-ce que la lenteur de l'application est due à mon pc ou parce que en appel cette fonction est trop lourde ?
Merci d'avance.
Et merci encore pour tous les conseils que vous m'avez donnés
PS : ça a été une vraie plaie à traduire en c ce pseudo code de A* sur Wikipédia XD
- Edité par ReunanBeauvois 12 juillet 2019 à 16:29:32
Ton code est trop difficile à lire pour être capable d'exprimer quoi que ce soit.
Ce que je vois c'est que à un moment tu as une quadruple boucle for le tout dans une boucle while - pour avoir une idée de la lenteur tu peux t'amuser a compter combien de fois les instructions de la 4eme boucle for sont exécutées en fonction de la taille du problème (ici la taille de ton écran ?).
Je vois des indices 0 qui sortent un peu de nulle part, du copier coller à certains endroits, un gros bloc au lieu de faire ça en petite fonction, tout ça n'aide pas à la lisibilité. Tu ne mets même pas le pseudo code qui correspond à telle ou telle chose donc y a vraiment que toi qui peut comprendre ce code là et être capable de l'analyser .
Pour la performance tu peux tenter de compiler en -O3
Mais de toute façon quelle que soit l'implémentation ça ne va pas faire de miracle : si je me souviens bien A* a une complexité exponentielle à la taille du chemin le plus court. C'est à dire que si tu rajoutes une distance de 1 entre le point A et le point B, tu doubles le temps d'exécution du pire cas. Comme en plus de ça tu veux déterminer le chemin le plus court entre deux pixel et il y a beaucoup de pixel, forcément c'est très lent.
Mais c'est déjà énorme que t'aies réussi à coder ça et que ça marche - c'est pas un simple algo, ni à coder ni à deboguer
Après de nombreuses recherches sur internet, j'ai trouvé ce code qui permet de supprimer les doublons :
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define size 11
typedef struct
{
int x, y;
int cout_f, heuristique; // cout_f : cost to go from the departure to the next tile
// heuristique : cost to go from the previous tile to the goal
}noeud;
int main (void)
{
system("cls");
noeud tab[size] = {0};
tab[0].x=20,tab[0].y=40,tab[0].cout_f=2,tab[0].heuristique=114;
tab[1].x=20,tab[1].y=40,tab[1].cout_f=2,tab[1].heuristique=114;
tab[2].x=20,tab[2].y=40,tab[2].cout_f=2,tab[2].heuristique=114;
tab[3].x=0,tab[3].y=40,tab[3].cout_f=1,tab[3].heuristique=14;
tab[4].x=20,tab[4].y=40,tab[4].cout_f=1,tab[4].heuristique=24;
tab[5].x=40,tab[5].y=60,tab[5].cout_f=4,tab[5].heuristique=33;
tab[6].x=40,tab[6].y=60,tab[6].cout_f=4,tab[6].heuristique=33;
tab[7].x=20,tab[7].y=40,tab[7].cout_f=3,tab[7].heuristique=114;
tab[8].x=20,tab[8].y=40,tab[8].cout_f=3,tab[8].heuristique=114;
tab[9].x=20,tab[9].y=40,tab[9].cout_f=3,tab[9].heuristique=114;
//tab[10].x=20,tab[10].y=80,tab[10].cout_f=3,tab[10].heuristique=114;
int RL_FIN_TRAIT_TRI;
int i;
int j;
int nb_tab=size;
int compteur_doublon = 0;
printf("**************** INIT ***********************\n");
for (i=0;i<nb_tab;i++)
{
printf("tab[%d]=(%d,%d,%d,%d)\n",i,tab[i].x,tab[i].y,tab[i].cout_f,tab[i].heuristique);
}
printf("**************** DURING ***********************\n");
RL_FIN_TRAIT_TRI=0;
while (RL_FIN_TRAIT_TRI!=1)
{
RL_FIN_TRAIT_TRI=1;
for( i=0 ; i<nb_tab-1 ; i++ )
{
if(tab[i].x==tab[i+1].x && tab[i].y==tab[i+1].y && tab[i].cout_f==tab[i+1].cout_f && tab[i].heuristique==tab[i+1].heuristique)
{
for(j=i+1;j<(nb_tab-1);j++)
{
tab[j].x = tab[j+1].x;
tab[j].y = tab[j+1].y;
tab[j].cout_f = tab[j+1].cout_f;
tab[j].heuristique = tab[j+1].heuristique;
}
RL_FIN_TRAIT_TRI = 0;
nb_tab = nb_tab - 1;
}
else
{
}
}
}
nb_tab=11;
printf("**************** UPDATED ***********************\n");
for (i=0;i<nb_tab;i++)
{
printf("tab[%d]=(%d,%d,%d,%d)\n",i,tab[i].x,tab[i].y,tab[i].cout_f,tab[i].heuristique);
}
return 0;
}
Mais même avec ce morceau de code intégré dans le pathfinding, ce code n'est exécuté qu'une seule fois et sans ce morceau de code voici ce que j'ai comme résultats avec comme position de départ (40,40) et d'arrivée (120,120) :
***Pathfinding***
Apercu de Open_list au debut (il n'y a que les donnees de depart) :
Open_list[0]=(40,40,0,0)
Open_list[1]=(0,0,0,0)
Open_list[2]=(0,0,0,0)
Open_list[3]=(0,0,0,0)
Open_list[4]=(0,0,0,0)
Open_list[5]=(0,0,0,0)
Open_list[6]=(0,0,0,0)
Open_list[7]=(0,0,0,0)
Open_list[8]=(0,0,0,0)
Open_list[9]=(0,0,0,0)
Open_list[10]=(0,0,0,0)
Open_list[11]=(0,0,0,0)
Open_list[12]=(0,0,0,0)
Open_list[13]=(0,0,0,0)
Open_list[14]=(0,0,0,0)
Open_list[15]=(0,0,0,0)
Open_list[16]=(0,0,0,0)
Open_list[17]=(0,0,0,0)
Open_list[18]=(0,0,0,0)
Open_list[19]=(0,0,0,0)
Apercu de Close_list au debut (elle est vide) :
Close_list[0]=(0,0,0,0)
Close_list[1]=(0,0,0,0)
Close_list[2]=(0,0,0,0)
Close_list[3]=(0,0,0,0)
Close_list[4]=(0,0,0,0)
Close_list[5]=(0,0,0,0)
Close_list[6]=(0,0,0,0)
Close_list[7]=(0,0,0,0)
Close_list[8]=(0,0,0,0)
Close_list[9]=(0,0,0,0)
Close_list[10]=(0,0,0,0)
Close_list[11]=(0,0,0,0)
Close_list[12]=(0,0,0,0)
Close_list[13]=(0,0,0,0)
Close_list[14]=(0,0,0,0)
Close_list[15]=(0,0,0,0)
Close_list[16]=(0,0,0,0)
Close_list[17]=(0,0,0,0)
Close_list[18]=(0,0,0,0)
Close_list[19]=(0,0,0,0)
Le premier element de Open_list est retire pour etre analyse :
memory[0]=(40,40,0,0)
Analyse de la case actuelle et de ses voisines :
neighbours[0]=(0,0,0,0)
neighbours[1]=(0,40,0,0)
neighbours[2]=(0,80,0,0)
neighbours[3]=(40,0,0,0)
neighbours[4]=(40,40,0,0)
neighbours[5]=(40,80,0,0)
neighbours[6]=(80,0,0,0)
neighbours[7]=(80,40,0,0)
neighbours[8]=(80,80,0,0)
Calcul du cout et de l'heuristique :
true_memory[0]=(0,0,0,0)
true_memory[1]=(0,40,1,145)
true_memory[2]=(0,80,1,127)
true_memory[3]=(40,0,1,145)
true_memory[4]=(40,40,1,114)
true_memory[5]=(40,80,1,90)
true_memory[6]=(80,0,1,127)
true_memory[7]=(80,40,1,90)
true_memory[8]=(80,80,1,57)
On retire les voisins inutiles ainsi que la position actuelle :
Open_list[0]=(80,40,1,90)
Open_list[1]=(0,0,0,0)
Open_list[2]=(0,0,0,0)
Open_list[3]=(0,0,0,0)
Open_list[4]=(0,0,0,0)
Open_list[5]=(0,0,0,0)
Open_list[6]=(0,0,0,0)
Open_list[7]=(0,0,0,0)
Open_list[8]=(0,0,0,0)
Open_list[9]=(0,0,0,0)
Open_list[10]=(0,0,0,0)
Open_list[11]=(0,0,0,0)
Open_list[12]=(0,0,0,0)
Open_list[13]=(0,0,0,0)
Open_list[14]=(0,0,0,0)
Open_list[15]=(0,0,0,0)
Open_list[16]=(0,0,0,0)
Open_list[17]=(0,0,0,0)
Open_list[18]=(0,0,0,0)
Open_list[19]=(0,0,0,0)
C'est bien mais ce n'est pas ce qu'on veux !
Veritable apercu de Open-list apres le tri :
Open_list[0]=(80,40,1,90)
Open_list[1]=(0,0,0,0)
Open_list[2]=(0,0,0,0)
Open_list[3]=(0,0,0,0)
Open_list[4]=(0,0,0,0)
Open_list[5]=(0,0,0,0)
Open_list[6]=(0,0,0,0)
Open_list[7]=(0,0,0,0)
Open_list[8]=(0,0,0,0)
Open_list[9]=(0,0,0,0)
Open_list[10]=(0,0,0,0)
Open_list[11]=(0,0,0,0)
Open_list[12]=(0,0,0,0)
Open_list[13]=(0,0,0,0)
Open_list[14]=(0,0,0,0)
Open_list[15]=(0,0,0,0)
Open_list[16]=(0,0,0,0)
Open_list[17]=(0,0,0,0)
Open_list[18]=(0,0,0,0)
Open_list[19]=(0,0,0,0)
On ajoute l'ancienne position de l'entite dans Close_list :
Close_list[0]=(40,40,1,114)
Close_list[1]=(0,0,0,0)
Close_list[2]=(0,0,0,0)
Close_list[3]=(0,0,0,0)
Close_list[4]=(0,0,0,0)
Close_list[5]=(0,0,0,0)
Close_list[6]=(0,0,0,0)
Close_list[7]=(0,0,0,0)
Close_list[8]=(0,0,0,0)
Close_list[9]=(0,0,0,0)
Close_list[10]=(0,0,0,0)
Close_list[11]=(0,0,0,0)
Close_list[12]=(0,0,0,0)
Close_list[13]=(0,0,0,0)
Close_list[14]=(0,0,0,0)
Close_list[15]=(0,0,0,0)
Close_list[16]=(0,0,0,0)
Close_list[17]=(0,0,0,0)
Close_list[18]=(0,0,0,0)
Close_list[19]=(0,0,0,0)
L'entite n'a pas encore atteint son objectif, on recommence !
memory[0]=(80,40,1,90)
Analyse de la case actuelle et de ses voisines :
neighbours[0]=(40,0,1,90)
neighbours[1]=(40,40,1,90)
neighbours[2]=(40,80,1,90)
neighbours[3]=(80,0,1,90)
neighbours[4]=(80,40,1,90)
neighbours[5]=(80,80,1,90)
neighbours[6]=(120,0,1,90)
neighbours[7]=(120,40,1,90)
neighbours[8]=(120,80,1,90)
Calcul du cout et de l'heuristique :
true_memory[0]=(40,0,2,146)
true_memory[1]=(40,40,2,115)
true_memory[2]=(40,80,2,91)
true_memory[3]=(80,0,2,128)
true_memory[4]=(80,40,2,91)
true_memory[5]=(80,80,2,58)
true_memory[6]=(120,0,2,122)
true_memory[7]=(120,40,2,82)
true_memory[8]=(120,80,2,42)
On retire les voisins inutiles ainsi que la position actuelle :
Open_list[0]=(40,40,2,115)
Open_list[1]=(40,40,1,114)
Open_list[2]=(120,40,2,82)
Open_list[3]=(80,80,2,58)
Open_list[4]=(0,0,0,0)
Open_list[5]=(0,0,0,0)
Open_list[6]=(0,0,0,0)
Open_list[7]=(0,0,0,0)
Open_list[8]=(0,0,0,0)
Open_list[9]=(0,0,0,0)
Open_list[10]=(0,0,0,0)
Open_list[11]=(0,0,0,0)
Open_list[12]=(0,0,0,0)
Open_list[13]=(0,0,0,0)
Open_list[14]=(0,0,0,0)
Open_list[15]=(0,0,0,0)
Open_list[16]=(0,0,0,0)
Open_list[17]=(0,0,0,0)
Open_list[18]=(0,0,0,0)
Open_list[19]=(0,0,0,0)
C'est bien mais ce n'est pas ce qu'on veux !
Veritable apercu de Open-list apres le tri :
Open_list[0]=(80,80,2,58)
Open_list[1]=(120,40,2,82)
Open_list[2]=(40,40,1,114)
Open_list[3]=(40,40,2,115)
Open_list[4]=(0,0,0,0)
Open_list[5]=(0,0,0,0)
Open_list[6]=(0,0,0,0)
Open_list[7]=(0,0,0,0)
Open_list[8]=(0,0,0,0)
Open_list[9]=(0,0,0,0)
Open_list[10]=(0,0,0,0)
Open_list[11]=(0,0,0,0)
Open_list[12]=(0,0,0,0)
Open_list[13]=(0,0,0,0)
Open_list[14]=(0,0,0,0)
Open_list[15]=(0,0,0,0)
Open_list[16]=(0,0,0,0)
Open_list[17]=(0,0,0,0)
Open_list[18]=(0,0,0,0)
Open_list[19]=(0,0,0,0)
On ajoute l'ancienne position de l'entite dans Close_list :
Close_list[0]=(40,40,1,114)
Close_list[1]=(80,40,2,91)
Close_list[2]=(0,0,0,0)
Close_list[3]=(0,0,0,0)
Close_list[4]=(0,0,0,0)
Close_list[5]=(0,0,0,0)
Close_list[6]=(0,0,0,0)
Close_list[7]=(0,0,0,0)
Close_list[8]=(0,0,0,0)
Close_list[9]=(0,0,0,0)
Close_list[10]=(0,0,0,0)
Close_list[11]=(0,0,0,0)
Close_list[12]=(0,0,0,0)
Close_list[13]=(0,0,0,0)
Close_list[14]=(0,0,0,0)
Close_list[15]=(0,0,0,0)
Close_list[16]=(0,0,0,0)
Close_list[17]=(0,0,0,0)
Close_list[18]=(0,0,0,0)
Close_list[19]=(0,0,0,0)
L'entite n'a pas encore atteint son objectif, on recommence !
memory[0]=(80,80,2,58)
Analyse de la case actuelle et de ses voisines :
neighbours[0]=(40,40,2,58)
neighbours[1]=(40,80,2,58)
neighbours[2]=(40,120,2,58)
neighbours[3]=(80,40,2,58)
neighbours[4]=(80,80,2,58)
neighbours[5]=(80,120,2,58)
neighbours[6]=(120,40,2,58)
neighbours[7]=(120,80,2,58)
neighbours[8]=(120,120,2,58)
Calcul du cout et de l'heuristique :
true_memory[0]=(40,40,3,116)
true_memory[1]=(40,80,3,92)
true_memory[2]=(40,120,3,83)
true_memory[3]=(80,40,3,92)
true_memory[4]=(80,80,3,59)
true_memory[5]=(80,120,3,43)
true_memory[6]=(120,40,3,83)
true_memory[7]=(120,80,3,43)
true_memory[8]=(120,120,3,3)
On retire les voisins inutiles ainsi que la position actuelle :
Open_list[0]=(40,40,2,115)
Open_list[1]=(40,40,1,114)
Open_list[2]=(40,40,1,114)
Open_list[3]=(80,40,2,91)
Open_list[4]=(120,40,2,82)
Open_list[5]=(80,120,3,43)
Open_list[6]=(0,0,0,0)
Open_list[7]=(0,0,0,0)
Open_list[8]=(0,0,0,0)
Open_list[9]=(0,0,0,0)
Open_list[10]=(0,0,0,0)
Open_list[11]=(0,0,0,0)
Open_list[12]=(0,0,0,0)
Open_list[13]=(0,0,0,0)
Open_list[14]=(0,0,0,0)
Open_list[15]=(0,0,0,0)
Open_list[16]=(0,0,0,0)
Open_list[17]=(0,0,0,0)
Open_list[18]=(0,0,0,0)
Open_list[19]=(0,0,0,0)
C'est bien mais ce n'est pas ce qu'on veux !
Veritable apercu de Open-list apres le tri :
Open_list[0]=(80,120,3,43)
Open_list[1]=(120,40,2,82)
Open_list[2]=(80,40,2,91)
Open_list[3]=(40,40,1,114)
Open_list[4]=(40,40,1,114)
Open_list[5]=(40,40,2,115)
Open_list[6]=(0,0,0,0)
Open_list[7]=(0,0,0,0)
Open_list[8]=(0,0,0,0)
Open_list[9]=(0,0,0,0)
Open_list[10]=(0,0,0,0)
Open_list[11]=(0,0,0,0)
Open_list[12]=(0,0,0,0)
Open_list[13]=(0,0,0,0)
Open_list[14]=(0,0,0,0)
Open_list[15]=(0,0,0,0)
Open_list[16]=(0,0,0,0)
Open_list[17]=(0,0,0,0)
Open_list[18]=(0,0,0,0)
Open_list[19]=(0,0,0,0)
On ajoute l'ancienne position de l'entite dans Close_list :
Close_list[0]=(40,40,1,114)
Close_list[1]=(80,40,2,91)
Close_list[2]=(80,80,3,59)
Close_list[3]=(0,0,0,0)
Close_list[4]=(0,0,0,0)
Close_list[5]=(0,0,0,0)
Close_list[6]=(0,0,0,0)
Close_list[7]=(0,0,0,0)
Close_list[8]=(0,0,0,0)
Close_list[9]=(0,0,0,0)
Close_list[10]=(0,0,0,0)
Close_list[11]=(0,0,0,0)
Close_list[12]=(0,0,0,0)
Close_list[13]=(0,0,0,0)
Close_list[14]=(0,0,0,0)
Close_list[15]=(0,0,0,0)
Close_list[16]=(0,0,0,0)
Close_list[17]=(0,0,0,0)
Close_list[18]=(0,0,0,0)
Close_list[19]=(0,0,0,0)
L'entite n'a pas encore atteint son objectif, on recommence !
memory[0]=(80,120,3,43)
Analyse de la case actuelle et de ses voisines :
neighbours[0]=(40,80,3,43)
neighbours[1]=(40,120,3,43)
neighbours[2]=(40,160,3,43)
neighbours[3]=(80,80,3,43)
neighbours[4]=(80,120,3,43)
neighbours[5]=(80,160,3,43)
neighbours[6]=(120,80,3,43)
neighbours[7]=(120,120,3,43)
neighbours[8]=(120,160,3,43)
Calcul du cout et de l'heuristique :
true_memory[0]=(40,80,4,93)
true_memory[1]=(40,120,4,84)
true_memory[2]=(40,160,4,93)
true_memory[3]=(80,80,4,60)
true_memory[4]=(80,120,4,44)
true_memory[5]=(80,160,4,60)
true_memory[6]=(120,80,4,44)
true_memory[7]=(120,120,4,4)
true_memory[8]=(120,160,4,44)
On retire les voisins inutiles ainsi que la position actuelle :
Open_list[0]=(40,40,2,115)
Open_list[1]=(40,40,1,114)
Open_list[2]=(40,40,1,114)
Open_list[3]=(40,40,1,114)
Open_list[4]=(80,40,2,91)
Open_list[5]=(80,40,2,91)
Open_list[6]=(120,40,2,82)
Open_list[7]=(80,80,3,59)
Open_list[8]=(120,120,4,4)
Open_list[9]=(0,0,0,0)
Open_list[10]=(0,0,0,0)
Open_list[11]=(0,0,0,0)
Open_list[12]=(0,0,0,0)
Open_list[13]=(0,0,0,0)
Open_list[14]=(0,0,0,0)
Open_list[15]=(0,0,0,0)
Open_list[16]=(0,0,0,0)
Open_list[17]=(0,0,0,0)
Open_list[18]=(0,0,0,0)
Open_list[19]=(0,0,0,0)
C'est bien mais ce n'est pas ce qu'on veux !
Veritable apercu de Open-list apres le tri :
Open_list[0]=(120,120,4,4)
Open_list[1]=(80,80,3,59)
Open_list[2]=(120,40,2,82)
Open_list[3]=(80,40,2,91)
Open_list[4]=(80,40,2,91)
Open_list[5]=(40,40,1,114)
Open_list[6]=(40,40,1,114)
Open_list[7]=(40,40,1,114)
Open_list[8]=(40,40,2,115)
Open_list[9]=(0,0,0,0)
Open_list[10]=(0,0,0,0)
Open_list[11]=(0,0,0,0)
Open_list[12]=(0,0,0,0)
Open_list[13]=(0,0,0,0)
Open_list[14]=(0,0,0,0)
Open_list[15]=(0,0,0,0)
Open_list[16]=(0,0,0,0)
Open_list[17]=(0,0,0,0)
Open_list[18]=(0,0,0,0)
Open_list[19]=(0,0,0,0)
On ajoute l'ancienne position de l'entite dans Close_list :
Close_list[0]=(40,40,1,114)
Close_list[1]=(80,40,2,91)
Close_list[2]=(80,80,3,59)
Close_list[3]=(80,120,4,44)
Close_list[4]=(0,0,0,0)
Close_list[5]=(0,0,0,0)
Close_list[6]=(0,0,0,0)
Close_list[7]=(0,0,0,0)
Close_list[8]=(0,0,0,0)
Close_list[9]=(0,0,0,0)
Close_list[10]=(0,0,0,0)
Close_list[11]=(0,0,0,0)
Close_list[12]=(0,0,0,0)
Close_list[13]=(0,0,0,0)
Close_list[14]=(0,0,0,0)
Close_list[15]=(0,0,0,0)
Close_list[16]=(0,0,0,0)
Close_list[17]=(0,0,0,0)
Close_list[18]=(0,0,0,0)
Close_list[19]=(0,0,0,0)
L'entite n'a pas encore atteint son objectif, on recommence !
memory[0]=(120,120,4,4)
Le chemin le plus court a ete trouve !
Le code trouve bien le chemin selon ce tableau mais ça ne change rien au fait que des doublons apparaissent sans aucune raison :
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define list_size 20
#define tab_size 7
#define tab_size2 7
#define neighbours_size 9
#define denied 1
// For a clearlier comprehension : http://mnemstudio.org/path-finding-a-star.htm
typedef struct
{
int x, y;
int cout_f, heuristique;
// x et y seront les coordonnées de chaque élement du tableau
// cout_f représente le nombre de fois que le calcul de l'heuristique a ete effectue
// l'heuristique (ou la norme) est la distance qui separe la case voisine et la case destination (j'expliquerai en détail un peu plus tard)
}noeud;
int main(void)
{
system("cls"); // J'utilise cette ligne pour réactualiser la cmd pour me retrouver qu'avec les résultats de ce code
unsigned int graphe[tab_size][tab_size2]={ // Je declare un tableau qui servira de monde au programme
{0,0,0,0,0,0,0}, // Vous remarquerez que ce tableau n'est remplit qu'avec deux genres de chiffres : 0 et 1
{0,1,1,1,1,1,0}, // 0 pour les murs et obstacles
{0,0,1,0,0,1,0}, // 1 pour les surfaces où l'entité peut se déplacer
{0,1,1,1,1,0,0},
{0,1,0,0,1,0,0},
{0,1,1,1,1,0,0},
{0,0,0,0,0,0,0}
};
noeud memory[1]={0};
unsigned int numbers_denied[denied]={0}; // Ici j'initialise une mémoire que j'utiliserai pour que le programme reconnaissent les murs
noeud tab[tab_size][tab_size2]={0}; // J'utilise ce tableau pour faire la distinction entre obstacles et sols un peu plus tard
noeud Open_list[list_size]={0}; // Cette liste est importante : elle retient les cases où l'entité peut potentiellement aller
noeud Close_list[list_size]={0}; // Cette liste est importante : elle retient les cases que l'entité devra emprunter pour atteindre son objectif le plus vite possible
noeud neighbours[neighbours_size]={0}; // Cette liste retiendra les voisins de la case actuelle
noeud b={0}; // J'utilise ce tableau de structure pour récupérer les voisins avant de les placer dans le tableau "neighbours"
// Tout un ensemble de variables dont j'expliquerai l'emploi
int i1,i2;
int g,p,a,c,d,f,h,i,j,i3,i4,k,e,l;
int dx,dy;
int x=0;
int n=0;
int max,max2,max3,max4;
int posmax;
g=0;
p=0;
dx=0;
dy=0;
a=0;
c=0;
d=0;
f=0;
h=0;
i=0;
j=0;
e=0;
l=0;
noeud vecteur[100]={0};
noeud depart={40,40,0,0};
noeud objective={80,200,0,0};
//Ajout de départ à Open_list
printf("\n***Pathfinding***");
printf("\n");
printf("\nApercu de Open_list au debut (il n'y a que les donnees de depart) :");
printf("\n");
for(i1=0;i1<tab_size;i1++) // Je remplis ce tableau pour reconnaître les obstacles et les sols
{
for(i2=0;i2<tab_size2;i2++)
{
tab[i1][i2].x=i2*40;
tab[i1][i2].y=i1*40;
}
}
for(g=0;g<list_size;g++) // J'inclus depart dans Open_list pour l'analyser
{
if((Open_list[g].x==0)&&(Open_list[g].y==0)&&(Open_list[g].cout_f==0)&&(Open_list[g].heuristique==0)&&(p==0))
{
Open_list[g].x=depart.x;
Open_list[g].y=depart.y;
Open_list[g].cout_f=depart.cout_f;
Open_list[g].heuristique=depart.heuristique;
p=1;
}
printf("\nOpen_list[%d]=(%d,%d,%d,%d)",g,Open_list[g].x,Open_list[g].y,Open_list[g].cout_f,Open_list[g].heuristique);
}
printf("\n");
printf("\nApercu de Close_list au debut (elle est vide) :");
printf("\n");
for(g=0;g<list_size;g++)
{
printf("\nClose_list[%d]=(%d,%d,%d,%d)",g,Close_list[g].x,Close_list[g].y,Close_list[g].cout_f,Close_list[g].heuristique);
}
printf("\n");
printf("\nLe premier element de Open_list est retire pour etre analyse :");
printf("\n");
while((memory[0].x!=objective.x)||(memory[0].y!=objective.y))
{
memory[0].x=Open_list[0].x;
memory[0].y=Open_list[0].y;
memory[0].cout_f=Open_list[0].cout_f;
memory[0].heuristique=Open_list[0].heuristique;
printf("\nmemory[0]=(%d,%d,%d,%d)",memory[0].x,memory[0].y,memory[0].cout_f,memory[0].heuristique);
Open_list[0].x=0;
Open_list[0].y=0;
Open_list[0].cout_f=0;
Open_list[0].heuristique=0;
if((memory[0].x==objective.x)&&(memory[0].y==objective.y))
{
printf("\n");
printf("\nLe chemin le plus court a ete trouve !");
printf("\n");
//reconstituer le chemin
return 1;
}
printf("\n");
printf("\nAnalyse de la case actuelle et de ses voisines :");
printf("\n");
if(c==0){
for (dx = -1 ; dx <= 1 ; dx += 1){
for (dy = -1; dy <= 1; dy += 1){
b.x = memory[0].x + dx*40;
b.y = memory[0].y + dy*40;
b.cout_f = memory[0].cout_f;
b.heuristique = memory[0].heuristique;
c=1;
if((dx==-1)&&(dy==-1)&&(c==1)){
neighbours[0].x=b.x;
neighbours[0].y=b.y;
neighbours[0].cout_f=b.cout_f;
neighbours[0].heuristique=b.heuristique;
printf("\nneighbours[%d]=(%d,%d,%d,%d)",0,b.x,b.y,b.cout_f,b.heuristique);
}
if((dx==-1)&&(dy==0)&&(c==1)){
neighbours[1].x=b.x;
neighbours[1].y=b.y;
neighbours[1].cout_f=b.cout_f;
neighbours[1].heuristique=b.heuristique;
printf("\nneighbours[%d]=(%d,%d,%d,%d)",1,b.x,b.y,b.cout_f,b.heuristique);
}
if((dx==-1)&&(dy==1)&&(c==1)){
neighbours[2].x=b.x;
neighbours[2].y=b.y;
neighbours[2].cout_f=b.cout_f;
neighbours[2].heuristique=b.heuristique;
printf("\nneighbours[%d]=(%d,%d,%d,%d)",2,b.x,b.y,b.cout_f,b.heuristique);
}
if((dx==0)&&(dy==-1)&&(c==1)){
neighbours[3].x=b.x;
neighbours[3].y=b.y;
neighbours[3].cout_f=b.cout_f;
neighbours[3].heuristique=b.heuristique;
printf("\nneighbours[%d]=(%d,%d,%d,%d)",3,b.x,b.y,b.cout_f,b.heuristique);
}
if((dx==0)&&(dy==0)&&(c==1)){
neighbours[4].x=b.x;
neighbours[4].y=b.y;
neighbours[4].cout_f=b.cout_f;
neighbours[4].heuristique=b.heuristique;
printf("\nneighbours[%d]=(%d,%d,%d,%d)",4,b.x,b.y,b.cout_f,b.heuristique);
}
if((dx==0)&&(dy==1)&&(c==1)){
neighbours[5].x=b.x;
neighbours[5].y=b.y;
neighbours[5].cout_f=b.cout_f;
neighbours[5].heuristique=b.heuristique;
printf("\nneighbours[%d]=(%d,%d,%d,%d)",5,b.x,b.y,b.cout_f,b.heuristique);
}
if((dx==1)&&(dy==-1)&&(c==1)){
neighbours[6].x=b.x;
neighbours[6].y=b.y;
neighbours[6].cout_f=b.cout_f;
neighbours[6].heuristique=b.heuristique;
printf("\nneighbours[%d]=(%d,%d,%d,%d)",6,b.x,b.y,b.cout_f,b.heuristique);
}
if((dx==1)&&(dy==0)&&(c==1)){
neighbours[7].x=b.x;
neighbours[7].y=b.y;
neighbours[7].cout_f=b.cout_f;
neighbours[7].heuristique=b.heuristique;
printf("\nneighbours[%d]=(%d,%d,%d,%d)",7,b.x,b.y,b.cout_f,b.heuristique);
}
if((dx==1)&&(dy==1)&&(c==1)){
neighbours[8].x=b.x;
neighbours[8].y=b.y;
neighbours[8].cout_f=b.cout_f;
neighbours[8].heuristique=b.heuristique;
printf("\nneighbours[%d]=(%d,%d,%d,%d)",8,b.x,b.y,b.cout_f,b.heuristique);
}
}
}
}
for(g=0;g<list_size;g++){
for(a=0;a<neighbours_size;a++){
if((Close_list[g].x == neighbours[a].x && Close_list[g].y == neighbours[a].y && Close_list[g].cout_f == neighbours[a].cout_f && Close_list[g].heuristique == neighbours[a].heuristique)||(Open_list[g].x == neighbours[a].x && Open_list[g].y == neighbours[a].y && Open_list[g].cout_f > neighbours[a].cout_f && Open_list[g].heuristique == neighbours[a].heuristique)){
//Aucune action requise
}
else{ // Calcul du cout_f (nb de fois que le programme a été éffectué) et de l'heuristique (distance entre la position des voisins de la case actuelle est de la destination)
neighbours[a].cout_f = memory[0].cout_f+1;
neighbours[a].heuristique = neighbours[a].cout_f + sqrt(((objective.x-neighbours[a].x)*(objective.x-neighbours[a].x))+((objective.y-neighbours[a].y)*(objective.y-neighbours[a].y)));
//Yes ! I did it !
Open_list[g].x=neighbours[g].x;
Open_list[g].y=neighbours[g].y;
Open_list[g].cout_f=neighbours[g].cout_f;
Open_list[g].heuristique=neighbours[g].heuristique;
}
}
}
printf("\n");
printf("\nCalcul du cout et de l'heuristique :");
printf("\n");
for(a=0;a<neighbours_size;a++){
if(d<9){
printf("\ntrue_memory[%d]=(%d,%d,%d,%d)",a,neighbours[a].x,neighbours[a].y,neighbours[a].cout_f,neighbours[a].heuristique);
d++;
}
}
printf("\n");
printf("\nOn retire les voisins inutiles ainsi que la position actuelle :");
//i=0;
for(i3=0;i3<tab_size;i3++)
{
for(i4=0;i4<tab_size2;i4++)
{
for(k=0;k<denied;k++)
{
for(g=0;g<list_size;g++){ // Je retire les obstacles, dégagez mécréants !
if(graphe[i3][i4]==numbers_denied[k] && Open_list[g].x==tab[i3][i4].x && Open_list[g].y==tab[i3][i4].y)
{
Open_list[g].x=0;
Open_list[g].y=0;
Open_list[g].cout_f=0;
Open_list[g].heuristique=0;
} // Ici je rejete les déplacements en biais, mettez cette condition if en commentaire pour utiliser les déplacements en biais
if((Open_list[g].x==neighbours[0].x && Open_list[g].y==neighbours[0].y && Open_list[g].cout_f==neighbours[0].cout_f && Open_list[g].heuristique==neighbours[0].heuristique)||(Open_list[g].x==neighbours[2].x && Open_list[g].y==neighbours[2].y && Open_list[g].cout_f==neighbours[2].cout_f && Open_list[g].heuristique==neighbours[2].heuristique)||(Open_list[g].x==neighbours[6].x && Open_list[g].y==neighbours[6].y && Open_list[g].cout_f==neighbours[6].cout_f && Open_list[g].heuristique==neighbours[6].heuristique)||(Open_list[g].x==neighbours[8].x && Open_list[g].y==neighbours[8].y && Open_list[g].cout_f==neighbours[8].cout_f && Open_list[g].heuristique==neighbours[8].heuristique))
{
Open_list[g].x=0;
Open_list[g].y=0;
Open_list[g].cout_f=0;
Open_list[g].heuristique=0;
}
}
}
}
}
for(g=0;g<list_size;g++){
if(Open_list[g].x==memory[0].x && Open_list[g].y==memory[0].y)
{
Open_list[g].x=0;
Open_list[g].y=0;
Open_list[g].cout_f=0;
Open_list[g].heuristique=0;
}
}
// Début de la comparaison
x=0;
for(g=0;g<list_size;g++) //On compare l'heursitique de chaque élément retenu pour choisir la prochaine case
{
vecteur[x].x=Open_list[g].x;
vecteur[x].y=Open_list[g].y;
vecteur[x].cout_f=Open_list[g].cout_f;
vecteur[x].heuristique=Open_list[g].heuristique;
x++;
}
n = list_size;
while(n>0)
{
max = vecteur[0].x;
max2 = vecteur[0].y;
max3 = vecteur[0].cout_f;
max4 = vecteur[0].heuristique;
posmax = 0;
for(i=0;i<n;i++)
{
if(vecteur[i].heuristique<max4)
{
max = vecteur[i].x;
max2 = vecteur[i].y;
max3 = vecteur[i].cout_f;
max4 = vecteur[i].heuristique;
posmax = i;
}
}
for(i=posmax;i<n;i++)
{
vecteur[i].x = vecteur[i+1].x;
vecteur[i].y = vecteur[i+1].y;
vecteur[i].cout_f = vecteur[i+1].cout_f;
vecteur[i].heuristique = vecteur[i+1].heuristique;
}
vecteur[n-1].x = max;
vecteur[n-1].y = max2;
vecteur[n-1].cout_f = max3;
vecteur[n-1].heuristique = max4;
n--;
}
x=0;
for(g=0;g<list_size;g++)
{
Open_list[g].x = vecteur[x].x;
Open_list[g].y = vecteur[x].y;
Open_list[g].cout_f = vecteur[x].cout_f;
Open_list[g].heuristique = vecteur[x].heuristique;
x++;
}
printf("\n");
for(g=0;g<list_size;g++)
{
printf("\nOpen_list[%d]=(%d,%d,%d,%d)",g,Open_list[g].x,Open_list[g].y,Open_list[g].cout_f,Open_list[g].heuristique);
}
printf("\n");
printf("\nC'est bien mais ce n'est pas ce qu'on veux !");
printf("\n");
printf("\nVeritable apercu de Open-list apres le tri :");
printf("\n");
x=0;
for(g=0;g<list_size;g++){
vecteur[x].x=Open_list[g].x;
vecteur[x].y=Open_list[g].y;
vecteur[x].cout_f=Open_list[g].cout_f;
vecteur[x].heuristique=Open_list[g].heuristique;
x++;
if((Open_list[g].x!=0)||(Open_list[g].y!=0))
{
n+=1;
}
if((Open_list[g].x==0)&&(Open_list[g].y==0)&&(Open_list[g].cout_f==0)&&(Open_list[g].heuristique==0))
{
n+=0;
}
}
x=0;
while(n>0)
{
max = vecteur[0].x;
max2 = vecteur[0].y;
max3 = vecteur[0].cout_f;
max4 = vecteur[0].heuristique;
posmax = 0;
for(i=0;i<n;i++)
{
if(vecteur[i].heuristique>max4)
{
max = vecteur[i].x;
max2 = vecteur[i].y;
max3 = vecteur[i].cout_f;
max4 = vecteur[i].heuristique;
posmax = i;
}
}
for(i=posmax;i<n;i++)
{
vecteur[i].x = vecteur[i+1].x;
vecteur[i].y = vecteur[i+1].y;
vecteur[i].cout_f = vecteur[i+1].cout_f;
vecteur[i].heuristique = vecteur[i+1].heuristique;
}
vecteur[n-1].x = max;
vecteur[n-1].y = max2;
vecteur[n-1].cout_f = max3;
vecteur[n-1].heuristique = max4;
n--;
}
x=0;
for(g=0;g<list_size;g++){
Open_list[g].x = vecteur[x].x;
Open_list[g].y = vecteur[x].y;
Open_list[g].cout_f = vecteur[x].cout_f;
Open_list[g].heuristique = vecteur[x].heuristique;
x++;
}
// Fin de la comparaison
for(g=0;g<list_size;g++){
printf("\nOpen_list[%d]=(%d,%d,%d,%d)",g,Open_list[g].x,Open_list[g].y,Open_list[g].cout_f,Open_list[g].heuristique);
}
printf("\n");
printf("\nOn ajoute l'ancienne position de l'entite dans Close_list :");
printf("\n");
// Obligatoire, sinon l'entité ne sait pas par où aller
for(g=0;g<list_size;g++){
if(Close_list[g].x==0 && Close_list[g].y==0 && Close_list[g].cout_f==0 && Close_list[g].heuristique==0 && f==0){
Close_list[g].x=neighbours[4].x;
Close_list[g].y=neighbours[4].y;
Close_list[g].cout_f=neighbours[4].cout_f;
Close_list[g].heuristique=neighbours[4].heuristique;
f=1;
}
}
for(g=0;g<list_size;g++){
if(h<list_size){
printf("\nClose_list[%d]=(%d,%d,%d,%d)",g,Close_list[g].x,Close_list[g].y,Close_list[g].cout_f,Close_list[g].heuristique);
h++;
}
}
printf("\n");
printf("\nL'entite n'a pas encore atteint son objectif, on recommence !");
printf("\n");
d=0; // Je réinitialise tout ces paramètres pour relancer plusieurs parties de pathfinding
x=0;
c=0;
f=0;
h=0;
}
return 0;
}
Par contre si jamais mon programme rencontre une intersection avec deux sorties menant à la destination avec le même nombre de cases, il va tourner à l'infini : c'est l'ultime défaut de ce programme, des idées ?
Merci d'avance,
Merci à tous pour les conseils, merci à Potterman28wxcv car sans toi j'allais abandonner
J'ai également un autre petit problème avec ce programme : avec un chemin direct ou avec des intersections, le programme va réussir à trouver le chemin le plus court, cependant si le chemin le plus court est en forme de U, l'entité dans les déplacements sont régis par le pathfinding va tourner en rond car l'une de ses précédentes positions a une valeur heuristique (norme) inférieure à celle des autres, ce qui est foireux...
J'ai bien une idée pour résoudre ce problème : vérifier si dans Open_list et dans Close_list (les listes utilisées pour d'une part enregistrer les déplacements potentiels et d'autre part pour enregistrer le chemin le plus court) si l'un des voisins analysé et déjà présent dans l'une de ces deux listes.
Si tel est le cas alors ce voisin doit être ignoré grâce à ce petit bout de code :
Je ne suis pas en mesure de savoir si ce bout de code fonctionnerait. Tout simplement parce que je ne peux pas relire ton code.
- aucune fonction n'est utilisée. Il y a de la réplication de code dans tous les coins. Difficile donc de savoir si un aspect particulier de ton code marche ou non.
- noms de variables pas du tout explicites. On a du d x c f h, on a du vecteur (ça dit pas grand chose sur ce que représente le vecteur).. les seules variables qui font à peu près du sens c'est open_list et close_list - on sent que c'est deux listes qui ont un rôle particulier mais quoi ? Et pourquoi elles commencent par une majuscule ? La variable neighbour par contre c'est a peu près clair à quoi ça correspond.
- tu t'es inspiré d'un pseudo code disponible sur wiki si je me rappelle bien, mais ce pseudo code n'apparaît nulle part dans ton code. Aucun moyen de savoir qu'est ce qui correspond à quoi - on ne sait même pas quelles sont les entrées (données d'entrées) et les sorties (données de sortie) de ton code. Difficile donc de savoir si ton code est bon ou pas.
Si tu veux que des gens comprennent ce que tu as écrit tu as tout intérêt à découper ça en plus petites fonctions élémentaires - sûrement que ça te fera aussi voir les choses d'une différente manière et te permettra d'identifier les bugs que tu as en refactorisant ton code.
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html
Bonhomme !! | Jeu de plateforme : Prototype.