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 : 16 Juin 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
                Il y a environ 11 heures

                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 il y a environ 10 heures

                • Partager sur Facebook
                • Partager sur Twitter
                  Il y a environ 10 heures

                  Est-ce que tu pourrais poster ton code avec la balise de l'éditeur de post </> stp ?
                  • 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