Discussion :

[AntoineCompagnie]

Bonsoir !

Je veux affecter un tableau de tableaux de manière dynamique et je ne sais pas quelle taille aura ce tableau.

Lorsque j'essaie de le faire une erreur apparait :

Code :

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

1
2
error: variable-sized object may not be initialized
            int **open_set[0][ligne][colonne] = board[ligne][colonne];

Voici le code en question. Il s'agit d'implémenter l'algorithme A-Star pour un cours d'intelligence artificielle.

**open_set représente les noeuds du graphe des chemins à suivre qui doivent encore être évaluer.

Code :

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

1
2
3
4
5
6
7
8
9
void A_star(){
 
    int **closed_set=NULL;
 
    for(int ligne = 0; ligne < d; ligne++){
        for(int colonne = 0; colonne<d;colonne++){
            int **open_set[0][ligne][colonne] = board[ligne][colonne];
        }
    }

Pouvez vous m'aider à comprendre comment affecter dynamiquement ce tableau?

Merci d'avance !

[Sve@r]

Bonjour

Quand tu as un pointeur truc *pt, tu n'as pas le droit de taper dans "*pt" si tu n'as pas écrit auparavant pt=adresse_valide. Et si tu n'as aucune adresse à ta disposition tu dois alors allouer de la mémoire via malloc.

Toi tu as un double pointeur. Si on doit faire une analogie, alors il faut voir autant d'étoiles que de dimensions (attention, ce n'est pas une équivalence stricte (sinon tous les puristes vont me hurler dessus -a raison !!!-), c'est juste une façon d'imaginer).
Donc si tu as in int **open_set (il y a d'ailleurs une erreur dans ta fonction car on y lit "closed_set"), ça veut dire que tu pars "à priori" sur un tableau 2D (comme un échiquier).

Mais comme pour un échiquier, tu dois d'abord définir combien tu auras de lignes (qui se comporteront comme d'autant de tableaux 1D). Tu dois alors impérativement allouer open_set en lui disant qu'il devra gérer "L" lignes: open_set=malloc(L * sizeof(int*)).

Maintenant tu as à ta disposition L pointeurs allant de open_set[0] jusqu'à open_set[L-1]. Mais chacun de ces pointeurs doit être alloué pour pouvoir stocker "c" éléments (le "c" représentant les colonnes de ton échiquier). Donc tu dois boucler de 0 à L et écrire à chaque itération open_set[i]=malloc(c * sizeof(int)). Et bien entendu, en vérifiant que chaque malloc se passe bien (donc qu'il n'ait pas renvoyé NULL) et en ayant prévu une échappatoire si c'est le cas ; échappatoire qui s'occupe alors de désallouer tout ce qui a été alloué => exemple: si tu as alloué les open_set[i] de 0 à 8 et que ça plante au open_set[9] tu dois alors libérer les 8 open_set[i] correctement alloués puis libérer le open_set alloué au tout début (celui qui gère les lignes).

Sinon une fois que tout est alloué sans erreur, tu as alors le droit de taper dans open_set[i][j] (lui affecter un entier, ou aller lire l'entier qui s'y trouve).

En tout état de cause, tu ne peux pas aller taper dans "**open_set[x][y][z]" vu que open_set n'a que 2 dimensions (et en plus tu y as rajouté 2 étoiles ce qui "signifierait" que "open_set" a en réalité 5 dimensions !!!

Bref beaucoup d'incohérences dans ce que tu écris. Tu devrais revoir sérieusement le cours sur les pointeurs et les tableaux...

[Invité]

Code :

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

1
2
3
4
5
6
7
8
 
void A_star(){ 
    int **closed_set=NULL;
    for(int ligne = 0; ligne < d; ligne++){
        for(int colonne = 0; colonne<d;colonne++){
            int **open_set[0][ligne][colonne] = board[ligne][colonne];
        }
    }

Je comprends pas trops ton code mais peut-être que tu voulais faire sa:

Code :

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

1
2
3
4
5
6
7
 
   int **open_set[1][d][d];
    for(int ligne = 0; ligne < d; ligne++){
        for(int colonne = 0; colonne<d;colonne++){
            open_set[0][ligne][colonne] = board[ligne][colonne];
        }
    }

[AntoineCompagnie]

D'accord, le point à travailler est bien entendu l'allocation avant l'insertion.

Dans la mesure ou j'essaye de stocker les nœuds de la résolution du jeu du Taquin de taille d*d, je cherche à stocker dans open_set les différents tableaux découverts que l'on doit encore évaluer selon l'algorithme A étoile.

Juste au cas ou, ci ca peut aider voici un exemple de jeu résolu.



J'essaie de le résoudre automatiquement grâce à A étoile. Ne sachant pas combien de tableau j'ai à gérer, comment allouer cette mémoire?

Code :

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

open_set=malloc(???*sizeof(int*))

Tout en bouclant à chaque itération:

Code :

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

1
2
 
open_set[i]=malloc(d*d * sizeof(int))

Ne serait il pas plus simple de représenter les tableau du jeu sous forme de liste?

Imaginons que j'ai bien mes pointeurs de tableau désormais. Pourquoi ne pas utiliser

Code :

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

**open_set[x][y][z]

? x aurait été le numéro du tableau, y et z les coordonnées de chaque numéro.


Je sais que c'est confus, j'ai débarqué en L3 informatique après deux ans de facs d'éco et je me suis battu pour entrer en M1.

[Matt_Houston]

Ton programme doit fonctionner avec des dimensions de grille arbitraires, mais es-tu autoriser à le recompiler pour modifier ces paramètres ?

Ma question est destinée à déterminer quel degré d'allocation mémoire dynamique est nécessaire.

C'est tentant de représenter une grille rectangulaire par un tableau multidimensionnel lorsque l'on débute mais c'est une fausse bonne idée. Particulièrement lorsque le tableau multidimensionnel doit être alloué dynamiquement (donc de manière non contigüe) et qu'on ne maîtrise pas la gestion mémoire.

[picodev]

Bonjour,

comme tu utilise A* tu vas devoir utiliser un type de données de genre file de priorité. Je ne peux que te conseiller de créer un module proposant ce type et les primitives le manipulant. L'écriture de ton code sera simplifiée.
Pour l'implémentation de cette file tu peux au choix utiliser les listes chaînées ou les tas avec, pour l'un comme pour l'autre, une implémentation soit à base de «pointeurs à la C» ou à base de tableaux.
Implémente déjà ta file de priorité avant de mettre la main dans le cambouis.

[AntoineCompagnie]

Ton programme doit fonctionner avec des dimensions de grille arbitraires, mais es-tu autoriser à le recompiler pour modifier ces paramètres ?

Oui, la taille est donnée dès le départ lors de l'appel du programme par ./fifteen 3 par exemple, qui donnera un tableau de taille 3*3.

C'est tentant de représenter une grille rectangulaire par un tableau multidimensionnel lorsque l'on débute mais c'est une fausse bonne idée. Particulièrement lorsque le tableau multidimensionnel doit être alloué dynamiquement (donc de manière non contigüe) et qu'on ne maîtrise pas la gestion mémoire.

Rah, oui c'est rageant, ça ressemble à la forme qu'on lui donne dans sa tête. Donc si j'ai bien compris il faut que j'utilise des tas avec des règles de priorité? Je ne sais pas encore ce que c'est que tout ça. Je vais me renseigner! Merci!

[Sve@r]

D'accord, le point à travailler est bien entendu l'allocation avant l'insertion.

Bien entendu. On ne peut peut évidemment pas insérer avant d'avoir la place pour ça. Ceci dit c'est bien d'en avoir conscience (tu te démarques déjà de 50% de débutants qui croient qu'en C la mémoire est générée automatiquement !!!)

Dans la mesure ou j'essaye de stocker les nœuds de la résolution du jeu du Taquin de taille d*d, je cherche à stocker dans open_set les différents tableaux découverts que l'on doit encore évaluer selon l'algorithme A étoile.Je sais que c'est confus, j'ai débarqué en L3 informatique après deux ans de facs d'éco et je me suis battu pour entrer en M1.

Je comprends mieux ce que tu veux faire.

A mon avis, une bonne façon de faire serait que tu dissocies

• l'état du jeu lui-même
• les différents jeux possibles

Dans cette optique, tu pourrais créer un outil destiné à stocker l'état du jeu. A mon avis je pense qu'un tableau 2D serait parfait. On pourrait éventuellement envisager la possibilité d'un tableau 1D car on peut par exemple considérer ton jeu final comme la suite "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0" mais si on ne symbolise pas le fait que "12" est au dessus du "0" (symbolisant le vide) on risque d'avoir des difficultés quand on voudra calculer les déplacements possibles. Et même si ces difficultés ne sont pas insurmontables, si on part directement sur du 2D on s'affranchit quand-même de certains soucis de positionnement.

Donc imaginons ton jeu se déclarant comme un int jeu[x][y]. Tu pourrais alors prévoir une structure de liste destinée à stocker les différents jeux possibles. Cette structure pourrait alors être

Code c :

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

1
2
3
4
5
6
7
8
9
10
typedef struct s_noeud{
    int jeu[x][y];
    struct s_noeud *next;
} t_noeud;
 
typedef struct {
    t_noeud *first;
    t_noeud *last;
    size_t nb_noeuds;
} t_liste;

Le problème, vois-tu, c'est qu'au delà d'un certain niveau de complexité, le cerveau ne peut plus suivre. C'est pour ça qu'en dissociant "jeu" et "structure permettant de manipuler différents jeux" tu transformes une entité de complexité "N" en "2" entités de complexité "N/2". Donc au lieu de représenter les différents jeux par un gros tableau multidimensionnel (2D pour le jeu et une 3° dimension pour les différents jeux) tu as d'un coté une entité te permettant de manipuler les pions d'un jeu et de l'autre une entité te permettant de manipuler différents jeux distincts.

A partir de là, tu peux mieux appréhender. Par exemple rajouter un jeu en fin de la liste des jeux déjà existants ça pourrait se faire ainsi

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
t_noeud *ajouter_jeu(int jeu[x][y], t_liste *liste)
{
    t_noeud *nouveau;
 
    // On crée le noeud à insérer
    nouveau=malloc(sizeof(t_noeud));
 
    // Si l'allocation a échoué
    if (nouveau == NULL)
    {
        // Inutile de continuer
        return NULL;
    }
 
    // On remplit le noeud créé avec le jeu à stocker
    memcpy(nouveau->jeu, jeu, x*y*sizeof(int)); // L'avantage du tableau c'est qu'il est contigu en mémoire donc le jeu tout entier peut se copier d'un bloc
    nouveau->next=NULL;
 
    // S'il n'y a pas de premier noeud
    if (liste->first == NULL)
    {
        // On positionne le noeud créé en tête de liste
        liste->first=nouveau;
    }
 
    // S'il y a un dernier noeud déjà présent
    if (liste->last != NULL)
    {
        // Le dernier noeud présent enchaine sur celui qu'on vient de créer
        liste->last->next=nouveau;
    }
 
    // Quoi qu'il arrive, le noeud nouvellement créé ira en fin de liste (puisque quoi qu'il arrive c'est le dernier a avoir été créé)
    liste->last=nouveau;
 
    // On a un noeud de plus dans la liste
    liste->nb_noeuds++;
 
    // Le travail a été fait - On renvoie une valeur indiquant qu'il n'y a pas eu de soucis - Le plus simple est alors de renvoyer l'adresse crééé
    return nouveau;
}

Avec cette fonction tu n'as plus de soucis de mémoire. Dès que tu veux stocker un nouveau jeu, tu l'appelles et tu la laisses se débrouiller (en vérifiant tout de même son retour pour t'assurer que le jeu a bien été stocké)...

[AntoineCompagnie]

Okay, merci pour ces précisions et ce plan de route. Ca m'a permit d'apprendre ce qu'étaient les structures, typedef...

Si je considère avoir déjà traité la création des jeux représenté par la variable board[ligne][colonne], je suis donc en train d'essayer de mettre en place la "structure permettant de manipuler différents jeux". Néanmoins j'ai un problème dans la mesure ou la taille x,y de "jeu[x][y]" que vous m'avez donné n'est pas fixée dès le départ dans la mesure ou cela dépend de ce que le joeur entre comme taille d lorsqu'il entre l'argument de type int au programme.

Cela résulte en une erreur fields must have a constant size dans le code de la structure de s_noeud qui représente les états de mon jeu et que j'ai mis à la fin du main:

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
int main(int argc, string argv[])
{
    // ensure proper usage
    if (argc != 2)
    {
        printf("Usage: fifteen d\n");
        return 1;
    }
 
    // ensure valid dimensions
    d = atoi(argv[1]);
 
    //lots of code to greet, initialise, draw the array and move the tiles... Not yet how A_star is called.
 
       typedef struct s_noeud{
        int jeu[d][d];
        struct s_noeud *next;
    } t_noeud;
 
}

Autre question plus théorique, je ne comprends pas pourquoi en dissociant "jeu" et "structure permettant de manipuler différents jeux" tu transformes une entité de complexité "N" en "2" entités de complexité "N/2".

Merci pour votre aide en tout cas!

[Sve@r]

Autre question plus théorique, je ne comprends pas pourquoi en dissociant "jeu" et "structure permettant de manipuler différents jeux" tu transformes une entité de complexité "N" en "2" entités de complexité "N/2".

C'est juste une façon de parler. Plus facile (enfin de mon point de vue) de manipuler d'un coté une simple liste de trucs et de l'autre coté un jeu 2D plutôt qu'un tableau 3D représentant le jeu 2D dans différents êtats...