wilvart
Messages postés47Date d'inscriptionsamedi 7 janvier 2006StatutMembreDernière intervention13 décembre 2012
-
29 oct. 2012 à 15:45
cptpingu
Messages postés3837Date d'inscriptiondimanche 12 décembre 2004StatutModérateurDernière intervention28 mars 2023
-
13 déc. 2012 à 14:05
Salut tout le monde !
Je suis en train de coder un algo de A* pour résoudre le jeu du sokoban.
Je n'ai pas de problème particulier avec l'algo en lui même mais plutôt avec les variables que j'utilise.
Mon problème est simple, je crée des Node contenant un chemin possible (avec un poids, un cout, etc...) et je les push_back dans 2 std::list différentes. Lorsque je pousse le premier tout va bien, mais ensuite (et sans aucune volonté de ma part) les Node contenu dans ces listes deviennent du grand n'importe quoi...
Je pense que j'utilise mal les std::list mais je ne suis pas sûr. J'ai donc coder l'algo de nouveau (from scratch) mais je me retrouve encore avec le même problème...
Tout le code et les fichiers textes sont ici : http://quentin.rubis.free.fr/Sokoban_solver.rar Le tout dans un projet code blocks. Le reste des fonctions marchent correctement et servent à lire les fichiers textes pour la map etc...
cptpingu
Messages postés3837Date d'inscriptiondimanche 12 décembre 2004StatutModérateurDernière intervention28 mars 2023123 13 déc. 2012 à 14:05
Salut.
- Diviser mes fonctions aStar est pour le moment 'optionnel', le code fonctionne et c'est un gros changement que je préfère éviter la tout de suite :) Mais ça viendra pour sur !
Ma remarque portait en fait plus sur le fait qu'il faut toujours penser son code en petite fonction, avant de coder. Ce qui est fait, est fait, et ce n'est pas la priorité de refactoriser ton code. Ton choix me parait pertinent.
Par exemple getPath(), j'ai essayer de lui faire retourner une référence de list au lieu d'une copie. J'ai un jolie segFault.
J'ai regardé "getPath" dans node.cpp:64 ainsi que "lowerWeightNode->getPath()" aStartDiamond.cpp:139, et il y a pour moi des petits soucis.
Si on prend ta fonction: "std::list Node::getPath();" Tu retournes par copie tout le tableau. Ce qui n'est pas top. J'aurais plus vu quelque chose dans le genre de: "const std::list& Node::getPath();".
Bien évidemment à la reception, il ne faut pas faire l'erreur suivante:
"const std::list list truc.getPath();". Ici, malgré le fait d'avoir mis une référence en sortie de getPath il y aura aussi copie. La bonne écriture serait: "const std::list & list truc.getPath();".
Vu que tu n'as fait aucun des deux, il y aura téhoriquement même double copie.
Maintenant, les dégâts sont limités par le fait que le compilateur, qui est intelligent, repère ce genre de cas, et a tendance à l'optimiser et à mettre de lui même la référence oubliée. Néanmoins je pense que c'est tout de même un souci, notamment pour le problème de mémoire que tu as.
Ce type de problème n'est pas limité à getPath(), par exemple "addNewMovement()" est aussi impacté.
2ème type de problème:
"std::list addNewMovement(const std::list& oldPath, const std::list& path);"
Si tu changes en:
"const std::list& addNewMovement(const std::list& oldPath, const std::list& path);"
Tu éviteras la copie mais tu auras potentiellement un problème. Renvoyer la référence d'une variable temporaire, peut te provoquer pas mal de soucis. Et donc cette méthode est bancale.
Je conseille dans ce cas l'écriture:
"void addNewMovement(std::list& newPath, const std::list& oldPath, const std::list& path);"
Et tu écris dans newPath, au lieu de retourner quoi que ce soit.
3ème problème:
Le 2ème type de problème est ultra vicieux, car il y a en C++, une particularité très peu connue. Écrire: "const std::list& addNewMovement(const std::list& oldPath, const std::list& path);" fonctionnera !
En effet, si tu retournes une référence sur un objet temporaire, ce n'est jamais valide sauf s'il est récupéré en tant que "const&" ! C'est vraiment un petit détail très avancé.
En d'autre terme:
"const std::list& res = addNewMovement(//..." fonctionnera, tandis que:
"std::list& res addNewMovement(//..." ou "const std::list res addNewMovement(//..." provoqueront des erreurs de mémoires.
- Le dernier problème, la mémoire. J'ai bien delete les nodes avant de supprimer leurs pointeurs de mes listes, et la différence est là, mais j'ai encore des fuites que je ne sais pas boucher. D'après valgrind elles seraient au même endroit.
Cf point précédent, à mon avis c'est lié :)
- J'ai fais un Makefile qui ne recompile que ce qui a été modifié,
Ah merci. Ça n'a l'air de rien, mais c'est pratique pour moi ^^
je pense que c'est pas extrêmement utile pour un petit projet comme le mien mais ça fait propre !
En fait, un makefile, tu l'écris une seul fois, bien complet, qui fait tout proprement, et après tu le réutilises dans tous tes projets. Je t'invite à regarder dans mes sources comments en faire un qui gère les dépendances (notamment via g++ -MM). N'hésite pas à prendre des makefile déjà fait. Par exemple, le tien actuellement, est plus long que ce qu'il devrait (tu te répètes beaucoup).
________________________________________________________________________
Historique de mes créations, et quelques articles:
[ http://0217021.free.fr/portfoliohttp://0217021.free.fr/portfolio]
Merci d'utiliser Réponse acceptée si un post répond à votre question