multi_array qui produit un SIGABRT

**chindit** · 27/09/2014, 19h10

Salut à vous tous

Je suis en train de mijoter sur un générateur de labyrinthe tout simple.
Le principe de mon algo est simple: Je commence en 0,0 et je me déplace dans une des cases adjacente disponible.
Une fois bougé, je marque la case comme «occupée» et je continue à me déplacer dans une de nouvelles cases adjacente libre (l'algo ne repasse jamais 2x au même endroit).
S'il n'y a plus de case adjacente disponible, je recule de 1 et je regarde s'il y a une case disponible. Si oui, j'avance, si non, je continue à reculer.
Une fois revenu au point de départ, le labyrinthe est généré.

Comme vous le voyez, le processus est très simple, ce n'est pas quelque chose de très élaboré (on verra ça plus tard). Je veux d'abord que ça marche.

Pour stocker mon labyrinthe, j'utilise un multi_array de Boost.
Ce multi_array fait [largeur][hauteur][5] et est de type bool
Dans chaque case, j'ai donc 5 booléens qui valent
0)Visité (facultatif mais j'aime bien)
1)HAUT
2)BAS
3)GAUCHE
4)DROITE

Chaque case étant à «false» si la «porte» de la cellule est fermée et à «true» si elle est ouverte.

Bon… je viens de vous baratiner pendant un p'tit tas de lignes et je ne vous ai toujours pas dit ce qui coinçait, mais j'y viens.
Ce générateur de labyrinthe a la fâcheuse manie de provoque une «SIGABRT» lorsqu'il arrive dans une case touchant un bord du tableau.
Vous allez dire «bah, il sort des limites, c'est tout»… ben non… J'ai vérifié et contre-vérifié tout le code 5 fois et je n'arrive toujours pas à comprendre pourquoi il génère un SIGABRT…

Mais trève de bavardage, voici mon code:
Le .h d'abord

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
35
36
#ifndef GENERATOR_H
#define GENERATOR_H
 
#include <boost/multi_array.hpp>
#include <list>
#include <map>
#include <iostream>
#include <cstdlib>
 
 
class Generator
{
    public:
        enum class direction{HAUT, BAS, GAUCHE, DROITE};
 
        Generator();
        virtual ~Generator();
    protected:
    private:
        //Déclarations du type du MultiArray
        typedef boost::multi_array<bool, 3> multiArray;
 
 
        void genereChemin();
        void resetDirections();
        void findBorders();
        void findVisited();
 
        //Création des deux multiArray
        multiArray labyrinthe, labyrintheDos;
        std::list<std::pair<int, int> > chemin;
        std::map<Generator::direction, bool> directions;
        std::pair<int, int> position;
};
 
#endif // GENERATOR_H

Puis le .cpp

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
#include "Generator.h"
 
Generator::Generator(){
    //Variables de taille, pour le moment aléatoires
    int const longueur(5), largeur(5);
 
    //Initialisation de rand
    srand(time(NULL));
 
    labyrinthe.resize(boost::extents[longueur][largeur][5]);
    labyrintheDos.resize(boost::extents[longueur][largeur][5]);
 
    for(int i=0; i<longueur; ++i){
        for(int j=0; j<largeur; ++j){
            for(int k=0; k<5; ++k){
                labyrinthe[i][j][k] = false;
                labyrintheDos[i][j][k] = false;
            }
        }
    }
    int larg = labyrinthe
    this->resetDirections();
    this->genereChemin();
}
 
Generator::~Generator(){
    //dtor
}
 
void Generator::genereChemin(){
    //On part toujours du coin supérieur gauche
    chemin.push_back(std::make_pair(0, 0));
    position = std::make_pair(0, 0);
    labyrinthe[0][0][0] = true; //La première case est visitée
 
    //Tant qu'on est pas revenu au début, on poursuit la génération
    while(!chemin.empty()){
        //Le principe est simple, on avance toujours et quand on ne peut plus, on recule
        //On remet le bordures à zéro
        this->resetDirections();
 
        //Délimitation des bordures
        this->findBorders();
 
        //Élimination des cases visitées adjacentes
        //HINT : Accepter une case visitée dans 20% des cas!
        this->findVisited();
 
        bool avancer = false;
        std::map<Generator::direction, bool>::iterator it;
        while(!avancer){
            //On fait des tours de boucle tant qu'on ne peut pas avancer
            for(it = directions.begin(); it != directions.end(); ++it){
                if(directions[it->first]){
                    avancer = true;
                    break;
                }//Fin IF
            }//Fin FOR
            if(!avancer){
                //Si on est ici, c'est qu'il est impossible d'avancer
                this->resetDirections();
                //On vérifie qu'on est pas revenu au début
                if(chemin.empty()){
                    return;
                }
                chemin.pop_back();
                position = chemin.back();
                //On recherche les bordures
                this->findBorders();
                //Et les cases visitées
                this->findVisited();
            }
        }//Fin WHILE
 
        //S'il est possible d'avancer, on tire une direction au hasard
        Generator::direction wayToGo;
        bool ok = false;
        //Tant que la direction n'est pas OK, on retire
        while(!ok){
            wayToGo = static_cast<Generator::direction>(rand() % (static_cast<int>(Generator::direction::DROITE)+1));
            if(directions[wayToGo]){
                    //Si la direction est bonne, on la garde
                ok = true;
            }
        }
        //Si on est ici, c'est qu'on a une direction donc, on bouge!
        switch(wayToGo){
        case Generator::direction::HAUT:
            //On change la position
            position = std::make_pair(position.first, position.second-1);
            chemin.push_back(position);
            //Et on visite les cases
            labyrinthe[position.first][position.second][0] = true;
            labyrinthe[position.first][position.second][2] = true; //BAS (vu qu'on monte)
            labyrinthe[position.first][position.second-1][1] = true; //HAUT
            break;
        case Generator::direction::BAS:
            position = std::make_pair(position.first, position.second+1);
            chemin.push_back(position);
            //Visite des cases
            labyrinthe[position.first][position.second][0] = true;
            labyrinthe[position.first][position.second][1] = true; //HAUT
            labyrinthe[position.first][position.second+1][2] = true; //BAS
            break;
        case Generator::direction::GAUCHE:
            position = std::make_pair(position.first-1, position.second);
            chemin.push_back(position);
            //Visite des cases
            labyrinthe[position.first][position.second][0] = true;
            labyrinthe[position.first][position.second][4] = true; //DROITE
            labyrinthe[position.first-1][position.second][3] = true; //GAUCHE
            break;
        case Generator::direction::DROITE:
            position = std::make_pair(position.first+1, position.second);
            chemin.push_back(position);
            //Visite des cases
            labyrinthe[position.first][position.second][0] = true;
            labyrinthe[position.first][position.second][3] = true; //GAUCHE
            labyrinthe[position.first+1][position.second][4] = true; //DROITE
            break;
        default:
            std::cerr << "ERREUR fatale" << std::endl << "La direction choisie est invalide" << std::endl;
            exit(EXIT_FAILURE);
            break;
        }
    }
    return;
}
 
//Remet toutes les directions à TRUE
void Generator::resetDirections(){
    directions[direction::HAUT] = true;
    directions[direction::BAS] = true;
    directions[direction::GAUCHE] = true;
    directions[direction::DROITE] = true;
    return;
}
 
//Trouve les bordures du labyrinche
void Generator::findBorders(){
    if(position.second == 0)
        directions[direction::HAUT] = false;
    if(position.second == 4)
        directions[direction::BAS] = false;
    if(position.first == 0)
        directions[direction::GAUCHE] = false;
    if(position.first == 4)
        directions[direction::DROITE] = false;
    return;
}
 
//Trouve les cases visitées aux alentours de la case actuelle
void Generator::findVisited(){
    std::map<Generator::direction, bool>::iterator it;
    for(it = directions.begin(); it != directions.end(); ++it){
        switch(it->first){
        case direction::HAUT:
            if(directions[it->first]){
                if(labyrinthe[position.first][position.second-1][0]){
                    directions[direction::HAUT] = false;
                }
            }
        break;
        case direction::BAS:
            if(directions[it->first]){
                if(labyrinthe[position.first][position.second+1][0]){
                    directions[direction::BAS] = false;
                }
            }
        break;
        case direction::GAUCHE:
            if(directions[it->first]){
                if(labyrinthe[position.first-1][position.second][0]){
                    directions[direction::GAUCHE] = false;
                }
            }
        break;
        case direction::DROITE:
            if(directions[it->first]){
                if(labyrinthe[position.first+1][position.second][0]){
                    directions[direction::DROITE] = false;
                }
            }
        break;
        default:
            std::cout << "ERREUR*FATALE" << std::endl << "Exception de direction trouvée" << std::endl;
            exit(EXIT_FAILURE);
        } //Fin du SWITCH
    }//Fin du FOR
}

Si vous voulez tester le code, le plus simple est de mettre 4 breakpoints. Un à chaque case du «switch(wayToGo)». (lignes 93, 101, 109, 117)
Le problème survient généralement à cette ligne:

Code :

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

 labyrinthe[position.first][position.second][0] = true;

Et je vous avoue que je n'ai vraiment aucune idée d'où peut bien provenir ce fichu SIGABRT.

Pour les tests, le labyrinthe fait 5x5 donc en moins de 10 mouvements, le programme plante.

Et pour info, il est nécessaire d'activer la norme «C++11» dans le compilateur.

Un immense merci à tous ceux qui pourront m'aider.

**Bousk** · 27/09/2014, 21h25

Salut,

plusieurs remarques
- this-> est inutile à préciser
- ce que tu fais ça s'apelle A*
- à quel moment tu testes que la case existe ?

Code :

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

1
2
3
4
5
6
7
 //On change la position
            position = std::make_pair(position.first, position.second-1);
            chemin.push_back(position);
            //Et on visite les cases
            labyrinthe[position.first][position.second][0] = true;
            labyrinthe[position.first][position.second][2] = true; //BAS (vu qu'on monte)
            labyrinthe[position.first][position.second-1][1] = true; //HAUT

où se trouve un quelconque test pour s'assurer que -1 soit correct ?!

Pourquoi ne pas utiliser un debugger ? Au moment du crash, il s'arrêtera et tu pourras avoir toutes les informations nécessaires : callstack, variables, mémoire, ..

**chindit** · 28/09/2014, 11h10

Envoyé par Bousk

this-> est inutile à préciser

Je sais, mais j'aime bien le préciser parce que ça rend le code beaucoup plus lisible.
Je trouve que, en jettant un coup d'œil rapide au code, on voit tout de suite qu'il s'agit d'un appel à une méthode interne.
Puis c'est plus beau qu'un simpel «mafonction();» perdue au milieu de tout.

Envoyé par Bousk

ce que tu fais ça s'apelle A*

Jamais entendu parler de ce machin. C'est quoi au juste?

Envoyé par Bousk

à quel moment tu testes que la case existe ?

Code :

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

1
2
3
4
5
6
7
 //On change la position
            position = std::make_pair(position.first, position.second-1);
            chemin.push_back(position);
            //Et on visite les cases
            labyrinthe[position.first][position.second][0] = true;
            labyrinthe[position.first][position.second][2] = true; //BAS (vu qu'on monte)
            labyrinthe[position.first][position.second-1][1] = true; //HAUT

où se trouve un quelconque test pour s'assurer que -1 soit correct ?!

Relis le code, tu verras que c'est prévu.
D'abord, on accepte toutes les directions (HAUT, BAS, GAUCHE, DROITE).
Ensuite, la méthode «this->findBorders()» élimine les cas qui feraient «sortir» le générateur du tableau. Grâce à cette méthode, je suis donc certain que la case existe.

Envoyé par Bousk

Pourquoi ne pas utiliser un debugger ? Au moment du crash, il s'arrêtera et tu pourras avoir toutes les informations nécessaires : callstack, variables, mémoire, ..

Mais je l'ai fait.
Et j'ai dit dans mon post que ça bloquait à telle ligne et toujours lorsque le générateur est au bord du tableau.
J'ai vu le contenu des variables en mémoire et elles indiquaient du genre «labyrinthe[4][0][0]», qui est une case qui existe.
Mais même avec toutes ces informations du débugger… je suis incapable de comprendre ce qui coince.

**Ehonn** · 28/09/2014, 11h32

Envoyé par chindit

Je sais, mais j'aime bien le préciser parce que ça rend le code beaucoup plus lisible.
Je trouve que, en jettant un coup d'œil rapide au code, on voit tout de suite qu'il s'agit d'un appel à une méthode interne.
Puis c'est plus beau qu'un simpel «mafonction();» perdue au milieu de tout.

Tu peux utiliser la convention suivante :
- les noms des données membre protected ou private commencent par m_, s_ si static, r_ pour une référence, p_ pour un pointeur, ...
- la distinction fonction libre et fonction membre se fait grâce aux namespace.

Envoyé par chindit

Jamais entendu parler de ce machin. C'est quoi au juste?

http://fr.wikipedia.org/wiki/Algorithme_A*

**chindit** · 28/09/2014, 13h18

J'ai fini par trouver le bug…
Finalement, je sortais bien du tableau.
Parce que je bougeais de case, puis je modifiais la case suivante qui n'avait, normalement, pas encore été choisie.

Such a shame…

Et merci à vous pour l'aide.

multi_array qui produit un SIGABRT

Boost C++

Discussions similaires

Partager

Partager