Aller au contenu

Parcours de graphe

Trouver un chemin sur une carte, c'est parcourir un graphe. Ce cours présente trois algorithmes, du plus simple au plus efficace. Chacun est une amélioration du précédent.

Le problème

Dans le jeu, une unité ne peut avancer que vers une case voisine. Pour aller plus loin en un clic, il faut que le programme trouve lui-même la suite de cases à traverser.

Qu'est-ce qu'un graphe

Un graphe est un ensemble de sommets reliés par des arêtes.

Dans la théorieDans le jeu
SommetUne case
ArêteDeux cases voisines
Poids d'une arêteLe coût d'entrée dans la case
Voisins d'un sommetfind_neighbors(coo)

La carte du jeu est un graphe : chaque hexagone est relié à six autres. Il n'y a rien à construire, la fonction find_neighbors suffit à le décrire.

Le schéma commun

Les trois algorithmes ont la même structure. Seule change la façon de choisir la prochaine case à explorer.

Python
a_explorer = [depart] vient_de = {depart: None} while a_explorer: courante = prendre_la_suivante(a_explorer) # la seule ligne qui change if courante == arrivee: break for voisin in voisins(courante): if voisin not in vient_de: vient_de[voisin] = courante a_explorer.append(voisin)

vient_de joue deux rôles : il retient les cases déjà vues, et il permet de reconstruire le chemin en remontant de l'arrivée au départ.

1. Le parcours en largeur

En anglais Breadth-First Search, ou BFS. On explore les cases dans l'ordre où on les a découvertes : d'abord les voisines du départ, puis les voisines des voisines.

L'exploration avance comme une vague, en cercles.

Python
from collections import deque def bfs(start, goal, neighbors): frontier = deque([start]) came_from = {start: None} while frontier: current = frontier.popleft() if current == goal: break for n in neighbors(current): if n not in came_from: came_from[n] = current frontier.append(n) return came_from

deque est une file : on ajoute à droite, on retire à gauche, les deux en temps constant. Avec une liste, pop(0) décalerait tous les éléments.

AvantageLimite
Très simpleConsidère que toutes les cases coûtent pareil
Trouve le chemin le plus court en nombre de casesExplore dans toutes les directions

Dans le jeu, la forêt coûte 1.5 et la plaine 1. Le parcours en largeur ne le voit pas.

Où il sert quand même : Map.layers, qui construit la carte anneau par anneau, est un parcours en largeur depuis la case centrale.

2. Dijkstra

On tient compte des coûts. Au lieu de prendre la case découverte en premier, on prend celle dont le coût depuis le départ est le plus faible.

Python
import heapq def dijkstra(start, goal, neighbors, cost): frontier = [(0, start)] came_from = {start: None} cost_so_far = {start: 0} while frontier: _, current = heapq.heappop(frontier) if current == goal: break for n in neighbors(current): new_cost = cost_so_far[current] + cost(n) if n not in cost_so_far or new_cost < cost_so_far[n]: cost_so_far[n] = new_cost came_from[n] = current heapq.heappush(frontier, (new_cost, n)) return came_from, cost_so_far

Deux nouveautés :

  • cost_so_far retient le meilleur coût connu pour chaque case. Une case peut être redécouverte par un chemin moins cher.
  • heapq est une file de priorité : elle rend toujours l'élément le plus petit, rapidement.
AvantageLimite
Trouve le chemin le moins coûteuxExplore encore dans toutes les directions

La vague n'est plus ronde : elle avance vite dans les plaines, lentement dans les forêts. Mais elle part toujours aussi bien vers l'arrière que vers l'arrivée.

Où il sert : pour calculer toutes les cases atteignables avec un nombre de points de mouvement donné, Dijkstra est exactement l'outil. On s'arrête quand le coût dépasse le mouvement disponible.

3. A*

On ajoute une information : dans quelle direction est l'arrivée. La priorité devient le coût déjà payé plus une estimation du coût restant.

Python
priority = new_cost + heuristic(n, goal) heapq.heappush(frontier, (priority, n))

C'est la seule ligne qui diffère de Dijkstra.

L'estimation s'appelle l'heuristique. Sur des hexagones, c'est la distance en cases. Tant qu'elle ne surestime jamais le coût réel, A* trouve le même chemin que Dijkstra en explorant beaucoup moins de cases.

Le détail et le code pour le jeu sont dans la page Le principe de A* de la documentation du jeu.

Comparaison

Parcours en largeurDijkstraA*
Tient compte des coûtsnonouioui
Sait où est l'arrivéenonnonoui
StructureFileFile de prioritéFile de priorité
PrioritéOrdre d'arrivéegg + h
Cases exploréesBeaucoupBeaucoupPeu
Usage dans le jeuConstruire la carteZone de déplacementChemin vers une case

Lequel choisir

Et le parcours en profondeur ?

Il existe un quatrième cousin, le parcours en profondeur, ou DFS. Il utilise une pile au lieu d'une file : il fonce le plus loin possible dans une direction avant de revenir en arrière.

Il ne trouve pas le plus court chemin. Il sert à autre chose : savoir si deux cases sont reliées, ou repérer des zones. Dans le jeu, il pourrait vérifier qu'aucun joueur n'apparaît sur une île coupée du reste par de l'eau.

Les structures qui font la différence

StructureOpération cléCoûtSert à
collections.dequepopleft()O(1)Parcours en largeur
heapqheappop()O(log n)Dijkstra, A*
dictx in dO(1)Cases déjà vues
listpop(0)O(n)À éviter ici

Le choix de la structure n'est pas un détail : avec une liste à la place du tas, A* passerait son temps à chercher le minimum. Voir La complexité.

À retenir

  • Une carte de cases est un graphe : sommets, arêtes, voisins.
  • Les trois algorithmes ont la même boucle. Seule la priorité change.
  • Largeur : nombre de cases. Dijkstra : coût réel. A* : coût réel plus estimation.
  • L'heuristique ne doit jamais surestimer.

Exercices

  1. Écrire bfs et l'utiliser pour compter les cases situées à 3 cases ou moins d'une case donnée. Sur une grille sans bord, il doit y en avoir 37 en comptant la case de départ.
  2. Transformer bfs en dijkstra avec TILES_MOVEMENT_COST. Afficher les cases qu'un colon peut atteindre avec 3 points de mouvement.
  3. Transformer dijkstra en A* en ajoutant l'heuristique. Compter les cases explorées par chacun pour le même trajet.
  4. Que se passe-t-il si l'on multiplie l'heuristique par 10 ? Le chemin est-il toujours le meilleur ?