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.

Parcours en largeur

La recherche en largeur explore de manière uniforme dans toutes les directions.

C’est un algorithme incroyablement utile, pas seulement pour la recherche de chemin, mais aussi pour la génération procédurale de carte, la mesure de topologie et d'autres types d'analyse.

Cela peut être l’algorithme de choix pour identifier les lieux d’intérêt proches dans le GPS.

L'algorithme BFS garantit le chemin le plus court.

Parcours en profondeur

Traverse en explorant autant que possible chaque chemin avant de revenir en arrière.

Aussi importante que la recherche en largeur, celle-ci peut être utilisée pour générer un ordre topologique, construire des arbres de descisions, générer des labyrinthes, découvrir un workflow avec des choix hiérarchiques, détecter un cycle dans un graphe...

L'algorithme DFS ne garantit pas le chemin le plus court.

Dijkstra

L’algorithme de Dijkstra nous permet de hiérarchiser les chemins à explorer. Au lieu d’explorer tous les chemins possibles de la même manière, il privilégie les chemins les moins coûteux.

Nous pouvons attribuer des coûts bas pour encourager les déplacements sur les routes tout en attribuant des coûts élevés aux déplacements sur autoroute pour les éviter.

Il est l'algorithme de choix pour trouver les chemins le chemin le plus court avec plusieurs destinations.

A* (A-Star)

A* est une modification de l’algorithme de Dijkstra optimisé pour une seule destination.

L’algorithme de Dijkstra peut trouver des chemins vers tous les emplacements; A* trouve des chemins vers un endroit. Il priorise les chemins qui semblent se rapprocher d'un objectif.

Dans un jeu, nous pourrions faire la même chose pour être attirés ou découragés de s'approcher de certains objets; c'est dire à quel point cela est utile pour une IA ;)

C'est plus ou moins l'algorithme standard (de premier choix) pour trouver rapidement un itinéraire entre deux lieux.
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