Methods of path-finding
Base requirements
Graphs
In order to represent the map in a way the AI program can understand, I created a graph. A graph contains a set of nodes, which have data such as their co-ordinates in the game space, travel cost, and traversability. A path-finding algorithm will run fastest with the least number of nodes, due to the fact that less processing is required.
The algorithm can use the nodes of the graph to get AI positions relative to the graph, and to move AI to positions on the graph. Each node will have a parent node, so it can reconstruct the path back to the origin.
Breadth-First Search
The breadth-first search algorithm searches equally in all directions, which can be used both for AI, and in other applications such as procedural generation. On a grid this method may also be called "Flood Fill" as it checks progressively outwards from the origin unless the path has already been visited. Even if it finds the target node, the algorithm will not exit early, making the algorithm very unoptimised.Early Exit
Breadth-first search is currently able to find paths to all nodes on the grid, which can be useful, but makes the algorithm slow. In order to make the algorithm faster, it can exit early, meaning once it finds its target node it stops and uses the first path it finds. However, this may not be the quickest path for the AI to follow.
Dijkstra's Algorithm
Movement Costs
Movement costs can be added to the nodes on the grid, for instance on hills or rivers that we either want the AI to have a preference to avoid or to move slowly across them. Dijkstra's algorithm takes into account movement costs by checking each new path's total movement cost with the current path's - if it's lower, then the new path becomes the current path and so forth.Optimisation problems
Dijkstra's algorithm only takes into account the cost relative to how far it is away from the start position, the highest cost and untraversable paths are then put into a "checked" list so they don't get processed more than one time. What the algorithm doesn't take into account is the distance from the target node, so the algorithm could check nodes leading away from the target. This also makes it so the path is the shortest in terms of distance from the start node.
Heuristic Search
In order to get the algorithm searching for a path in the direction of the target node rather than in all directions, we use "Greedy best first search". We can find the distance from each node using Pythagoras - square root(the difference in x coordinates, squared) + (the difference in y coordinates, squared). Greedy best first search uses the distance from the target rather than the start in order to prioritise the checking of nodes. However, this algorithm doesn't work as well when there's a lot of obstacles in the way.
A* Algorithm
The A* algorithm improves obstacle avoidance and the checking of less promising areas by using both the distance from the start and the distance from the target to find the optimal path. It simply adds each distance cost and chooses the node with the lowest cost. This means the path tries to stay as short as possible.