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.