Understanding the pathfinder
The pathfinder is an Artificial Intelligence (AI) algorithm that has the objective of finding the best path between two points in a 2D or 3D world. The algorithm has a graph data structure that uses a set of nodes, and their adjacent connected nodes, to search for the best path.
The pathfinder is commonly used in RTS games, so the selected units and even the enemies can find the best path while avoiding blocks in the way. We are going to get an overview of the pathfinder algorithm and understand how it works.
The Greedy Best-First and A* algorithms
Game worlds can be represented, for example, as a grid of squares or hexes, with every cell being a node. The cell neighbors are the adjacent nodes used to determine the path. In the following figure, we can see the best path that the pathfinder can find from the blue cell to the orange cell, which is just a straight line:
Figure 8.1 – Pathfinding in a direct line
...
