# 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**.

<Mermaid
  chart={`flowchart LR
    A((A)) --- B((B))
    A --- C((C))
    B --- D((D))
    C --- D
    D --- E((E))`}
/>

| 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_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.

<Mermaid
  chart={`flowchart LR
    D((départ<br/>0)) --> a1((1)) & a2((1)) & a3((1))
    a1 --> b1((2)) & b2((2))
    a2 --> b3((2))
    a3 --> b4((2)) & b5((2))`}
/>

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.

| 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
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.

| 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
priority = new_cost + heuristic(n, goal)
heapq.heappush(frontier, (priority, n))
```

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

<Mermaid
  chart={`flowchart LR
    subgraph bfs [Parcours en largeur]
      b["priorité = ordre de découverte"]
    end
    subgraph dij [Dijkstra]
      d["priorité = coût depuis le départ"]
    end
    subgraph ast [A*]
      a["priorité = coût depuis le départ<br/>+ estimation jusqu'à l'arrivée"]
    end
    bfs --> dij --> ast`}
/>

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

<Mermaid
  chart={`flowchart TB
    q1{Les déplacements ont-ils<br/>des coûts différents ?}
    q1 -- non --> bfs[Parcours en largeur]
    q1 -- oui --> q2{Je cherche un chemin<br/>vers une seule destination ?}
    q2 -- oui --> astar[A*]
    q2 -- non --> dij[Dijkstra<br/>toutes les cases atteignables]`}
/>

## 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.deque` | `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é](/algorithmes/complexite).

## À 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 ?
