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éorie | Dans le jeu |
|---|---|
| Sommet | Une case |
| Arête | Deux cases voisines |
| Poids d'une arête | Le coût d'entrée dans la case |
| Voisins d'un sommet | find_ |
La carte du jeu est un graphe : chaque hexagone est relié à six autres. Il n'y a rien à construire, la fonction find_ 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
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
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.
| Avantage | Limite |
|---|---|
| Très simple | Considère que toutes les cases coûtent pareil |
| Trouve le chemin le plus court en nombre de cases | Explore 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
Deux nouveautés :
cost_so_farretient le meilleur coût connu pour chaque case. Une case peut être redécouverte par un chemin moins cher.heapqest une file de priorité : elle rend toujours l'élément le plus petit, rapidement.
| Avantage | Limite |
|---|---|
| Trouve le chemin le moins coûteux | Explore 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
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 largeur | Dijkstra | A* | |
|---|---|---|---|
| Tient compte des coûts | non | oui | oui |
| Sait où est l'arrivée | non | non | oui |
| Structure | File | File de priorité | File de priorité |
| Priorité | Ordre d'arrivée | g | g + h |
| Cases explorées | Beaucoup | Beaucoup | Peu |
| Usage dans le jeu | Construire la carte | Zone de déplacement | Chemin 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
| Structure | Opération clé | Coût | Sert à |
|---|---|---|---|
collections. | popleft() | O(1) | Parcours en largeur |
heapq | heappop() | O(log n) | Dijkstra, A* |
dict | x in d | O(1) | Cases déjà vues |
list | pop(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
- Écrire
bfset 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. - Transformer
bfsendijkstraavecTILES_. Afficher les cases qu'un colon peut atteindre avec 3 points de mouvement.MOVEMENT_ COST - Transformer
dijkstraen A* en ajoutant l'heuristique. Compter les cases explorées par chacun pour le même trajet. - Que se passe-t-il si l'on multiplie l'heuristique par 10 ? Le chemin est-il toujours le meilleur ?