Recherche de chemin à travers l’algorithme A* en C++ 4/4 : implémentation de l’algorithme A*

Pour installer le projet, il suffit de faire : mkdir build && cd build && cmake ..

Pour le compiler, depuis le dossier build : make

Pour lancer le programme, depuis le dossier build : ./project

Explication de l’architecture

Le monde est défini dans world.hpp et world.cpp, ces fichiers visent à créer une carte aléatoire d’une taille paramétrable avec une densité d’obstacles paramétrable. Ces deux fichiers ne sont pas à modifier. Ce monde est composé de Node qui sont des cases de la carte et possèdent les attributs suivants :

int x;
int y;
int cost_g;
int cost_h;
int cost_f;
int obstacle;
Node *parent;

Les méthodes suivantes sont à votre disposition pour manipuler les Node :

int getX() const;
int getY() const;
int getCostG() const;
int getCostH() const;
int getCostF() const;
int getObstacle() const;
Node *getParent();
void setCostG(int costG);
void setCostH(int costH);
void setCostF(int costF);
void setParent(Node *newParent);

Finalement la fonction int distance(Node *node1, Node *node2); permet de calculer la distance entre 2 nœuds.

Le dossier libAstar contient une implémentation de l’algorithme A* permettant de vérifier si la carte précédemment créée est valide. Il servira aussi d’éléments de corrections. Il n’est pas à ouvrir pendant la séance, sinon cela ne sert à rien.

Les fichiers astar.cpp et astar.hpp sont les fichiers de votre implémentation de l’A*. Seul le fichier astar.cpp doit être modifié. Plus précisément les fonctions initialize et findPath sont à implémenter obligatoirement. Vous pouvez rajouter autant de fonction que vous voulez dans les fichiers astar.cppet astar.hpp. Certaines fonctions utilitaires sont déjà implémentées dans astar.cpp et astar.hpp. Vous pouvez les utiliser ou non. Les signatures des fonctions initialize et findPath sont déjà définies dans astar.hpp et ne doivent pas être modifiées. findPath doit obligatoirement remplir les 3 vecteurs (path closed_list et open_list) avec les coordonnées des cases parcourues, les coordonnées des cases ouvertes et les coordonnées des cases fermées.

Le fichier main.cpp s’occupe de générer une carte, de vérifier qu’un chemin existe et de fournir cette carte à votre algorithme puis de vérifier votre chemin. Il affiche la carte, le chemin que vous avez calculé et les différentes listes dans un fichier map.ppm

Manipulation des matrices et des lignes avec des vecteurs

Pour simplifier l’écriture des types, nous avons défini les types suivants :

typedef std::vector<std::vector<Node*>> nodeMatrix;
typedef std::vector<Node*> nodeList;

Quelques fonctions utiles

// Taille d'un element
element.size()
//  Rajout d'un element
element.insert(place, newNode);
// Suppression d'un element
element.erase(place);
// Ajout d'un élément à la fin
element.push_back(newNode);
element.emplace_back(newNode);

Accéder à un élément

// Pour une matrice
nodeMatrix matrix;
matrix[i][j]

// Pour un pointeur de matrice 
nodeMatrix *matrix;
matrix->at(i).at(j)

// Pour une liste
nodeList list;
list[i]

// Pour un pointeur de liste
nodeList *list;
list->at(i)

Rappel de l’algorithme A*

Le nœud de départ est le nœud courant, le nœud de départ doit avoir un costG nul, un costH égal à la distance par rapport à l’arrivée et comme parent nullptr. Il est ajouté à la liste ouverte et fermée.

Vision 1

Tant que l’on n’est pas à destination :

• On cherche tous les voisins du nœud courant en éliminant les obstacles
• pour chaque voisin : si le voisin n’est pas dans la liste fermée, on calcule son costF, met à jour son parent et on l’ajoute à la liste ouverte s’il n’y est pas déjà. S’il est déjà dans la liste ouverte, on vérifie si le nouveau costF est meilleur que celui existant. Si c’est le cas, on met à jour le nœud dans la liste ouverte.
• On cherche dans la liste ouverte le nœud avec le costF le plus faible, s’il n’y en a pas l’algorithme s’arrête, il n’y a pas de solution.
• Sinon, ce nœud devient le nouveau nœud courant, on l’ajoute le nœud dans la liste fermée et on le retire de la liste ouverte.

On remonte la chaine de parents jusqu’à la case de départ en plaçant chaque noeud dans la liste de chemin.

Vision 2

Tant que la liste ouverte n’est pas vide :

• On cherche tous les voisins du nœud courant en éliminant les obstacles
• pour chaque voisin : si le nœud n’est pas dans la liste fermée, on calcule son costF, met à jour son parent et on l’ajoute dans la liste ouverte s’il n’y est pas déjà. S’il est déjà dans la liste ouverte, on vérifie si le nouveau costF est meilleur que celui existant. Si c’est le cas, on met à jour le nœud dans la liste ouverte. Si l’un des voisins est la destination, on a trouvé un chemin.
• On cherche dans la liste ouverte le nœud avec le costF le plus faible, on le met dans la liste fermée et on le retire de la liste ouverte. Ce nœud devient le nouveau nœud courant.

Si on a trouvé le noeud de destination, on remonte la chaine de parents jusqu’à la case de départ en plaçant chaque noeud dans la liste de chemin. Sinon l’algorithme s’arrête, il n’y a pas de solution.