Bonjour,
Je dois programmer une "IA" permettant de donner les solutions à un petit jeu avec un personnage qui part de la case en haut à gauche de la grille pour aller en bas à droite de cette dernière en se déplaçant entre les éventuels blocs que le personnage peut pousser lors de son déplacement.
Comme état pour ce problème j'ai considéré la configuration de la grille à un instant donné. Ainsi, j'ai commencé par implémenter l'algorithme de recherche en profondeur d'abord pour résoudre ce problème. Tout marche bien et j'obtiens bien une solution.
J'utilise une matrice à 2 dimensions pour stocker la grille . Compte tenu de la place importante prise en mémoire par ce stockage je me demande quelle est la meilleure solution pour ressortir la solution au problème.
J'hésite entre construire le graphe d'état correspondant durant la recherche en profondeur d'abord ( en liant le père au fils et le fils au père pour pouvoir en partant du père afficher facilement les différentes configurations possibles)
ET entre stocker les déplacements possibles dans une liste que je mets à jour au fur et à mesure de la recherche en profondeur d'abord.
Bien sur, je n'aurais pas le même résultat dans les deux cas puisque d'un côté je pourrais afficher les différents configurations de la grille avec les déplacements et dans l'autre solution juste la liste des déplacements ayant conduits à la grille solution.
Mais ce n'est pas un problème, mon problème ça serait de savoir ce qui serait le mieux au niveau de la place occupée en mémoire notamment.
Qu'en pensez vous ? et si vous avez une idée d'une meilleure solution, n'hésitez pas.
merci d'avance.
Partager