Pathfinding (mode débutant) qui fonctionne mais...

#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.y ==y)
     {
          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 ;
}

 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 ; 

}

#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.y ==y)
     {
          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 ;
}