Discussion :

[hbx360]

Bonjour, dans mon jeu j'ai créer une liste simplement chainé qui contient les données des mes balles il y a :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
typedef struct dataImg dataImg;
 
struct dataImg
{
  int x, y; /*position dans la SDL */
  int vx, vy; /*vecteur vitesse*/
  int count;  /*un conteur qui dit quand la balle a été touché 4 fois elle disparait */
  char ScrPos;  /*L'écran est divisé en 4 partie, la valeur ScrPos vaut soit 0 1 2 3 en fonction de sa position dans une des4 partie de l'écran*/ 
  SDL_Rect ImgSpr; /*contient les coordonnées de l'image dans le sprite*/
  dataImg* next;
};

Ensuite j'ai une autre struct ou une des variables pointe sur la struct dataImg la voici :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
typedef struct dataImageScr
{
  dataImg* ball; /*C'est le pointeur qui pointe sur ma liste*/
  dataImg ship;
  dataImg shoot;
  dataImg flashShipL;
  dataImg flashShipR;
  int NbBallScr;
  int count0,count1,count2,count3;/*Nb ball in each of 4 section of screen */
}dataImageScr;

Donc voilà mon problème il ce situe au niveau du partage de l'écran je vous explique : j'ai une fonction qui récolte les positions de chaque balle a l'écran si une ball est dans le coin inférieur (je me base sur les origines de la SDL) droit je met PosScr à 0, si la balle est dans coin supérieur droit je mets 1 si on est dans le coin supérieur gauche je mets 2 et si je suis dans le coin inférieur gauche je mets 3.

Et donc ensuite ce que je souhaite c'est comparé toutes les coordonnées des balles qui ont un ScrPos identique pour faire mes collisions.

Et donc comme dans ma liste les ScrPos ne sont pas dans l'ordre je souhaitais trié ma liste dans l'ordre croissant avant de faire mes test de collisions et c'est la que l'on arrive au fond du problème c'est que j'ai un seg fault quand je fait mon tri.
Pourriez-vous m'aider à trouver l'erreur ; dans mon code le problème ce situe quand je fait C=C->next
car quand ensuite je fait mon if donc :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

if(C->ScrPos > C->next->ScrPos)

dans C->next->ScrPos C->next vaut NULL alors que le tri n'est pas terminé comme si j'étais arrivé a la fin alors que je ne suis pas arrivé a la fin de ma liste.

Pour mon tri je changes les adresses. J'utilise le tri a bulle qui est conseillé pour des tris de moins de 20 valeurs.

Voici ma fonction de tri :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
 
void clash_sortBallSplitScr(dataImageScr* D)
{
  dataImg* C=NULL;
  dataImg* F=NULL;
  int i,j;
  int nb=D->NbBallScr-1;
  int nb1=nb;
 
 for(j=0;j<nb;j++)
   {
      C=D->ball;
      F=D->ball;
 
      /*while(C->next!=NULL)*/
      for(i=0;i<nb1;i++)
	{ 
	  if(C->ScrPos>C->next->ScrPos) /*sa plante au niveau de C->next qui vaut NULL alors que la boucle n'a pas fini de s'exécuter*/
	    {
	      if(i==0)
		D->ball=C->next; /*pour toujours garder l'adresse de la tête */
 
	      F->next=C->next; 
	      F=C->next;
	      C->next=C->next->next;
	      F->next=C;
	      C=F;
	    }
	  C=C->next; /*l'erreur est ici et se matérialise au if*/
	}
      nb1--;
    }
}

Sinon si je ne veut pas modifié les pointeurs de mes cellules je suis obligé de transférer toutes les donné de la cellule dans l'autre, en fonction de ScrPos ce que je trouve reloud je préfère changer la dispositions des cellules de ma liste.

Ou bien de créer une autre liste et de copié dans celle-ci les donné de la cellule en mettant dans l'ordre croissant en me basant sur ScrPos.

[Matt_Houston]

Je ne vais pas répondre directement à ta question car - ne le prend pas mal - j'ai l'impression que tu perds vraiment beaucoup de temps en conjectures et en premature optimization. C'est bien de t'intéresser aux techniques permettant d'améliorer l'efficacité d'un programme, encore faut-il que leur application soit pertinente.

Tu dis qu'il n'y a qu'une vingtaine de valeurs dans ta liste et tu utilises pourtant un partitionnement, qui est une optimisation plutôt destinée à des collections de grande taille. Pourquoi ? Est-ce que tu as profilé ton code et identifié un ralentissement notable provenant de cette section de code ? Ton jeu est-il par ailleurs terminé ?

À la longue, tu risques de te démotiver plus qu'autre chose. Je te conseille de t'en tenir à une approche naïve (ici, comparer simplement chaque balle à toutes les autres) jusqu'à obtenir un premier résultat. Si les performances ne sont pas satisfaisantes, tu auras bien le temps de t'en rendre compte et de t'en occuper ensuite.

[hbx360]

Non je ne le prends pas mal bien au contraire à partir du moment ou c'est constructif ; je te remercie de ton aide.

Tu dis qu'il n'y a qu'une vingtaine de valeurs dans ta liste et tu utilises pourtant un partitionnement, qui est une optimisation plutôt destinée à des collections de grande taille. Pourquoi ?

je voulais passer par les liste car il m'avait semblé que pour supprimer une balle c'était plus simple en détruisant la cellule que en écrasant le pointeur a supprimer d'un tableau de pointeur par la dernière valeur de ce tableau

Est-ce que tu as profilé ton code et identifié un ralentissement notable provenant de cette section de code ? Ton jeu est-il par ailleurs terminé ?

Profilé je ne vois pas ce que tu veux dire mais non mon jeu ne ralentie pas mon il est terminé (la version tableau) avec quelque petite imperfection (notament après la suppression d'une balle il garde une trace de la dernière position et je n'ai pas réussis a voir ou était le problème mais disparait a la frame suivante) et reste en constante évolution car je voudrais continuer a l'améliorer.

Le partitionnement de l'écran en 4 je me suis dit que sa pouvais être pas mal a coder mais c'est vrai que avec des liste c'est moins évident.

[Matt_Houston]

Une liste chaînée est tout à fait adaptée à ta solution, ce n'est pas cela qui est en cause. Le souci est que tu complexifies - à mon sens bien vainement - ton code en espérant l'optimiser sans te baser sur des faits.

Renseigne-toi bien sur le profilage et les outils disponibles. Cela t'aidera à déterminer quelles parties de ton code méritent ton attention, et tu auras probablement quelques surprises.

[hbx360]

Ok merci pour ta réponse

[hbx360]

Question quand on tri une liste par exemple par ordre alphabétique

est-ce que c'est mieux de trié les cellule ou bien de trié en changeant juste les valeurs de ces cellules ?

[dinobogan]

est-ce que c'est mieux de trié les cellule ou bien de trié en changeant juste les valeurs de ces cellules ?

Il n'y a pas de mieux ou de moins bien. Dans l'absolu, il n'y a pas de réponse correcte : un grand nombre de facteurs entrent en compte. Par exemple la machine qui fait tourner le code, la compréhension et capacité du développeur, les habitudes, la taille des données à copier, le nombre de fois qu'on le fait, la taille du code source...
On ne cherchera pas à optimiser (au sens large) de la même manière entre un code utilisé uniquement à l'init du programme qu'un autre code appelé plusieurs milliers de fois par seconde. Donc au delà de ce qu'il est communément admis, il ne faut jamais perdre de vue l'usage qui en sera fait.

En programmation, la recherche de la perfection ne se fait jamais à priori (Matt_Houston utilise la célèbre expression premature optimization) mais à postériori. Cela signifie que ton développement aura une forme itérative. Tu produits le code source le plus logiquement et standard possible. Pas n'importe comment non plus bien sûr. Tu dois avoir une vision globale pour savoir ou tu veux en venir pour ne pas être obligé de casser ton architecture toute les 2 semaines. Mais le code écrit n'est jamais figé. Durant le développement, il ne faut pas s'interdire de revenir sur certains points. Les phases de tests sont également le moment de revenir sur des parties qui ne sont pas satisfaisantes (souvent pour le temps d'exécution, mais aussi pour l'usage des ressources CPU, disque, réseau, RAM, ...). Et pour revenir sur certains points, il faut du temps. Si tu as passé tout ton temps à philosopher sur pleins d'approches possibles, tu ne pourras plus utiliser du temps pour améliorer ton code

[hbx360]

Merci pour ta réponse

[hbx360]

Merci a tous pour vos réponse mais je souhaiterais recentré la discussion sur mon problème j'ai un tri a bulle qui ne fonctionne pas et en faite j'aurai aimer avoir de l'aide pour voir d'ou viens mon erreur que je n'arrive pas a trouvé.

Merci par avance.

[Sve@r]

Merci a tous pour vos réponse mais je souhaiterais recentré la discussion sur mon problème j'ai un tri a bulle qui ne fonctionne pas et en faite j'aurai aimer avoir de l'aide pour voir d'ou viens mon erreur que je n'arrive pas a trouvé.

Bonjour

Déjà faire un tri sur une liste chainée c'est absurde car un des avantages d'une liste c'est d'avoir ses éléments toujours triés (tout nouvel élément est inséré à sa bonne place). Donc généralement les tris se font sur des tableaux.
Ensuite faire un tri à bulle est le plus ignobles des tris (une liste de n éléments est parcourue n fois).
Et enfin faire soi-même son tri est dommage vu qu'il existe la fonction qsort() qui peut trier n'importe quel tableau de n'importe quoi...

[hbx360]

Merci pour ta réponse je pense que c'est un bonne exercice de le faire soit même sinon on n'apprendrais jamais rien je penses.

En faite dans mon jeu je divise en quatre mon écran pour optimisé (je trouve que c'est là aussi un bonne exercice pour apprendre) pour avoir moins de teste de collision a faire.

Donc c'est pour sa que je tri ma liste puisque les balles ne sont pas toujours forcément dans le mêmes endroit donc la valeur ScrPos de mes cellule peux changer.

Par exemple je pourrai avoir ma liste simplement chainé comme ça avec la valeur ScrPos de mes cellule à : 0 1 0 2 3 0 3 1 2 2 et donc le but serait de trié la liste afin d'avoir ça 0 0 0 1 1 2 2 2 3 3 et ensuite je ferai mes testes de collisions, puis je pourrai tester si il y a collision avec mon tire pour effacé la balle.

Je trouve que de trié les cellule c'est mieux de plus je ne peux pas créer ma liste et trié en même temps puis que les valeur ScrPos change régulièrement.

[hbx360]

Merci pour ta réponse je pense que c'est un bonne exercice de le faire soit même sinon on n'apprendrais jamais rien je penses.

En faite dans mon jeu je divise en quatre mon écran pour optimisé (je trouve que c'est là aussi un bonne exercice pour apprendre) pour avoir moins de teste de collision a faire.

Donc c'est pour sa que je tri ma liste puisque les balles ne sont pas toujours forcément dans le mêmes endroit donc la valeur ScrPos de mes cellule peux changer.

Par exemple je pourrai avoir ma liste simplement chainé comme ça avec la valeur ScrPos de mes cellule à : 0 1 0 2 3 0 3 1 2 2 et donc le but serait de trié la liste afin d'avoir ça 0 0 0 1 1 2 2 2 3 3 et ensuite je ferai mes testes de collisions, puis je pourrai tester si il y a collision avec mon tire pour effacé la balle.

Je trouve que de trié les cellule c'est mieux de plus je ne peux pas créer ma liste et trié en même temps puis que les valeur ScrPos change régulièrement.

Si je t'écoute tu es en train de me dire que pour mon jeu il est inapproprié d'utiliser une liste chainé pourtant dans le jeu de la taupe codeurPlusPlus utilise des chaines donc je voulais faire de même et la aussi c'est un bonne entrainement de plus mon but c'est aussi de coder par moi même sinon quel est l'intérêt d'apprendre si tu ne fait qu'utiliser des fonctions toutes faite je pense que faire c'est propre fonction c'est bien aussi.

Ensuite faire un tri à bulle est le plus ignobles des tris (une liste de n éléments est parcourue n fois).

Je suis allé voir une vidéo youtube :

Le prof explique que le tri a bulle est approprié pour les dimension inférieur a 20 ce qui est mon cas donc j'ai suivie ce que ce prof universitaire a dit.
Ansia c'est l'École nationale supérieure d'informatique et d'analyse des systèmes est l'une des grandes écoles d'ingénieurs marocaines rattachée à l'université Mohammed V - Souissi de Rabat.
Donc je ne pense pas que c'est prof universitaire soit des guignols.

[ternel]

En fait, tu as beaucoup mieux à faire que trier tes balles.
Tu peux avoir quatre listes, une pour chaque partie de ton écran.
Ainsi, tu n'as pas besoin de trier completement, mais juste de remettre chaque balle dans la bonne liste quand tu la déplaces.
au lieu de faire un tri, au mieux en N*log(N), tu n'a qu'une série de changement, en N

Renseignes-toi sur ce qu'on appelle quad-tree ou octree/octtree/oct-tree.
C'est précisément un système de répartition par parties, en 2D (quad-) ou 3D (oct-)

[hbx360]

Merci beaucoup pour ta réponse qui m'apporte pas mal d'info.

Tu peux avoir quatre listes, une pour chaque partie de ton écran.

Effectivement je n'y avais pas pensé.

Renseignes-toi sur ce qu'on appelle quad-tree ou octree/octtree/oct-tree.

Merci pour cette info je vais me renseigné.

[Sve@r]

Merci pour ta réponse je pense que c'est un bonne exercice de le faire soit même sinon on n'apprendrais jamais rien je penses.

Exact - Mais dans ce cas, on se concentre sur le tri lui-même (a titre d'exercice) ce qui évite de cumuler les soucis liés au tri et à la liste chainée...

et la aussi c'est un bonne entrainement de plus mon but c'est aussi de coder par moi même sinon quel est l'intérêt d'apprendre si tu ne fait qu'utiliser des fonctions toutes faite je pense que faire c'est propre fonction c'est bien aussi.

Exact (je me suis d'ailleurs moi-même amusé à recoder qsort). Mais encore une fois, quand on tente un exercice, je pense qu'il vaut mieux alors se limiter à l'exercice et éviter de cumuler les soucis.

Revenons donc à ton tri à bulles. Voici ta fonction d'origine

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void clash_sortBallSplitScr(dataImageScr* D)
{
  dataImg* C=NULL;
  dataImg* F=NULL;
  int i,j;
  int nb=D->NbBallScr-1;
  int nb1=nb;
 
 for(j=0;j<nb;j++)
   {
      C=D->ball;
      F=D->ball;
 
      /*while(C->next!=NULL)*/
      for(i=0;i<nb1;i++)
	{ 
	  if(C->ScrPos>C->next->ScrPos) /*sa plante au niveau de C->next qui vaut NULL alors que la boucle n'a pas fini de s'exécuter*/
	    {
	      if(i==0)
		D->ball=C->next; /*pour toujours garder l'adresse de la tête */
 
	      F->next=C->next; 
	      F=C->next;
	      C->next=C->next->next;
	      F->next=C;
	      C=F;
	    }
	  C=C->next; /*l'erreur est ici et se matérialise au if*/
	}
      nb1--;
    }
}

Regarde bien la partie en rouge. Si tu as (par exemple) 5 éléments, ta boucle fera une itération de l'élément [0] (le premier) vers l'élément [4] (le dernier). Mais quand tu es sur le dernier, tu ne peux plus comparer avec le suivant (vu qu'il n'y a pas de suivant !!!)
En plus tu l'avais vu que ça plantait et surtout pourquoi ça plantait !!! Comment t'as fait pour ne pas en tirer les bonnes conclusions ???

Dans un tri à bulles, la seconde boucle va de (i=1; i <n). Et tu compares l'élément [i] avec l'élément [i-1]. Ou bien elle va de (i=0; i < (n-1)) si tu veux comparer l'élément [i] avec l'élément [i+1].
En fait, pour être exact, la seconde boucle doit s'arrêter à "n - indice de la première boucle" (parce qu'à chaque itération "i" de la première boucle, les "i" valeurs les plus grandes sont alors placées à la bonne place). Et si tu veux l'optimiser un peu plus, alors tu mémorises la position de la première permutation (premier élément qui n'est plus à la bonne place) et à l'itération suivante de la première boucle, tu fais commencer ta seconde boucle à cette position (algorithme du "tri à bulles optimisé")...

[hbx360]

Merci beaucoup pour ta réponse cela va me permettre de résoudre mon problème.
C'est pas évident de coder des tri avec des listes.