Bonjour à tous

Voilà, depuis le TP de matéo sur mario sokoban j'ai l'habitude de représenter mes map dans un double tableau appelé niveau.

Or je rencontre actuellement un problème pour implémenter ça en C++.

Comment créer un double tableau en attribut si on ne connais pas a l'avance la taille du tableau (sachant qu'on donne sa longueur et sa largeur dans le constructeur)?

Je réussit en trichant en faisant des #define mais bon, j'aimerais rendre mon algo (A*) le plus générique possible.

Merci d'avance

doubles pointeurs.

Utilise les vector.

Vector de vector plus précisément

std::vector< std::vector< int > > niveau;

Après tu le remplis, avec tes données

D'accord merci.

Et pour initialiser ce double vector, peut on faire quelque chose comme :

Constructeur::Constructeur(std::vector< std::vector< int > > map)
{
   std::vector< std::vector< int > > niveau =map
}

Si ce n'est pas possible, comment utiliser une double boucle avec les double vector ?

std::vector< std::vector<int> > map

map.resize(nombre_lignes);
for(int t=0; t<map.size(); t++)
{
map[t].resize(nombre_colonnes);
}
Comme ca tu initialise ton tableau.
L'accès : map[x][y].

Par contre peut etre que j'ai inversé entre lignes et colonnes (mas c'est pas trop grave...)

Salut,
pour c'est un tableau ND, il faut mieux utiliser un tableau 1D qui sera une représentation "a plat" de ton tableau.

Pour un tableau 2D, tu créé un tableau de taille Height*Width et accède à l'élément (x,y) en faisant y*width + x

Hum, je trouve qu'il est plus simple, d'utiliser quelque chose comme :

tableau[i][j]

Ca me semble plus facile pour faire des interraction avec.

En tout cas merci pour vos réponses, mon problème est résolus !

Et bien pas si résolus que ça en fait

J'ai tenté ta méthode d'initialisation darktib mai j'ai eu un peu de mal a la mettre en place.

En y reflechissant j'ai trouvé un moyen beaucoup plus simple : créer un pointeur !

J'ai donc un attribut map dans ma classe implémenter comme ça :

std::vector< std::vector<int> > *map;

Et mon constructeur est devenu :

A_Star::A_Star(std::vector< std::vector<int> > *niveau,
               int largeur,int hauteur,
               int depart_x,int depart_y,
               int arrivee_x,int arrivee_y) : largeur_map(largeur),
                                              hauteur_map(hauteur),
                                              pos_depart_x(depart_x),
                                              pos_depart_y(depart_y)

{
    arrivee.x=arrivee_x;
    arrivee.y=arrivee_y;

    map=niveau;
}

Or maintenant j'ai un problème dans l'utilisation de l'attribut map dans mes méthodes (comme map est devenu un pointeur ça change tout).

Voici ce que me dit le compilo :

Citation : compilo

||=== algo, Debug ===|
C:\Documents and Settings\rrazpo\Bureau\Programmes\algo\astar.cpp||In member function `void A_Star::ajouter_cases_adjacentes(std::pair<int, int>&)':|
C:\Documents and Settings\rrazpo\Bureau\Programmes\algo\astar.cpp|82|error: no match for 'operator==' in '(((A_Star*)this)->A_Star::map + (+(((unsigned int)i) * 12u)))->std::vector<_Tp, _Alloc>::operator[] [with _Tp = std::vector<int, std::allocator<int> >, _Alloc = std::allocator<std::vector<int, std::allocator<int> > >](((unsigned int)j)) == 1'|
||=== Build finished: 1 errors, 1 warnings ===|

Qui plante à cette ligne là :

if ( map[i][j] == OBSTACLE)

Je ne sais pas trop comment on gère l'écriture d'un pointeur d'un vector de vector donc j'en appelle à votre aide

pourquoi un pointeur sur un vector ? Quel intéret ?

Une référence (constante) lors des passages de paramètres sera tout aussi efficace et beaucoup plus simple à programmer.

Sinon, tu dois faire une magouille du genre:

if(map->operator[](i)[j] == OBSTACLE){}

beaucoup trop compliqué.

Citation : Nanoc

pourquoi un pointeur sur un vector ? Quel intéret ?

Une référence (constante) lors des passages de paramètres sera tout aussi efficace et beaucoup plus simple à programmer.

Pour ma défense, je ne me suis encore jamais réellement servis des références donc je ne suis pas trop à l'aise avec

Sinon, merci pour ta réponse, une référence constantes marche parfaitement ici !

En revanche je trouve une autre erreur cette fois ci dans mon main, et cela doit venir du fait d'une incompréhension de la structure d'un double vector.

Voici le bout de code qui provoque un segmentation fault :

std::vector< std::vector<int> > map;
    map[0][0]=0;
    map[1][0]=0;
    map[2][0]=0;
    map[0][1]=0;
    map[1][1]=1;
    map[1][2]=0;
    map[2][2]=0;

Ce n'est pas comme ça qu'on peut initialiser ?

Non, car ton vecteur n'a pas de case allouées à ce moment là. Regarde bien le tuto de Nanoc, tu comprendras sûrement.

Indice clef : allocation/taille.

Oui c'est vrai c'était un vector de taille zéro

J'ai lu la partie du tuto de Nanoc sur les double vector, mais en fait il nous explique tout sauf la réponse à mon problème

Car bon, je veut bien faire resize sur les deux vector pour ensuite assigner des valeurs, mais ils n'existe pas de push_back avec les double vector ?

Pour moi l'interet des vector est d'être redimmensionnable.

Tien,
voici une des raison d'utiliser un tableau 1D au lieu de 2D..
L'initialisation et garantir que ton tableau à le m^me nombre de colone à chaque ligne

"push_back avec les double vector" est tout à fait faisable, mais tu dois avoir un vector temporaire de la taille voulue.

Sinon tu peux "aplatir" ton vecteur en une seule dimension.

Citation : mongauloi

Tien,
voici une des raison d'utiliser un tableau 1D au lieu de 2D..
L'initialisation et garantir que ton tableau à le m^me nombre de colone à chaque ligne

Oui bon, ok

C'est comme ça qu'on apprend de toute façon Si je n'avais pas testé je n'aurai pas compris pourquoi cela engendrerai un problème.

Bon ba ça l'air de marcher (pas mon algo mais la structure de donné qui contien ma carte ^^).

Merci beaucoup pour vos réponses !

En fait je vois que tu fais un alog astar...

Ca dépend du type de matrice que tu utilise (creuse ou pleine).
Perso j'ai développé une librairie de recherche de path avec Astar (signature) et si tu utilise une matrice creuse tu n'as qu'a prendre un vector tout simple.
Par contre si tu veux une matrice pleine le code que je t'ai donné est normalement bon (je l'utilise dans mon plugin par exemple et ca marche tres bien)

Ah, et j'ai retrouvé une bon tuto sur les vector :
http://glinfrench.apinc.org/article.php3?id_article=73

Heu, quel est la différence entre matrice creuse et pleine ?

Citation : darktib

Perso j'ai développé une librairie de recherche de path avec Astar (signature)

Alors là j'ai halluciner, ça a l'air d'être vachement bien ta dll (dommage que je ne sache pas m'en servir mais bon xD). Félicitation ça n'a pas du être simple

Merci pour ton lien je vais le regarder.

Merci.

Pour l'utilisation a moins d'avoir DarkBASIC pro tu ne pourra pas l'utiliser...

Enfin, du moins pour l'instant. Dans 1 ou 2 mois, en fonction de mon temps libre, je sortirai la version anglaise - et la version C++ en passant.

edit : une matrice pleine est une matrice dont tu ne crée pas les cases. Il s'agit généralement d'un tableau a deux dimensions. Si jamais tu as un map tres grande la matrice peut etre gigantesque et prendre une place énorme (et les calculs seront plus lents)
une matrice creuse est une matrice a laquelle tu ajoute les cases manuellement. L'algo est plus dur, la matrice prendra de toute facon beaucoup de place si tu as beaucoup de données a enregistrer. Ce genre de matrice est peut adapté a certains types d'utilisation. Les systemes d'octree sont plus durs a coder avec ces matrices (et moins efficients)

@Darktib:
Pour tes définitions de matrice pleines et creuses, tu es à coté de la plaque. Matric creuse == Matrice avec beaucoup de 0 dedans. Matrice pleine == matrice avec beaucoup de cases non-nulles. Ensuite, c'est vrai qu'on implémente parfois les matrices creuses sous formes de map, mais pour le moment, je crois que c'est couper les cheveux en 4 vu le problème originel posé.

Ah, ok. Pour les noms alors j'ai faux... mais pas pour le principe. Par contre j'ai vu beaucoup de personnes utilisant ces termes, donc je doute que les termes soient vraiment inadaptés.

Citation : Nanoc

je crois que c'est couper les cheveux en 4 vu le problème originel posé.

Sans doute^^