Partage
  • Partager sur Facebook
  • Partager sur Twitter

Faire un pathfinding

    10 juin 2019 à 19:19:38

    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.

    • Partager sur Facebook
    • Partager sur Twitter
      10 juin 2019 à 19:54:14

      Salut !

      Si tu veux des mots clés :

      Un algo de pot de peinture avec une exploration en largeur te donnera un bon chemin. 

      • Partager sur Facebook
      • Partager sur Twitter

      Recueil de codes en C et C++ http://fvirtman.free.fr/recueil/index.html

        12 juin 2019 à 16:42:20

        Bonjour Fvirtman,

        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 ?

        • Partager sur Facebook
        • Partager sur Twitter
          12 juin 2019 à 17:25:34

          Salut,

          Tu peux aller voir du côté de Astar (A*).

          Le pot de peinture s'appelle le "remplissage par diffusion".

          Bonne continuation.

          • Partager sur Facebook
          • Partager sur Twitter

          Stringman | Jeux de plateforme : Nouvelle Démo. (màj : 20 Juillet 2019)

            12 juin 2019 à 20:11:40

            Merci drx,

            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).

            Une idée de comment procéder ?

            • Partager sur Facebook
            • Partager sur Twitter
              13 juin 2019 à 10:24:27

              Tu peux compter le nombre d'appui sur une flèche et ne rien faire si le nombre de flèches appuyé est supérieur ou égal à 2.

              (en supposant que haut/bas/droite/gauche est déclenché par les touches fléchées du clavier, mais le raisonnement marche aussi avec d'autres touches)

              -
              Edité par potterman28wxcv 13 juin 2019 à 10:25:18

              • Partager sur Facebook
              • Partager sur Twitter
                24 juin 2019 à 22:19:57

                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

                • Partager sur Facebook
                • Partager sur Twitter
                  24 juin 2019 à 23:30:17

                  Est-ce que tu pourrais poster ton code avec la balise de l'éditeur de post </> stp ?
                  • Partager sur Facebook
                  • Partager sur Twitter
                    26 juin 2019 à 19:35:50

                    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

                    • Partager sur Facebook
                    • Partager sur Twitter
                      26 juin 2019 à 23:22:25

                      Hello,

                      Désolé :p 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).

                              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;
                              }

                      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 :p 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

                      • Partager sur Facebook
                      • Partager sur Twitter
                        29 juin 2019 à 20:34:58

                        Bonjour potterman28wxcv,

                        Le code suivant :

                        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.

                        Merci d'avance ^^

                        • Partager sur Facebook
                        • Partager sur Twitter
                          12 juillet 2019 à 16:16:45

                          Bonjour tout le monde,

                          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 ?

                          Voici la fonction :

                          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 numbers_denied[denied]={0,2,3,4,5,6,7,8,9,10,11,13,14,15,25,26,27,28,29,32,33,38,39,40,41,44,45,48,49,50,51,52,53,54,55,60,61,62,63,64,65,66,68,69,70,72,73};
                          
                          void Shortest_path_to_destination(unsigned int graphe[tab_size][tab_size2],noeud objective,noeud departure,SDL_Rect * entity)
                          {
                          	noeud tab[tab_size][tab_size2]={0};
                          	noeud Open_list[list_size]={0};
                          	noeud Close_list[list_size]={0};
                          	noeud memory[1]={0};
                          	noeud neighbours[neighbours_size]={0};
                          	noeud b={0};
                          	int i1,i2;
                          	int g,p,e,a,c,d,f,h,i,j,i3,i4,k;
                          	int dx,dy;
                          	int x=0;
                          	int n=0;
                          	int max1,max2,max3,max4;
                            	int posmax;
                            	int fin=0;
                          	g=0;
                          	p=0;
                          	e=0;
                          	dx=0;
                          	dy=0;
                          	a=0;
                          	c=0;
                          	d=0;
                          	f=0;
                          	h=0;
                          	i=0;
                          	j=0;
                          	noeud vecteur[100]={0};
                          	//Ajout de départ à Open_list
                          	for(i1=0;i1<tab_size;i1++)
                          	{
                          		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++)
                          	{
                          		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=departure.x;
                          			Open_list[g].y=departure.y;
                          			Open_list[g].cout_f=departure.cout_f;
                          			Open_list[g].heuristique=departure.heuristique;
                          			p=1;
                          		}
                          	}
                          	//Mémoire pour retenir le premier élément de Open_list
                          	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);
                          	while((memory[0].x!=objective.x)||(memory[0].y!=objective.y)&&(fin==0))
                          	{
                          		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;
                          		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))
                          		{
                          		    entity->x=memory[0].x;
                          		    entity->y=memory[0].y;
                          		    for(g=0;g<list_size;g++)
                                      {
                                          Open_list[g].x=0;
                                          Open_list[g].y=0;
                                          Open_list[g].cout_f=0;
                                          Open_list[g].heuristique=0;
                                          Close_list[g].x=0;
                                          Close_list[g].y=0;
                                          Close_list[g].cout_f=0;
                                          Close_list[g].heuristique=0;
                                      }
                          			//reconstituer le chemin
                          			fin=1;
                          			//return 1;
                          		}
                          		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;
                          	                //printf("\n(%d,%d,%d,%d)",b.x,b.y,b.cout_f,b.heuristique);
                          	                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;
                          			        }
                          			        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;
                          			        }
                          			        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;
                          			        }
                          			        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;
                          			        }
                          			        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;
                          			        }
                          			        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;
                          			        }
                          			        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;
                          			        }
                          			        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;
                          			        }
                          			        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;
                          			        }
                          	            }
                          	        }
                              	}
                              	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{
                          	        		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 !
                          	        		i=0;
                          	        		if(Open_list[g].x!=0 || Open_list[g].y!=0 || Open_list[g].cout_f!=0 || Open_list[g].heuristique!=0){
                          						i+=1;
                          					}
                          					if(Open_list[g].x==0 && Open_list[g].y==0 && Open_list[g].cout_f==0 && Open_list[g].heuristique==0 && j<neighbours_size){
                          						Open_list[g].x=neighbours[g-i].x;
                          						Open_list[g].y=neighbours[g-i].y;
                          						Open_list[g].cout_f=neighbours[g-i].cout_f;
                          						Open_list[g].heuristique=neighbours[g-i].heuristique;
                          						j++;
                          					}
                          					//Il ne faut pas oublier de retirer neighbours[4]
                          	        	}
                          	        }
                              	}
                              	for(a=0;a<neighbours_size;a++){
                              		if(d<9){
                              			d++;
                              		}
                              	}
                              	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++){
                          						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;
                          						}
                          						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;
                          			}
                          		}
                          		x=0;
                          	  	for(g=0;g<list_size;g++)          //On veut remplir la case i du tableau
                          	    {
                          	    	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)
                          		{
                          			max1 = 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)
                          				{
                          					max1 = 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 = max1;
                          			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++;
                          		}
                          		x=0;
                          	  	for(g=0;g<list_size;g++){         //On veut remplir la case i du tableau
                          	    	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)
                          		{
                          			max1 = 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)
                          				{
                          					max1 = 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 = max1;
                          			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++;
                          		}
                              	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){
                              			h++;
                              		}
                              	}
                          		d=0;
                          		x=0;
                          		c=0;
                          		f=0;
                          		h=0;
                          		i=0;
                          		j=0;
                          		g=0;
                          		n=0;
                          		k=0;
                          		a=0;
                          		i1=0;
                          		i2=0;
                          		i3=0;
                          		i4=0;
                          		dx=0;
                          		dy=0;
                          		max1=0;
                          		max2=0;
                          		max3=0;
                          		max4=0;
                          		posmax=0;
                          	}
                          	//return -1;
                          	return 0;
                          }

                          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

                          • Partager sur Facebook
                          • Partager sur Twitter
                            12 juillet 2019 à 19:24:30

                            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 :)

                            • Partager sur Facebook
                            • Partager sur Twitter

                            Faire un pathfinding

                            × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                            • Editeur
                            • Markdown