Aide projet jeu vidéo

**Lanslow** · 28/05/2015, 20h15

Bien le bonjour/bonsoir !

Je viens à vous car j'ai un problème avec mon jeu vidéo que je crée dans le cadre de mes études.
On dispose d'un vaisseau, qui tire sur des astéroïdes à l'aide de missiles.
Quand le missile touche un gros, il se divise en 2 moyens (j'ai les sprites), et un moyen en 2 petits.

Donc quand il y a collision, j'utilise une fonction pour enlever l'astéroïde de ma liste, afin qu'il disparaisse de l'écran. Mais cette fonction ne marche pas très bien si l'astéroïde est en premier de la liste je crois.
Voici ma fonction :

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
 
    object_list delete_object(object * O, object_list L)
    {
      object_list tmp = L;
      object_list previous = L;
      if (object_list_head(previous) == O)
        {
          L = object_list_tail(previous);
          free(previous);
          return L;
        }
      tmp = object_list_tail(previous);
      while (tmp != NULL)
        {
          if (object_list_head(tmp) == O)
            {
               previous->next = tmp->next;
               free(tmp);
               return L;
            }
          previous = tmp;
          tmp = object_list_tail(tmp);
        }
 
      return L;
 
    }

object_list_head retourne le premier de la liste, et object_list_tail retourne le reste de la liste.
Donc ma structure object_list contient : un objet O, et une object_list L.

Merci d'avance de vos réponses!

Cordialement,

Lanslow

**Médinoc** · 29/05/2015, 11h12

C'est quoi object_list?
Encore un typedef mal pensé sur un pointeur vers élément de liste?

Franchement, pour supprimer des éléments d'une liste simplement chaînée, je trouve que la technique du pointeur de pointeur est paradoxalement plus simple que la technique d'en mémoriser plusieurs.

Il suffit de comprendre qu'à chaque étape du parcours, on pointe sur le pointeur qu'on modifiera en cas de suppression. Nom : LinkedList.png
Affichages : 363
Taille : 7,8 Ko

Nom : LinkedList.png
Affichages : 363
Taille : 7,8 Ko

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <stdlib.h>
#include <assert.h>
 
/*En supposant qu'un nœud est de type object_link*/
 
typedef struct object_link
{
	struct object_link *pNext;
 
	object* data;
};
 
/*D'abord quelques fonctions d'aide, qui évitent les erreurs:*/
 
/*Fonction de free fortement typée*/
void free_node(object_link *pRemove) { free(pRemove); }
 
/*Fonction pour parcours indirect de la liste:
À partir d'un pointeur sur un pointeur sur un objet, elle retourne le pointeur sur son pointeur "suivant",
c'est-à-dire le pointeur sur le pointeur sur l'objet suivant.*/
object_link ** GetNextPtr(object_link ** ppObj)
{
	/*La fonction ne doit pas être appelée sur un pointeur nul, ni sur un pointeur pointant sur un pointeur nul.*/
	/*Elle ne retourne jamais un pointeur nul non plus, mais elle peut retourner un pointeur sur un pointeur nul.*/
	assert(ppObj != NULL);
	assert(*ppObj != NULL);
 
	return &( (*ppObj)->pNext );
}
 
/*Retourne le pointeur sur le pointeur sur le premier objet contenant O.
  Le pointeur retourné pointe donc sur celui à modifier si on supprime le nœud.
 
Cette fonction retourne un pointeur nul en cas d'échec, 
mais ne retourne jamais de pointeur sur un pointeur nul.*/
object_link ** List_FindPtr(object_link ** ppHead, object * O)
{
	object_link **ppCurrent;
 
	assert(ppHead != NULL);
	for(ppCurrent=ppHead ; *ppCurrent != NULL ; ppCurrent = GetNextPtr(ppCurrent))
	{
		if((*ppCurrent)->data == 0)
			return ppCurrent;
	}
	return NULL;
}
 
void List_Remove(object_link ** ppHead, object * O)
{
	object_link ** ppRemove = List_FindPtr(ppHead, O);
	if(ppRemove != NULL)
	{
		object_link *pRemove = *ppRemove;
		*ppRemove = pRemove->pNext;
		free_node(pRemove);
	}
}

**Lanslow** · 29/05/2015, 22h34

Code :

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

1
2
3
4
5
struct object_list_cell
{
  object * obj;
  struct object_list_cell * next;
};

Voici la structure, renommée en object_list ensuite.

Et je n'ai pas très bien compris toutes les étapes de tes fonctions, ce n'est que mon tout début en C...
Mais merci de ta réponse.

**Médinoc** · 30/05/2015, 11h10

Alors j'explique:

Le principe de travailler avec des pointeurs de pointeur, c'est que ça permet aux fonctions de modifier le pointeur en question directement quand la liste est modifiée. Y compris le premier pointeur, celui qui n'est pas dans une structure object_list_cell (ou object_link comme je l'appelle).

Considère la fonction basique d'insertion en tête de liste:

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
int List_InsertHead(object_link **ppHead, object * O)
{
	object_link *pNew;
	assert(ppHead != NULL);
 
	pNew = malloc(sizeof *pNew);
	if(pNew == NULL)
		return -1;
	pNew->pNext = NULL;
	pNew->data = O;
 
	/*Insère en tête de liste*/
	pNew->pNext = *ppHead;
	*ppHead = pNew;
	return 0;
}

L'insertion se fait directement en modifiant le pointeur pointé. Comment les choses pourraient-elles être plus simples?

Attention: Quand on travaille avec des pointeurs de pointeur, il est très facile de s'emmêler les pinceaux. C'est pourquoi je recommande d'utiliser au moins un minimum de notation hongroise, en préfixant les pointeurs ordinaires par p et les pointeurs de pointeur par pp, pour bien voir ce que l'on fait.

**Lanslow** · 30/05/2015, 12h18

J'ai compris ta fonction, c'est déjà ça.

Mais par contre ce que je ne comprends pas, c'est l'utilité d'utiliser un pointeur de pointeur, contrairement à un pointeur standard. Donc d'utiliser **pphead au lieu de *phead en paramètre. Si tu peux m'expliquer la différence que cela changera dans la fonction.

**Médinoc** · 30/05/2015, 15h28

C'est parce que je n'aime pas le formalisme pListe = List_Add(pListe, quelquechose) quand la fonction modifie le truc pointé de toute façon. L'ancien pointeur pListe? Il pointe désormais au beau milieu de la liste, ou bien il était nul avant, etc.

Je trouve que le mécanisme List_Add(&pPremier, quelquechose) est bien plus explicite et facile à assimiler.

De plus, ma fonction insertHead? J'aurais en fait du l'appeler insertBefore, parce qu'on peut l'utiliser ailleurs dans la liste. Y compris avant la fin:

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
/*Fonction pour parcours indirect de la liste:
À partir d'un pointeur sur un pointeur sur un objet, elle retourne le pointeur sur son pointeur "suivant",
c'est-à-dire le pointeur sur le pointeur sur l'objet suivant.*/
object_link ** GetNextPtr(object_link ** ppObj)
{
	/*La fonction ne doit pas être appelée sur un pointeur nul, ni sur un pointeur pointant sur un pointeur nul.*/
	/*Elle ne retourne jamais un pointeur nul non plus, mais elle peut retourner un pointeur sur un pointeur nul.*/
	assert(ppObj != NULL);
	assert(*ppObj != NULL);
 
	return &( (*ppObj)->pNext );
}
 
 
/*Cette fonction me donne carrément un pointeur vers le pointeur nul de la liste.
  C'est-à-dire, un pointeur vers le pointeur à modifier si j'ajoute un truc à la fin de la liste.*/
object_link ** GetTailNullPtr(object_link **ppObj)
{
	assert(ppObj != NULL);
 
	while(*ppObj != NULL)
		ppObj = GetNextPtr(ppObj);
 
	return ppObj;
}
 
/*Et avec ça, voici comment on ajoute à la fin de la liste:*/
void List_AppendTail(object_link **ppHead, object* O)
{
	object_link **ppTail = GetTailNullPtr(ppHead);
	List_Insert(ppTail, O);	
}

Vois-tu comme la dernière fonction devient simple? Avec cette façon de faire, il n'y a pas de cas particulier pour le début ou la fin de la liste. Je peux juste appeler la fonction X fois comme ceci (bien que ce soit sous-optimal en termes de performances):

Code C :

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

1
2
3
4
5
6
7
object_link *pHead = NULL;
 
...
 
List_AppendTail(&pHead, object1); /*Ce premier ajout créera la liste*/
List_AppendTail(&pHead, object2);
List_AppendTail(&pHead, object3);

Et pour le faire ajouter en boucle à la fin de la liste sans re-parcourir la liste à chaque fois, on peut faire ceci:

Code C :

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

1
2
3
4
5
6
7
8
9
10
object_lnk **ppTail = GetTailNullPtr(&pHead); /*Ceci marche même si pHead est NULL*/
 
/*On suppose que read_object() lit un nouvel objet depuis un fichier, 
ou l'entrée standard, etc. et qu'on veut l'ajouter à la liste */
object *new_object;
while((new_object=read_object()) != NULL)
{
	List_AppendTail(ppTail, new_object);
	ppTail = GetTailNullPtr(ppTail);
}

Ce code ajoutera les objets au fur et à mesure, sans parcourir la liste à chaque fois, même si elle est complètement vide au début.
C'est un concept qui paraît compliqué au début, mais simplifie grandement la vie pour les listes simplement chaînées!

Invité · 30/05/2015, 15h46

C'est à cause de la portée des variables.

En C, lors d'un appel d'une fonction, le passage des paramètres se fait par valeur. Ainsi, les fonctions ne reçoivent pas les variables en tant que tel, mais une copie de la valeur des variables.
Que ce soit des variables "normal" ou des pointeurs, le contenu de la variable est copié dans la fonction, et ce sont des variables internes à la fonction (donc, des variables contenant des copies de la valeur) que l'on va utiliser.

Quand on utilise un pointeur, comme on ne modifie pas la variable en elle-même mais le contenu à l'adresse pointé par la variable, cela permet de modifié des variables n'étant pas interne à cette fonction.

Mais, à partir du moment ou tu souhaites modifier l'adresse pointé par un pointeur, on se retrouve dans le même cas d'une variable "normal". Les modifications qui seront faites seront réalisé non pas sur la "vrai" variable pointeur, mais sur la variable pointeur interne à la fonction. Quand la fonction s'arrête, ta modification s'en va elle aussi.

Du coup, on utilise la même astuce : On utilise un pointeur. Au lieu de donner un paramètre le pointeur, on va donné son adresse. Ainsi on va pouvoir modifier la "vrai" variable et non une copie. Ce qui, du coup, résout beaucoup de problème.

**Lanslow** · 30/05/2015, 23h33

Je n'avais toujours pas compris l'histoire des pointeurs de pointeurs avec ton explication Médinox, mais l'explication de archMqx m'a parue vraiment très clair, alors merci ! J'ai bien compris leur utilité dans ce cas.

Et merci pour ton explication sur les fonctions que tu as utilisé Médinox, cela devrait me permettre de recréer ma fonction de suppression d'un objet, je vais me concentrer là dessus pour bien comprendre, et je pense que je vais y arriver.
Merci beaucoup !

**Lanslow** · 30/05/2015, 23h37

Mais alors en utilisant ta façon de faire, je dois changer ma structure de liste je suppose?

**Médinoc** · 31/05/2015, 08h47

Normalement, la structure reste la même (ça reste une liste simplement chaînée), les seuls changements que je recommande sont:

préfixer les noms de variables des pointeurs pour éviter de s'y perdre.
Pas de typedefs qui cachent les pointeurs. C'est une source de confusions et problèmes. Je ne suis pas le seul sur ce site à dire cela.

**Lanslow** · 31/05/2015, 12h52

D'accord, je devrais pouvoir m'en sortir grâce à tes précieuses explications, et à celles de archMqx, merci beaucoup !

**Kannagi** · 31/05/2015, 15h05

C'est un peu HS (mais pas tant que ça) , sauf si c'est un exercice de cours C mais pour un shoot them up je trouve que l'utilisation des listes chaînées est un peu abusé un simple tableau bien pensé est suffisant pour les tirs (je parle en connaissance de cause ayant codé ce genre de fonctionnalité en C ou assembleur).

**Lanslow** · 31/05/2015, 18h48

Ce sont les profs qui nous imposent d'utiliser les listes, sinon oui on avait tout de suite pensé à utilisé des tableaux, mais pas le choix !

**Lanslow** · 01/06/2015, 15h33

Envoyé par Médinoc

Alors j'explique:

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
int List_InsertHead(object_link **ppHead, object * O)
{
	object_link *pNew;
	assert(ppHead != NULL);
 
	pNew = malloc(sizeof *pNew);
	if(pNew == NULL)
		return -1;
	pNew->pNext = NULL;
	pNew->data = O;
 
	/*Insère en tête de liste*/
	pNew->pNext = *ppHead;
	*ppHead = pNew;
	return 0;
}

Je ne comprends pas la ligne if (pNew == NULL) alors return -1;
Je ne comprends pas pourquoi ce test.
Merci d'avance de votre réponse!

**ternel** · 01/06/2015, 15h57

La fonction malloc peut toujours échouer, par exemple par manque de mémoire disponible, auquel cas, elle retourne NULL.

NULL étant une valeur de pointeur invalide, tout utilisation provoque une erreur de segmentation (segfault).

Tester le retour de malloc permet de s'assurer qu'on n'aura pas de soucis.
le choix du return -1 est arbitraire, mais permet de sortir de la fonction avec une valeur anormale.
J'aurai cependant ajouté un commentaire expliquant que -1 est un code d'erreur.

**Médinoc** · 01/06/2015, 18h05

En effet, j'ai oublié de mentionner, j'ai utilisé ici la convention POSIX: La fonction retourne 0 pour OK, -1 en cas d'erreur (ou de manière plus générale, un retour non-négatif pour OK, strictement négatif pour erreur).

**Lanslow** · 01/06/2015, 20h05

D'accord, j'ai bien compris, ton explication m'est très claire, merci !

**Lanslow** · 01/06/2015, 20h25

Mais c'est une convention qui est déjà définie en C ?

Invité · 01/06/2015, 21h53

Envoyé par Lanslow

Mais c'est une convention qui est déjà définie en C ?

C'est suivis par l'ensemble de la glibc en tout cas, la bibliothèque standard C dans le monde Unix.

Comme l'a dit Médinoc, prends toujours l'habitude de vérifier le retour des fonctions de la librairie standard, et de toutes les fonctions d'une manière générale.
Les fonctions sont censé faire ce que tu souhaites, mais si pour une raison X ou Y ce n'est pas le cas, cela causera des erreurs dans la suite de ton programme (typiquement un malloc qui n'alloue pas un espace mémoire, ou un fopen qui n'ouvre pas le FILE*).

**Lanslow** · 02/06/2015, 01h15

D'accord merci du conseil!

Aide projet jeu vidéo

C

Discussions similaires

Partager

Partager