Graph theory

Behind this slightly daunting name of "graph theory", which comes to us from mathematics, actually hides a set of tools that are very much rooted in the real world. These tools are particularly interesting in computer science, because they let you solve a huge number of problems.

A graph lets you model entities (called vertices or nodes) that interact with each other. These interactions are represented by links between the vertices, and these links are called edges.

The vertices, as well as the edges, of a graph can have properties (sometimes found under the name of label in the literature).

Edges can be directed. They are then called arcs or arrows.

Well... all this vocabulary is nice, but concretely, what is a graph good for? For loads of things, of course! A very classic example is the graph of a road network: the vertices are the intersections, and the edges are the roads. Edges? Not quite: it's more relevant here to use arcs to represent roads that can only be taken in one direction because of one-way streets. We can also add to our arcs some labels for the maximum speeds and the lengths of the roads.

The advantage of using graphs to represent a road network is that, afterwards, we can use a huge number of "ready-to-use" algorithms to solve the problems we might have with that road network. Typically, we'll surely want to compute shortest paths. And there, bingo! we'll be able to implement Dijkstra's algorithm :)

And in Leek Wars, what can it be used for? To start with, you can represent the map with a graph. For one thing, you'll be able to save a few operations when you want to do a getPath if you use an algorithm more efficient than the one offered natively. Then, you'll be able to handle the Jump and Teleportation chips more easily with a graph structure.

Among the well-known shortest-path algorithms, we find the famous Dijkstra's algorithm we already mentioned, but there are others, such as the A* algorithm.

Your search for the accessible cells could also benefit from the breadth-first search (or BFS).

For more advanced uses, some breeders use particular graph structures, called trees), that let them generate the possible sequences of actions.