Théorie des graphes

Derrière ce nom un peu barbare de "théorie des graphes" qui nous provient des mathématiques, se cache en réalité un ensemble d'outils très ancrés dans le réel. Ces outils sont particulièrement intéressants en informatique, car ils permettent de résoudre énormément de problèmes.

Un graphe permet de modéliser des entités (qu'on appelle sommets ou nœuds) en interactions. Ces interactions sont représentées par des liens entre les sommets, et on appelle ces liens des arêtes.

Les sommets, ainsi que les arêtes, d'un graphe peuvent avoir des propriétés (qu'on retrouve parfois sous le nom de label dans la littérature).

Les arêtes peuvent être orientées. On les appelle alors des arcs ou des flèches.

Bon... c'est bien gentil tout ce vocabulaire, mais concrètement, ça sert à quoi un graphe ? À pleins de choses, pardi ! Un exemple très classique, c'est le graphe d'un réseau routier : les sommets seront les intersections, et les arêtes seront les routes. Des arêtes ? Pas tout à fait : il est plus pertinent d'avoir ici des arcs pour représenter les routes qu'on ne peut emprunter que dans une seule direction à cause des sens interdits. On pourra aussi ajouter à nos arcs des labels correspondants aux vitesses maximales et aux longueurs des routes.

L'avantage d'avoir des graphes pour représenter un réseau routier, c'est qu'ensuite, on va pouvoir utiliser énormément d'algorithmes "prêt à l'emploi" pour résoudre les problèmes qu'on pourrait avoir avec ce réseau routier. Typiquement, on voudra sûrement calculer des plus courts chemins. Et là, bingo ! on va pouvoir implémenter un algorithme de Dijsktra :)

Et dans Leek Wars, ça peut servir à quoi ? Pour commencer, il est possible de représenter la carte avec un graphe. Déjà, vous pourrez gagner quelques opérations lorsque vous voudrez faire un getPath si vous utilisez un algorithme plus efficace que celui proposé nativement. Ensuite, vous pourrez plus facilement gérer les puces saut et téléportation avec une structure en graphe.

Parmi les algorithmes connus de plus court chemin, on retrouve le célèbre algorithme de Dijsktra dont on a déjà parlé, mais il en existe d'autres, comme l'algorithme A*.

Votre recherche des cellules accessibles pourrait aussi bénéficier de l'algorithme de parcours en largeur (ou BFS, pour Breadth-First Search en anglais).

Pour des utilisations plus avancées, certains éleveurs utilisent des structures de graphes particulières, qu'on appelle des arbres), et qui leur permettent de générer les suites d'actions possibles.