Posez votre question Signaler

Pathfinding (mode débutant) qui fonctionne mais... [Résolu]

Messages postés
16
Date d'inscription
lundi 20 octobre 2008
Statut
Membre
Dernière intervention
30 août 2011
 - - Dernière réponse : eustatika
Messages postés
16
Date d'inscription
lundi 20 octobre 2008
Statut
Membre
Dernière intervention
30 août 2011
 - 30 août 2011 à 16:16
C Posez votre question Signaler
Bonjour,

je suis en train d'améliorer la source que j'avais précédement posté (Sokoban pour débutant) et j'espère pouvoir la mettre à jour rapidement (pour info, vu les "pas de commentaire" que ça a suscité, je me suis dis qu'elle devait être totalement imbuvable donc ça fait une semaine que je restructure ma source et la recommente "intelligemment").

Enfin je vais pas vous raconter ma vie.
Le problème que je rencontre est que j'ai intégré un pathfinding pour déplacer le joueur au clique.
Je doute forts qu'il soit vraiment optimisé (en terme de calcule) mais il fonctionne. C'est un algo fait maison (le défi que je me suis lancé) et non une implémentation d'un algo que je connaissait donc il est fort possible que j'ai fait des erreurs

Par contre, il n'arrive pas à trouver le chemin le plus court dans certains cas (ça fait 24h que j'essaie de déterminé lesquels)
ex :


Juste pour info : je n'ai fait aucun 'free' pour le moment, je verrai ça à la fin.


Voici le code complet du pathfinding : 

#include <stdio.h>
#include <stdlib.h>
#include "pathfinding.h"

typedef struct sPosition
{    short x; /**< X-coordinate value  */
    short y; /**< Y-coordinate value  */
} sPOSITION;

typedef struct s_dlNode s_dlNode  ;
struct s_dlNode
    {
   struct sPosition NodeValue; /**< s_Level structure that contains a level data data */
    int depth ;
    struct s_dlNode* nxtL; /**< Pointer to next level LEFT */
    struct s_dlNode* nxtR; /**< Pointer to next level RIGHT */
    struct s_dlNode* nxtB; /**< Pointer to next level BOTTOM*/
    struct s_dlNode* nxtT; /**< Pointer to next level TOP */
    struct s_dlNode* prev; /**< Pointer to the previous node   */
    struct s_dlNode* direct  ; /**< Pointer to the direct node (assigned when optimal path is found)*/
    int direction ; /**Player move direction to go to the next cell of the optimal path (the function i use to move player need this)*/

    };
typedef  s_dlNode* sPtr_dlTree;

int forbiddenTable[NB_TOTAL_BLOCS]= {0} ; //Stock le numéro des cellules interdites
struct s_dlNode *tab_goodsPath[100] ; //Stock les noeuds terminaux correpondants à la position d'arrivée
int numberOfGoodPath ; //Compte le nombre d'éléments ajoutée a 'tab_goodsPath'
struct sPosition postarget ; //Position de la cible
 struct sPosition posinit ; //Position du joueur


/**Réinitialise la tableau des cellules interdites*/
void reinitForbidTable(void)
{
     int i ;
     for(i=0 ; i<NB_TOTAL_BLOCS ; i++)
     {
          forbiddenTable[i]=0 ;
     }
}

/**Ajoute un noeud terminal au tableau des noeux répondants au critère de recherche*/
void addGoodPath(s_dlNode* goodpath)
{
     tab_goodsPath[numberOfGoodPath]=goodpath ;
     numberOfGoodPath++ ;
}


/**Fonction appelée récursivement : Parcours de la map à la recherche des chemins*/
void buildTree(struct s_dlNode* node, int fromDirection, int grid[][NB_BLOCS_HEIGHT])
{
     int i ;
     printf("Level : %d\n", node->depth);
     int x= node->NodeValue.x;
     int y= node->NodeValue.y;
     /**Si l'on a atteint la cible, on sort de la fonction*/
     if(postarget.x x && postarget.yy)
     {
          printf("\nPath added with depth %d at address %d\n\n", node->depth,node);
          addGoodPath(node) ;
          return;
     }
     /**Sinon, on ajoute la cellule actuelle aux cellules interdites*/
     forbiddenTable[x*NB_BLOCS_HEIGHT +y] =1;
     for(i=0; i<4; i++)
     {
          switch(i)
          {
          case LEFT :
               /**Pour chaque direction, on vérifie que :
                   L'on ne sort pas des limites de la map
                   Que la cellule cible est de type EMPTY ou TARGET (Les autre types étant CRATE, TARGETOK et WALL)
                   Que la direction courante ne ramène pas à la position précédente
                   Que la cellule cible ne fait pas partie des cellules interdites
                    */
               printf("Case left \n") ;
               if(((NB_BLOCS_HEIGHT*(x-1)+y)>=0) &&
                         ((grid[x-1][y]==EMPTY)||(grid[x-1][y]==TARGET)) &&
                         fromDirection!=i &&
                         !(forbiddenTable[(x-1)*NB_BLOCS_HEIGHT +y]))
               {
                    printf("Déplacement gauche possible depuis la position : x=%d  y=%d \n\n", x, y) ;
                    struct s_dlNode* child =(s_dlNode*) malloc(sizeof(s_dlNode)) ;
                    child->nxtB=NULL ;
                    child->nxtL=NULL;
                    child->nxtR=NULL;
                    child->nxtT=NULL;
                    child->depth = node->depth+1 ; /**Incrément de la profondeur de m'enfant */
                    child->NodeValue.x= node->NodeValue.x-1 ;
                    child->NodeValue.y =node->NodeValue.y ;
                    child->prev= node ;
                    child->direct=NULL ;
                    /**Previous node*/
                    node->nxtL=child ;
                    buildTree(child, RIGHT, grid); /**Recurs*/
               }
               else
               {
                    node->nxtL=NULL ;
               }
               break ;
          case RIGHT :
               printf("Case right \n") ;
               if(((NB_BLOCS_HEIGHT*(x+1)+y)<NB_TOTAL_BLOCS) &&
                         ((grid[x+1][y]==EMPTY)|| (grid[x+1][y]==TARGET)) &&
                         fromDirection!=i &&
                         !(forbiddenTable[(x+1)*NB_BLOCS_HEIGHT +y]))
               {
                    printf("Déplacement droit possible :\n De : x=%d  y=%d \n\n", x, y) ;
                    struct s_dlNode* child =(s_dlNode*) malloc(sizeof(s_dlNode)) ;
                    child->nxtB=NULL ;
                    child->nxtL=NULL;
                    child->nxtR=NULL;
                    child->nxtT=NULL;
                    child->depth = node->depth+1 ;
                    child->NodeValue.x= node->NodeValue.x+1 ;
                    child->NodeValue.y =node->NodeValue.y ;
                    child->prev= node ;
                    child->direct=NULL ;
                    /**Previous node*/
                    node->nxtR=child ;
                    buildTree(child, LEFT,  grid);
               }
               else
               {
                    node->nxtL=NULL ;
               }
               break ;
          case TOP :
               printf("Case top \n") ;
               if(((NB_BLOCS_HEIGHT*x+y-1)>=0) &&
                         ((grid[x][y-1]==EMPTY)||(grid[x][y-1]==TARGET)) &&
                         fromDirection!=i &&
                         !(forbiddenTable[x*NB_BLOCS_HEIGHT +y-1]))
               {
                    printf("Déplacement haut possible :\n De : x=%d  y=%d \n\n", x, y) ;
                    struct s_dlNode* child =(s_dlNode*) malloc(sizeof(s_dlNode)) ;
                    child->nxtB=NULL ;
                    child->nxtL=NULL;
                    child->nxtR=NULL;
                    child->nxtT=NULL;
                    child->depth = node->depth+1 ;
                    child->NodeValue.x= node->NodeValue.x ;
                    child->NodeValue.y =node->NodeValue.y-1 ;
                    child->prev= node ;
                    child->direct=NULL ;
                    /**Previous node*/
                    node->nxtT=child ;
                    buildTree(child, BOTTOM, grid);
               }
               else
               {
                    node->nxtT=NULL ;
               }
               break ;
          case BOTTOM:
               printf("Case bottom \n") ;
               if(((NB_BLOCS_HEIGHT*x+y+1)<NB_TOTAL_BLOCS) &&
                         ((grid[x][y+1]==EMPTY)||(grid[x][y+1]==TARGET)) &&
                         fromDirection!=i &&
                         !(forbiddenTable[x*NB_BLOCS_HEIGHT +y+1]))
               {
                    printf("Déplacement bas possible :\n De : x=%d  y=%d \n\n", x, y) ;
                    struct s_dlNode* child =(s_dlNode*) malloc(sizeof(s_dlNode)) ;
                    child->nxtB=NULL ;
                    child->nxtL=NULL;
                    child->nxtR=NULL;
                    child->nxtT=NULL;
                    child->depth = node->depth+1 ;
                    child->NodeValue.x= node->NodeValue.x ;
                    child->NodeValue.y =node->NodeValue.y+1 ;
                    child->prev= node ;
                    child->direct=NULL ;
                    /**Previous node*/
                    node->nxtB=child ;
                    buildTree(child, TOP ,  grid);
               }
               else
               {
                    node->nxtB=NULL ;
               }
               break ;
          }
     }
     printf("\n\n END \n\n") ;
}




char* directionString(int dirInt)
{
     switch(dirInt)
     {
     case LEFT :
          return "LEFT" ;
          break ;
     case RIGHT :
          return "RIGHT" ;
          break ;
     case TOP :
          return "TOP" ;
          break ;
     case BOTTOM :
          return "BOTTOM" ;
          break ;
     }
}


s_dlNode* findPathToTargetPos(int grid[][NB_BLOCS_HEIGHT], int targetX, int targetY, int playerX, int playerY)
{
     int i,j ;

     /**Initialisations*/
     numberOfGoodPath =0 ;
     for(i=0 ; i<NB_TOTAL_BLOCS ; i++)
     {
          tab_goodsPath[i]=NULL ;
     }
     reinitForbidTable() ;
     posinit.x=playerX ;
     posinit.y=playerY ;
     postarget.x=targetX ;
     postarget.y=targetY ;

/**Création du noeud racine*/
     sPtr_dlTree root=(s_dlNode*)malloc(sizeof(s_dlNode));
     root->NodeValue=posinit ;
     root->depth=0 ;
     root->nxtB=NULL ;
     root->nxtL=NULL;
     root->nxtR=NULL;
     root->nxtT=NULL;
     root->prev=NULL;
     root->direct=NULL ;


     printf("Build tree\n", i, j);
     buildTree(root, TOP, grid) ;
     reinitForbidTable() ;
     buildTree(root, LEFT, grid) ;
     reinitForbidTable() ;
     buildTree(root, RIGHT, grid) ;
     reinitForbidTable() ;
     buildTree(root, BOTTOM, grid) ;
     reinitForbidTable() ;
     printf("Calculation done !\n ") ;
     s_dlNode* finalpath ;

     /**Si l'on n'a rien trouvé, on sort et on retourne NULL*/
     if(!numberOfGoodPath)
     {
          return NULL ;
     }

     /**Sinon on recherche la noeud ayant la profondeur la plus faible dans les noeuds valides*/
     for(i=0; i<=numberOfGoodPath ; i++)
     {
          if(i==0)
          {
               finalpath=tab_goodsPath[i];
          }
          if(tab_goodsPath[i+1]!=NULL)
          {
               if(tab_goodsPath[i+1]->depth <finalpath->depth)
               {
                    finalpath =tab_goodsPath[i+1] ;
               }
          }
     }
     printf("Best path depth : %d\n", finalpath->depth) ;
 /**On remonte jusqu'au noeud racine tout en indiquant quel direction prendre pour aller de la cellule précédent à celle en cours*/
     while(finalpath->prev!=NULL)
     {
          if(finalpath->NodeValue.x ==finalpath->prev->NodeValue.x+1)
          {
               finalpath->prev->direction = RIGHT ;
          }
          else if(finalpath->NodeValue.x ==finalpath->prev->NodeValue.x-1)
          {
               finalpath->prev->direction = LEFT ;
          }
          else if(finalpath->NodeValue.y ==finalpath->prev->NodeValue.y+1)
          {
               finalpath->prev->direction = BOTTOM ;
          }
          else if(finalpath->NodeValue.y ==finalpath->prev->NodeValue.y-1)
          {
               finalpath->prev->direction = TOP ;
          }


          finalpath->prev->direct= finalpath ;
          finalpath= finalpath->prev ;
              }

     return finalpath ;
}


Si quelqu'un a une suggestion, ça serait magnifique car là je sèche .

Bonne journées à tous.

PS : Si par ailleurs, sait-on jamais, la source vous intéresse, faites en ce que vous voulez.
Afficher la suite 

Votre réponse

Répondre au sujet

10 réponses

Meilleure réponse
Signaler Commenter la réponse de cptpingu
Messages postés
3835
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
5 mai 2019
 167
3
Merci
pour info, vu les "pas de commentaire" que ça a suscité, je me suis dis qu'elle devait être totalement imbuvable donc ça fait une semaine que je restructure ma source et la recommente "intelligemment"

Pas de déduction hâtive ! Tu as tout de même 1029 vus et 70 téléchargements. C'est simplement que ce site est dédié aux débutants, qui vont se servir de ton code et ne vont pas forcément oser le critiquer. Pour faire une critique de code, il faut déjà avoir un minimum d'expérience.

j'ai intégré un pathfinding pour déplacer le joueur au clique

C'est une très bonne idée, qui apportera une vraie plus-value au projet de base.


La méthode que tu utilises s'appelle le backtracking. C'est une bonne méthode, c'est une bonne intuition de l'avoir choisie.
En revanche, au niveau de l'implémentation, tu te prends un peu trop la tête. Pourquoi vouloir stocker tous les chemins ? Au final ce qui t'intéresse c'est d'aller d'un point A vers un point B ? Si ce n'est que le 2ème ou 3ème meilleur chemin, est-ce vraiment grave ? A ton avis est-ce qu'il vaut mieux trouver le 3ème meilleur chemin en 1 sec ou trouver LE meilleur chemin en 5 secondes ? (Exemples extrêmes et pas tout à fait vrai).
A ta place, je ne garderais qu'un seul chemin et je profiterais à fond de la récursion pour copier automatiquement tout ce dont j'ai besoin. Avec une pile par exemple.

Au niveau du code, je n'ai pas compris pourquoi tu as une liste chaînée aussi compliquée.
Un tableau à double dimension (ou encore mieux un tableau simple avec la technique que tu utilises pour forbiddenTable) est largement suffisant. En plus ta grille ne change pas de taille en cours de jeu, c'est d'autant plus facile à gérer. Tu ne devrais pas avoir de liste chaînées (sauf si tu veux recoder une pile avec, pour stocker le meilleur chemin (uniquement un tableau de sPosition), mais ce n'est pas forcé).

Au niveau du code, il y a beaucoup de redondance de code que tu pourrais éviter. Par exemple dans switch...case, tu pourrais créer une fonction au lieu de recopier dans chaque case quasiment la même chose.

Enfin, pour ton bug, la comme ça, c'est pas facile de te répondre. Envoie moi ton code par mp, que je passe un coup de gdb dessus. Ça ira plus vite :p Ou alors passe un petit coup de gdb toi même (ça aide !).

________________________________________________________________________
Historique de mes créations, et quelques articles:
[ http://0217021.free.fr/portfolio http://0217021.free.fr/portfolio]
Merci d'utiliser Réponse acceptée si un post répond à votre question

Dire « Merci » 3

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

Codes Sources 139 internautes nous ont dit merci ce mois-ci

Commenter la réponse de cptpingu
Signaler Commenter la réponse de cptpingu
Messages postés
3835
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
5 mai 2019
 167
3
Merci
Félicitations pour ta correction.

Pour ceux que ça intéresse, voici le code qui permet de trouver le chemin le plus court dans un labyrinthe 2D

Merci d'avoir mis à jour tes avancées sur ce forum. Rares sont ceux qui ont la politesse de le faire.

Je dois le reprendre de 0 pour l'optimiser car on m'a fait remarquer que c'était un peu tortueux

Ce n'est pas vraiment tortueux, c'est juste un code peu robuste en l'état (bien que fonctionnel). Il y a juste deux choses qu'il faut que tu fasses:
- Suppression de toutes les variables globales.
- Factorisation du code redondant en fonctions. Éviter qu'une fonction dépasse une trentaine de ligne.

________________________________________________________________________
Historique de mes créations, et quelques articles:
[ http://0217021.free.fr/portfolio http://0217021.free.fr/portfolio]
Merci d'utiliser Réponse acceptée si un post répond à votre question

Dire « Merci » 3

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

Codes Sources 139 internautes nous ont dit merci ce mois-ci

Commenter la réponse de cptpingu
Signaler Commenter la réponse de eustatika
Messages postés
16
Date d'inscription
lundi 20 octobre 2008
Statut
Membre
Dernière intervention
30 août 2011
0
Merci
Juste au cas où, le pathfinding.h ne vous sera pas utile, il y avait la déclaration des structures que j'ai mis en haut du .c.
Voilà également un exemple de mon utilisation de cette fonction : 
 s_dlNode* ret =NULL ;
ret=findPathToTargetPos(grid, mouseX, mouseY, posPlayer.x , posPlayer.y) ;
 while(ret->direct !=NULL)
{
  movePlayer(grid, &posPlayer,ret->direction) ;
//ICI la fonction de mAj d l'affichage
Sleep(10) ; 
ret = ret->direct ; 

}
Commenter la réponse de eustatika
Signaler Commenter la réponse de eustatika
Messages postés
16
Date d'inscription
lundi 20 octobre 2008
Statut
Membre
Dernière intervention
30 août 2011
0
Merci
En fait, j'ai été un peu lourd au niveau du code car :
- Je débute mais ça tu le sais déjà ^^
- Il faut que je trouve le chemin le plus direct car le jeux intègre un compteur de mouvement et enregistre les records. Si le déplacement au clique augmente le nombre de déplacements inutilement, ça risque de pas avoir de succès ^^.
- J'ai conservé tous les chemins trouvé juste pour pouvoir les analyser et comprendre un peu mieux à quelle moment ça twist.
- J'ai utilisé des listes chaines car... je viens de les découvrir et je trouve ça sexy . Après, j'ai pas beaucoup réfléchi avant de m'ezn servir.

Par contre, le jeu que j'ai posté en source utilisait un tableau pour stocker les niveaux.
Là je suis passé à la liste chainée et j'ai beaucoup apprécié la facilité/rapidité de suppression d'éléments en mileu de liste

Enfin, si en effet tu as le temps de regarder, je dis pas non. J'ai déjà passé un coup de gdb mais j'avoue que, les fonctions récursives, j'ai parfois du mal à les débuger. Mais je comprends bien qu'il faut que je reprenne tout ça et que je l'épure.
Ca me donnera peut-être un indice.

Tu veux j'envoie tout le code?

Merci en tout cas pour ta réponse (toujours aussi rapide :-))
Commenter la réponse de eustatika
Signaler Commenter la réponse de cptpingu
Messages postés
3835
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
5 mai 2019
 167
0
Merci
- Je débute mais ça tu le sais déjà ^^

Ce n'est pas un mal, on a tous commencé un jour. C'est en faisant des erreurs que l'on apprend (pas d'erreurs, pas d'apprentissage).

- Il faut que je trouve le chemin le plus direct car le jeux intègre un compteur de mouvement et enregistre les records. Si le déplacement au clique augmente le nombre de déplacements inutilement, ça risque de pas avoir de succès ^^.

Je n'avais pas cette notion en tête. Dans ce cas, oui tu as raison.

- J'ai conservé tous les chemins trouvé juste pour pouvoir les analyser et comprendre un peu mieux à quelle moment ça twist.

Pour avoir le meilleur chemins, tu peux juste garder le meilleur des chemins, à chaque fois que tu en trouves un. Pas besoin de tous garder. Pour du débug, je comprends néanmoins ta démarche.

- J'ai utilisé des listes chaines car... je viens de les découvrir et je trouve ça sexy . Après, j'ai pas beaucoup réfléchi avant de m'ezn servir.

C'est vrai que c'est sexy, mais attention à utiliser le bon outil dans la bonne situation. Une perceuse c'est sexy, mais rien ne vaut un bon marteau pour taper sur un clou :p

Là je suis passé à la liste chainée et j'ai beaucoup apprécié la facilité/rapidité de suppression d'éléments en mileu de liste

Dans ta grille de taille fixe, as-tu besoin de supprimer/insérer souvent en milieu de liste ? ;)

Mais je comprends bien qu'il faut que je reprenne tout ça et que je l'épure.

Je t'invite à d'abord regarder par toi même. Je te donnerais un coup de main si tu es toujours bloqué.

________________________________________________________________________
Historique de mes créations, et quelques articles:
[ http://0217021.free.fr/portfolio http://0217021.free.fr/portfolio]
Merci d'utiliser Réponse acceptée si un post répond à votre question
Commenter la réponse de cptpingu
Signaler Commenter la réponse de eustatika
Messages postés
16
Date d'inscription
lundi 20 octobre 2008
Statut
Membre
Dernière intervention
30 août 2011
0
Merci
Merci pour tout ces conseils.
Pour répondre à la question :
Dans ta grille de taille fixe, as-tu besoin de supprimer/insérer souvent en milieu de liste ? ;)


C'est là que je charge les niveau du jeu depuis le fichier lvl, ensuite on peut ajouter/supprimer/modifier les niveaux.
J'imagine que pour charger un niveau, c'est plus lourd à l'exécution de se taper les pointeurs les une après les autres mais pour la suppression de niveau c'est vraiment moins lourds. Et surtout, mon code a fait un petit régime minceur.

En plus, ça ne prends que ce qu'il faut de place. Au début, j'avais bridé le nombre de niveaux à 255.
Du coup, si un courageux veut créer une campagne de 10 000 niveaux, son seul souci sera son espérance de vie

Allez, je m'y mets.
Thanks
Commenter la réponse de eustatika
Signaler Commenter la réponse de eustatika
Messages postés
16
Date d'inscription
lundi 20 octobre 2008
Statut
Membre
Dernière intervention
30 août 2011
0
Merci
Bonsoir, grâce à CptPingu, j'ai pu me sortir de ce mauvais pas.
Il fallait en fait que je libère l'accès à la cellule à chaque sortie de la fonction récursive.

Pour ceux que ça intéresse, voici le code qui permet de trouver le chemin le plus court dans un labyrinthe 2D (enfin, c'est que qu'il me semble jusqu'à présent).
Je dois le reprendre de 0 pour l'optimiser car on m'a fait remarquer que c'était un peu tortueux. Mais bon, ça marche et quand j'aurais revu tout ça, je le posterai. 

#include <stdio.h>
#include <stdlib.h>
typedef enum eDirection
{
     TOP,
     BOTTOM,
     LEFT,
     RIGHT
}eDirection;

/*!struct sPosition
@brief Define 2D coordinates of a point
*/
typedef struct sPosition
{    short x; /**< X-coordinate value  */
    short y; /**< Y-coordinate value  */
} sPOSITION;

typedef struct s_dlNode s_dlNode  ;
struct s_dlNode
    {
   struct sPosition NodeValue; /**< s_Level structure that contains a level data data */
    int depth ;
    struct s_dlNode* nxtL; /**< Pointer to next left cell node  */
    struct s_dlNode* nxtR; /**< Pointer to next right cell node */
    struct s_dlNode* nxtB; /**< Pointer to next bottom cell node */
    struct s_dlNode* nxtT; /**< Pointer to next top cell node */
    struct s_dlNode* prev; /**< Pointer to previous node */
    struct s_dlNode* direct /**< Pointer next node (in shortest path) */ ;
    eDirection direction /**< Direction to "direct" node  */ ;

    };
typedef  s_dlNode* sPtr_dlTree;

int forbiddenTable[NB_TOTAL_BLOCS]= {0} ; //Stock le numéro des cellules interdites
struct s_dlNode *tab_goodsPath[1000] ; //Stock les noeuds terminaux correpondants à la position d'arrivée
int numberOfGoodPath ; //Compte le nombre d'éléments ajoutée a 'tab_goodsPath'
struct sPosition postarget ; //Position de la cible
 struct sPosition posinit ; //Position du joueur
 int foundIndex ;


/**Réinitialise la tableau des cellules interdites*/
void reinitForbidTable(void)
{
     int i ;
     for(i=0 ; i<NB_TOTAL_BLOCS ; i++)
     {
          forbiddenTable[i]=0 ;
     }
}

/**Ajoute un noeud terminal au tableau des noeux répondants au critère de recherche*/
void addGoodPath(s_dlNode* goodpath)
{
     tab_goodsPath[numberOfGoodPath]=goodpath ;
     numberOfGoodPath++ ;
}


/**Fonction appelée récursivement : Parcours de la map à la recherche des chemins*/
void buildTree(struct s_dlNode* node, eDirection fromDirection, int grid[][NB_BLOCS_HEIGHT])
{
     int i ;
     printf("Level : %d\n", node->depth);
     int x= node->NodeValue.x;
     int y= node->NodeValue.y;
     /**Si l'on a atteint la cible, on sort de la fonction*/


     if(postarget.x x && postarget.yy)
     {
          printf("\nPath added with depth %d \n\n", node->depth);
   
          addGoodPath(node) ;


          return;
     }
      
     /**Sinon, on ajoute la cellule actuelle aux cellules interdites*/
         printf("Adding %d %d to forbidden table\n", x, y);
     forbiddenTable[x*NB_BLOCS_HEIGHT +y] =1;
     for(i=0; i<4; i++)
     {
          switch(i)
          {
          case LEFT :
               /**Pour chaque direction, on vérifie que :
                   L'on ne sort pas des limites de la map
                   Que la cellule cible est de type EMPTY ou TARGET (Les autre types étant CRATE, TARGETOK et WALL)
                   Que la direction courante ne ramène pas à la position précédente
                   Que la cellule cible ne fait pas partie des cellules interdites
                    */
               printf("Case left \n") ;
               if(((NB_BLOCS_HEIGHT*(x-1)+y)>=0) &&
                         ((grid[x-1][y]==EMPTY)||(grid[x-1][y]==TARGET)) &&
                         fromDirection!=i &&
                         !(forbiddenTable[(x-1)*NB_BLOCS_HEIGHT +y]))
               {
                    printf("Déplacement gauche possible depuis la position : x=%d  y=%d \n\n", x, y) ;
                    struct s_dlNode* child =(s_dlNode*) malloc(sizeof(s_dlNode)) ;
                    child->nxtB=NULL ;
                    child->nxtL=NULL;
                    child->nxtR=NULL;
                    child->nxtT=NULL;
                    child->depth = node->depth+1 ; /**Incrément de la profondeur de m'enfant */
                    child->NodeValue.x= node->NodeValue.x-1 ;
                    child->NodeValue.y =node->NodeValue.y ;
                    child->prev= node ;
                    child->direct=NULL ;
                    /**Previous node*/
                    node->nxtL=child ;
                    buildTree(child, RIGHT, grid); /**Recurs*/
               }
               else
               {
                    node->nxtL=NULL ;
               }
               break ;
          case RIGHT :
               printf("Case right \n") ;
               if(((NB_BLOCS_HEIGHT*(x+1)+y)<NB_TOTAL_BLOCS) &&
                         ((grid[x+1][y]==EMPTY)|| (grid[x+1][y]==TARGET)) &&
                         fromDirection!=i &&
                         !(forbiddenTable[(x+1)*NB_BLOCS_HEIGHT +y]))
               {
                    printf("Déplacement droit possible :\n De : x=%d  y=%d \n\n", x, y) ;
                    struct s_dlNode* child =(s_dlNode*) malloc(sizeof(s_dlNode)) ;
                    child->nxtB=NULL ;
                    child->nxtL=NULL;
                    child->nxtR=NULL;
                    child->nxtT=NULL;
                    child->depth = node->depth+1 ;
                    child->NodeValue.x= node->NodeValue.x+1 ;
                    child->NodeValue.y =node->NodeValue.y ;
                    child->prev= node ;
                    child->direct=NULL ;
                    /**Previous node*/
                    node->nxtR=child ;
                    buildTree(child, LEFT,  grid);
               }
               else
               {
                    node->nxtL=NULL ;
               }
               break ;
          case TOP :
               printf("Case top \n") ;
               if(((NB_BLOCS_HEIGHT*x+y-1)>=0) &&
                         ((grid[x][y-1]==EMPTY)||(grid[x][y-1]==TARGET)) &&
                         fromDirection!=i &&
                         !(forbiddenTable[x*NB_BLOCS_HEIGHT +y-1]))
               {
                    printf("Déplacement haut possible :\n De : x=%d  y=%d \n\n", x, y) ;
                    struct s_dlNode* child =(s_dlNode*) malloc(sizeof(s_dlNode)) ;
                    child->nxtB=NULL ;
                    child->nxtL=NULL;
                    child->nxtR=NULL;
                    child->nxtT=NULL;
                    child->depth = node->depth+1 ;
                    child->NodeValue.x= node->NodeValue.x ;
                    child->NodeValue.y =node->NodeValue.y-1 ;
                    child->prev= node ;
                    child->direct=NULL ;
                    /**Previous node*/
                    node->nxtT=child ;
                    buildTree(child, BOTTOM, grid);
               }
               else
               {
                    node->nxtT=NULL ;
               }
               break ;
          case BOTTOM:
               printf("Case bottom \n") ;
               if(((NB_BLOCS_HEIGHT*x+y+1)<NB_TOTAL_BLOCS) &&
                         ((grid[x][y+1]==EMPTY)||(grid[x][y+1]==TARGET)) &&
                         fromDirection!=i &&
                         !(forbiddenTable[x*NB_BLOCS_HEIGHT +y+1]))
               {
                    printf("Déplacement bas possible :\n De : x=%d  y=%d \n\n", x, y) ;
                    struct s_dlNode* child =(s_dlNode*) malloc(sizeof(s_dlNode)) ;
                    child->nxtB=NULL ;
                    child->nxtL=NULL;
                    child->nxtR=NULL;
                    child->nxtT=NULL;
                    child->depth = node->depth+1 ;
                    child->NodeValue.x= node->NodeValue.x ;
                    child->NodeValue.y =node->NodeValue.y+1 ;
                    child->prev= node ;
                    child->direct=NULL ;
                    /**Previous node*/
                    node->nxtB=child ;
                    buildTree(child, TOP ,  grid);
               }
               else
               {
                    node->nxtB=NULL ;
               }
               break ;
          }
     }
        printf("Removing  %d %d from forbidden table\n", x, y);
        /**On supprime l'interdiction de parcourir cette cellule*/
       forbiddenTable[x*NB_BLOCS_HEIGHT +y] =0;
     printf("\n\n END \n\n") ;
}




char* directionString(eDirection dirInt)
{
     switch(dirInt)
     {
     case LEFT :
          return "LEFT" ;
          break ;
     case RIGHT :
          return "RIGHT" ;
          break ;
     case TOP :
          return "TOP" ;
          break ;
     case BOTTOM :
          return "BOTTOM" ;
          break ;
     }
}


s_dlNode* findPathToTargetPos(int grid[][NB_BLOCS_HEIGHT], int targetX, int targetY, int playerX, int playerY)
{
     int i,j ;

     /**Initialisations*/
     numberOfGoodPath =0 ;
     for(i=0 ; i<NB_TOTAL_BLOCS ; i++)
     {
          tab_goodsPath[i]=NULL ;
     }
     reinitForbidTable() ;
     posinit.x=playerX ;
     posinit.y=playerY ;
     postarget.x=targetX ;
     postarget.y=targetY ;

/**Création du noeud racine*/
     sPtr_dlTree root=(s_dlNode*)malloc(sizeof(s_dlNode));
     root->NodeValue=posinit ;
     root->depth=0 ;
     root->nxtB=NULL ;
     root->nxtL=NULL;
     root->nxtR=NULL;
     root->nxtT=NULL;
     root->prev=NULL;
     root->direct=NULL ;


     printf("Build tree\n", i, j);
     foundIndex=0 ;
     buildTree(root, TOP, grid) ;
   
       foundIndex=1 ;
     buildTree(root, LEFT, grid) ;
 
       foundIndex=2 ;
     buildTree(root, RIGHT, grid) ;
 
       foundIndex=3 ;
     buildTree(root, BOTTOM, grid) ;
   
     printf("Calculation done !\n ") ;
     s_dlNode* finalpath ;

     /**Si l'on n'a rien trouvé, on sort et on retourne NULL*/
     if(!numberOfGoodPath)
     {
          return NULL ;
     }

     /**Sinon on recherche la noeud ayant la profondeur la plus faible dans les noeuds valides*/
     for(i=0; i<=numberOfGoodPath ; i++)
     {
          if(i==0)
          {
               finalpath=tab_goodsPath[i];
          }
          if(tab_goodsPath[i+1]!=NULL)
          {
               if(tab_goodsPath[i+1]->depth <finalpath->depth)
               {
                    finalpath =tab_goodsPath[i+1] ;
               }
          }
     }
     printf("Best path depth : %d\n", finalpath->depth) ;
 /**On remonte jusqu'au noeud racine tout en indiquant quel direction prendre pour aller de la cellule précédent à celle en cours*/
     while(finalpath->prev!=NULL)
     {
          if(finalpath->NodeValue.x ==finalpath->prev->NodeValue.x+1)
          {
               finalpath->prev->direction = RIGHT ;
          }
          else if(finalpath->NodeValue.x ==finalpath->prev->NodeValue.x-1)
          {
               finalpath->prev->direction = LEFT ;
          }
          else if(finalpath->NodeValue.y ==finalpath->prev->NodeValue.y+1)
          {
               finalpath->prev->direction = BOTTOM ;
          }
          else if(finalpath->NodeValue.y ==finalpath->prev->NodeValue.y-1)
          {
               finalpath->prev->direction = TOP ;
          }


          finalpath->prev->direct= finalpath ;
          finalpath= finalpath->prev ;
              }

     return finalpath ;
}
Commenter la réponse de eustatika
Signaler Commenter la réponse de eustatika
Messages postés
16
Date d'inscription
lundi 20 octobre 2008
Statut
Membre
Dernière intervention
30 août 2011
0
Merci
Ca marche.
Je suis en train de revoir le programme dans sa globalité car je souhaite que l'on puisse créer des niveaux de tailles variable (jusqu'à 30x30).
Donc j'ai tout à reprendre.
J'en profiterai pour factoriser un maximum de chose et privatiser tout ce qui doit l'être.

Petite note :
Dans la fonction buildTree, lorsque je teste la possibilité de déplacement, j'ai oublié de tester si l'on sort de la grille verticalement.
( y+1 < NB_BLOC_HEIGHT et y-1>0)
Le problème ne s'était pas manifesté jusqu'à présent... étrange.
Commenter la réponse de eustatika
Signaler Commenter la réponse de cptpingu
Messages postés
3835
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
5 mai 2019
 167
0
Merci
Un dépassement de borne ne fait pas forcément planter l'application. Tout dépend de si tu écris sur une page non allouée ou non, d'où le nom de "segmentation fault" (qui devrait s'appelait "page fault"). Quand tu utilises malloc, celui-ci utilise "brk" et "sbrk" qui sont des fonctions systèmes qui ouvrent de nouvelles pages si nécessaire. Écrire sur la fin d'une page allouée, même si avec malloc tu n'es censé ne prendre que la moitié de la page, ne provoque pas de souci. En revanche, si tu écris après la page, là tu auras une erreur car il n'y a pas de page "ouverte" après.

Généralement, sous Linux, je compile en debug ave DUMA qui remplace tous les mallocs par des mallocs spéciaux qui allouent en fin de page. Ainsi, le moindre dépassement de borne assure un segfault. En release, je le retire bien évidemment.

Autre solution: valgrind. Cet utilitaire traque tous les soucis mémoire (fuite de mémoire, dépassement, ...). Agit sur n'importe quel binaire, même si celui-ci n'est pas compilé en debug, et même si l'on n'a pas les sources.

________________________________________________________________________
Historique de mes créations, et quelques articles:
[ http://0217021.free.fr/portfolio http://0217021.free.fr/portfolio]
Merci d'utiliser Réponse acceptée si un post répond à votre question
Commenter la réponse de cptpingu
Signaler Commenter la réponse de eustatika
Messages postés
16
Date d'inscription
lundi 20 octobre 2008
Statut
Membre
Dernière intervention
30 août 2011
0
Merci
Ok merci je vais regarder ça
Commenter la réponse de eustatika

Votre réponse

Répondre au sujet
Posez votre question
S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.