Sommaire

Exemple en cartographie

Pour étudier les différents algorithmes, nous allons nous intéresser à un petit jeu dans lequel nous contrôlons un personnage qui est un explorateur. Comme dans beaucoup de jeux de rôle, notre héros est limité à chaque tour (il n’a le droit qu’à un certain nombre de points d’action). Pour aller le plus vite d’un point à un autre, nous cherchons le chemin le plus court sur la carte, en prenant en compte les types de terrains.

Il en existe de plusieurs sortes, requérant plus ou moins d’énergie (et donc de points d’action) :

  • Des chemins, qui nécessitent un point d’action par case.

  • De l’herbe, nécessitant deux points d’action.

  • Des ponts, nécessitant deux points d’action.

  • De l’eau, infranchissable.

  • Et des arbres, infranchissables aussi.

La carte est la suivante :

images/03DP09.png

Et la légende :

images/03DP10.png

Nous cherchons donc le chemin permettant de relier le départ (D) à l’arrivée (A), et ce en utilisant le moins de points d’action possible. Le chemin le plus court coûte 27 points d’action (en suivant le chemin et en passant le premier pont, puis en coupant par l’herbe à la fin).