Aaaaaand we back, with another gamedev-log, this time we focus on the algorithm that we talked about last time, the pathfinding used by the enemies to track the player down. This devlog will be a bit different because it would also be kind of a tutorial, I'll try to explain how I've implemented the basic algorithm of pathfinding and you can then use that too.

So, first of all some terminology, in this "tutorial" I'll use the terms BFS (Breadth First Search) and DFS (Depth First Search) when I'll need to refer to the algorithm that perform the pathfinding for the enemies.

BFS

This algorithm is the one that we are currently using and is capable of finding the shortest path between two cells. This algorithm is usually used and explained in relation to trees, but with some adaptation we can use it in a matrix (like the one of ProjectAlpha).

The BFS basically work by searching in each neighobur of a cell if taht neighbour is the destination, if not that cell is added to a queue and the process is repated for each element in the queue until the destination is found, otherwise there is no path to the destination cell. We always have to keep track of visited cells because otherwise it would loop forever on the same cells.

Then, in order to find, the path, we save every neighbour cell in a dictionary where the key is the "parent": the cell from wich we come; when we find the destination we travel back in the dictionary until we reach the start, in this way we have the shortest path.

In a grid it basically spread in it's entirety until it finds the destination, there the final result:

DFS

This algorithm is very similar to BFS, in fact it is basically the same, except that instead of using a queue it uses a stack. In this way instead of populating the entire grid and moving towards the destination almost with all the cells togheter, this one focuses on the "head" cell and goes as far as it can with that one. Here is the final result with same grid as the one used before:

As you can see in our case the DFS doesn't find the shortest path to the destination, it just finds a path. In a situation like a maze this would be good enough, but in our case this algorithm is not our best solution.

The good part

And here we have the part of the code that does all the magic, as you can see it's not that big nor complex:

public List<IBoardCell> GetPath(int row1, int col1, int row2, int col2)

{

Dictionary<IBoardCell, IBoardCell> previous = new Dictionary<IBoardCell, IBoardCell>();

HashSet<IBoardCell> visited = new HashSet<IBoardCell>();

Queue<IBoardCell> queue = new Queue<IBoardCell>();

queue.Enqueue(this.board.BoardCells[row1, col1]);

int iterations = 0;

while (queue.Count > 0)

{

var current = queue.Dequeue();

if (visited.Contains(current))

continue;

visited.Add(current);

foreach (var neigh in this.GetCellNeighbour(current.Row, current.Column))

{

if (!visited.Contains(neigh))

{

queue.Enqueue(neigh);

if (!previous.ContainsKey(neigh))

previous.Add(neigh, current);

}

}

iterations++;

}

List<IBoardCell> path = new List<IBoardCell>();

var prev = this.board.BoardCells[row2, col2];

while (prev.Row != row1 || prev.Column != col1)

{

path.Add(prev);

prev = previous[prev];

}

path.Add(prev);

path.Reverse();

return path;

}

If you have any questions, as always leave a comment or contact us on our socials.

cya next time.