Optimizing Algorithms that you use in your Game

Why should we consider the complexity of every single algorithm that we implement? Because we can! Or, more seriously: Because writing a good algorithm right from the start can save you the time of modifying it later on, when you realize that you suffer from performance issues.

Of course you should distinguish certain cases, i.e., it does not make much sense to optimize algorithms that are not called at run-time. Also, there is always a trade-off between readability and maintainability of your code and the performance speed-up that is gained by optimizations.

As far as AI pathfinding is concerend, e.g., I compute a ternary relation that stores the shortest paths from one square to another. As the walls of a map don't change during a match, this information can be computed as a preprocessing and might be saved together with the map. (This is work in progress and will be found in the algorithms section once it is finished).

However, things are different in the pathfinding for pieces of energy that try to take the shortest (pipeline) path to your base: Pipelines change during the game and thus we have to update our knowledge about shortest paths to the base in every call of our Update-method. Below, I give a theoretic characterization of the problem together with an algorithm that solves it in linear time. (For those that are not familiar with the Lambda notation for computation complexity: linear time means 'fast'.)

Speaking of algorithm optimization I want to make one last remark: In Shawn's wonderful perfromance introduction 'Why measure when we can guess?' we learn that the effort only makes sense if we are CPU-bound. And even if this is the case, it is a good idea to identify (not by guessing!) those algorithms which make the bottleneck of your game and optimize them and only them.


Your ElecTons shortest Paths to your Base

Once you connect your base with an energy source, the game has to know the shortest path to your base, so the ElecTons may flow into the right direction. In the following picture, there are two different paths available. The shorter one contains dots that represent flowing ElecTons.



Now how do we abstract from our game board to consider anf compare different ways to compute such a shortest path? In computer science, a navigation problem based on a set of different locations with connections in between of them is usually modeled as a graph G = (V,E), where V denotes the set of nodes (i.e., the locations) and E denotes the set of edges (i.e., the connections between nodes).
Graphs are a very well-studied strucutre. It is common knowledge that Dijkstra's algorithm allows us to compute the shorest paths from to all nodes from a single souce in O(nē), where n is the number of nodes. So a first idea would be to reverse all edges, i.e., to interpret the base as the source and the energy sources as the sinks, which does not make any difference to the shortest paths, and to compute the shortest paths for our three base squares. As 3 is only a constant factor, this approach works in O(nē).

However, considering our pipeline structure more closely reveals our graph structure is not at all generic: Two tower squares (the darker ones in the picture) are connected with line squares (the brighter ones in the picture) if and only if they are in the same line or column and have at most three (non-occupied) squares in between of them. Additionally (what I hitherto concealed) our job is not only to compute the shortest paths in every clock cycle of the game, but we also have to refresh the pipeline strucutre:
Note, that we only want line squares to emerge between a pair of tower squares, if the condition stated above holds and one of the towers is already connected to the base.
So the task we want to perform efficiently contains both defining the present line squares (after having deleted the old line squares in every update) and computing a shortest path to the base for each square.
It is obvious that both tasks are closely related, because in order to find out, whether a certain square is a line square (and may thus be used on a path) we have to find out, whether lies in between to towers, where for one of them there exists already a path to the base.
If we already had constructed the line squares, our task would be simple enough: For graphs, in which all edges have length 1, one may use breadth-first search to solve the single-source-shortest-paths problem.
As only tower squares may alter the direction of an ElecTon that is flowing through, we may at first abstract from line squares and only take tower squares into account for V. We still apply the idea of reversing all edges and start to compute the shortest paths from our base squares to all others with the very simplest algorithm available on graphs, i.e., breadth-first search.

We start our breadth-first search in the base and give all base nodes the distance value 0. Starting with the three base squares in the queue we check for each square whether it is a tower square or a line squares.
For tower squares we check all four neighbor directions (for up to four steps) and establish the corresponding line squares. Then (starting again in For line squares (that do not allow a change of direction) we simply head on to the next square into our present direction and add the neighbour (which must exist because a line square cannot be a dead end) to the queue after storing the incremented basePathLength and forwarding the presentDirection.

Check this file for the C# implementation of the modified breadth-first search approach. DetermineConnectionsAndShortestBasePaths.cs

There are some pitfalls when deleting line information and recomputing it. Given two pairs of towers of different teams, e.g., that would build a 'crossroads' the question which pair of towers yields a connection depends on which pair was there first. There is no need to store that information but to keep things in order we must not delete all line squares at the same time. Instead we delete and recompute the line information team by team. (This is why we call the method DetermineConnectionsAndShortestBasePaths with a team as a parameter.)