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"
j'ai intégré un pathfinding pour déplacer le joueur au clique
Pour ceux que ça intéresse, voici le code qui permet de trouver le chemin le plus court dans un labyrinthe 2D
Je dois le reprendre de 0 pour l'optimiser car on m'a fait remarquer que c'était un peu tortueux
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 ; }
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question- 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.
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
Mais je comprends bien qu'il faut que je reprenne tout ça et que je l'épure.
Dans ta grille de taille fixe, as-tu besoin de supprimer/insérer souvent en milieu de liste ? ;)
#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 ; }