Pathfinding - Preliminaries

Although from a didactic point of view it might be nice to do some easy stuff first, our AI will be utterly useless without a possibility to find its way to, e.g., the next power-up it wants to collect.

Pathfinding is pretty much the same problem in any kind of game. Let us consider a Squar map from above and compare it to a map in an FPS. A bot that wants to determine the best way from room A to room B has exactly the same problem to solve as our tank:



The fact that one could almost call pathfining an academic discipline of computer science might be a little bit disincentive to people who are not familiar with the area, so it is a good idea to cheer us all up a little with this video of pathfinding issues in modern games.



Note: The video was made by ai-blog and is part of a very instructive pathfinding discussion.

So although we all had a good laugh now we also learned that pathfinding is still a problem, even for AAA titles and the professional programmers behind them. My statement from above - that pathfinding was pretty much the same problem in any kind of game - is the key to our success: Find out what makes your game different from others and use these differences to your advantage. Especially if you are developing an indie game gives you a good chance that things are different in your game.

In the case of Squar we have two major characteristics:
a) Given the map editor and the fact that the user may generate maps on his/her own maps means that we can not use static waypoints that we determine ourselves but need an algorithmic solution.
b) Although a Squar map may be compared to a floorplan in an FPS, our obvious advantage is that we only have 15x15 (i.e. 225) squares in our gameboard.

The naive way to benefit from aspect b) would be to use 225 waypoints - one for the center of each square. Let us try and take this approach.

Using waypoints we would abstract from the gameboard and define a graph with 225 nodes that represent (the centers of) our squares. We introduce an edge between every pair of neighbor nodes. If one of the nodes is a wall, we give the edge the distance value infinite, otherwise we give it the distance value 1.

However, if we only use the orthogonal neigbor relation, we will encounter a problem, namely, we will no longer be able to detect shorter ways that "cross a room diagonally". As a consequence we cannot decide whether to take the white or the red path in the following picture. Even if we apply string pulling afterwards, we will have a bad solution if we start out with the red one.



The solution to this problem is to inroduce edges also for pairs of squares that are diagonal neighbors. The adequate weight of such an edge would be the square root of 2, but as we want to avoid floating point operations we will simply use the weight 2 for orthogonal neighbors and 3 for diagonal ones. This is exact enough as our paths will always be relatively short and so the sum over the "inaccuracies" will be small.

So our distnace matrix with which we start out for our graph computations can be sketched as follows...



This matrix will allow us to compute the following shortest path



and with string pulling we finally get...



So our final task is to put our information so far in an adequate data structure. For easy and fast access to our distance information we will use two-dimensional array distance[,]. While the class GameBoard.cs in Squar refers to a square by its row and column we want to refer to a sqaure by a a single index, so we enumerate the 225 squares (starting with 0) from left to right and top to bottom. We supply methods to compute row and column from an index and an index from row and column.
As we often want to have a neighbor of square we define an enumeration of neigbor relations together with a function that returns a corresponding neighbor. This makes our code easy to read later on.



Given the auxiliary methods from above we can finally initialize our distance matrix as follows.