Quel est le trajet le plus court pour le parc le plus proche ?
Comment pouvons-nous trouver notre chemin à travers un labyrinthe ?
Peut-on programmer un personnage de jeu pour sortir du bunker en évitant les ennemis?

Les algorithmes de recherche de chemins traitent le problème de trouver un chemin partant d'une source vers une destination tout en évitant les obstacles et minimisant les coûts (temps, distance, risques, carburant, prix, etc.). Il s’agit d’un défi courant en matière de programmation. Principalement connus dans la navigation et les jeux vidéos, nous découvrirons que ces algorithmes sont utilisés dans tous les domaines.

Pour une brève introduction sur les labyrinthes et pourquoi nous les aimons tant, prière de se référer à l'article 'Introduction aux générateurs de labyrinthe'.

Nous étudierons pour commencer la recherche en largeur ainsi que la recherche en profondeur car elles sont fondamentales pour traverser un graphique (ou un arbre) et sont souvent une première étape requise pour de nombreux autres types d’analyses. Nous aborderons ensuite des algorithmes plus avancés tels que Dijkstra ou A* (A-Star).

Et ensuite?

Au final, la plupart des développeurs qui manipulent des données/graphes finissent par écrire leur propres parcours, tous fortement basés sur ces solutions connues pour s'adapter aux contextes plus particulilers. Nous pourrons écrire nos propres algorithmes de résolution de labyrinthes en utilisant par exemple H.urna Core C++ comme projet template clés en mains.

La première chose à faire quand on étudie un algorithme est de comprendre les données.
Quelle est l'entrée ? Quelle est la sortie ?
Voici le genre de structure avec laquelle nous allons jouer.

Comment sont structurées les données?
Voici un labyrinthe avec un peu plus de détails.

Dans cette grille, chaque case représente un noeud. Une connection entre deux noeuds est représentée, elle, par un chemin entre deux cases. Ces informations sont aussi affichées textuellement (encadré haut gauche dans l'image). Ici, notre souris est sur le premier noeud (0,0) et affiche des connexions avec les noeuds (0,1) et (1,0).

Nous avons choisi de décrire notre grille (ou graphe) à l'aide d'une structure de données en liste d'adjacence (adjacency lists). L'idée est plutôt simple : un tableau de noeuds avec chaque noeud stockant la liste de leurs voisins connectés. Facile à créer, facile à manipuler, voici comment les données pourraient être représentées en JSON:

[
  {
    "x":0, "y":0,
    "neighbors":[1,5]
  }, {
    "x":0, "y":1,
    "neighbors":[0,2]
  }, {
    "x":0, "y":2,
    "neighbors":[1,3,7]
  }
  ...
] 

L'identifiant de noeud est donné par son index de tableau, cet identifiant est utilisé pour faire référence aux voisins.
Oui, c’est aussi simple que cela ! Cela contient toutes les informations nécessaires pour visualiser et parcourir le labyrinthe.

Quelle est sortie?

Le résultat auquel on peut s’attendre est le chemin trouvé entre deux nœuds. Un tableau ordonné (par ordre de pas) semble suffisant:

[0, 3, 19, 9, ...]

En partant du noeud 0, nous allons au noeud 3, puis au noeud 19, etc. jusqu'au but.

Parfait, nous savons tout ce qu'il faut pour construire nos recherches!

Remarque: une grille peut utiliser un algorithme de parcours de graphe et inversement.
Ici, les grilles (nos labyrinthes orthogonaux) sont utilisées car elles sont plus faciles à comprendre, à travailler et à visualiser; cependant le principe reste exactement le même.

Fournit un bon résumé des algorithmes de recherche de chemin classiques.

Pour mieux comprendre les différences entres ces algorithmes et leurs fonctionnements, utilisez H.urna Explorer : notre plateforme intéractive, qui vous permettra de les manipuler et les comparer

• Wikipedia