Cost-Driven and Heuristic-Driven

Cost-Driven and Heuristic-Driven

Figure 2: AI 101 – PART 10 – A* SEARCH (Thompson, 2016)

To understand how pathfinding works, we first need to explore how routes are calculated and what the factors are that need to be considered. Efficiency is the what makes us choose one algorithm over another. In pathfinding, efficiency is measured by finding the route costs, distance travelled, and time taken. For example, if the application is for satellite navigation, then cost would consider traffic jams, number of lanes on a road and the speed limit. Distance travelled is simply the length of the route from one node to another. When we consider it for pathfinding for AI, we want the AI to move to a target such as the player in the shortest time, and hope that it doesn’t take a bizarre route. In the above image [fig. 2], it illustrates route costs and paths to get from Arad to Bucharest. This shows three types of algorithms: cost-driven, heuristic-driven and A* Search. Cost-driven is a type of heuristic function that looks at route nodes and sorts its destination by route cost. This can often very quickly find the best path, but not always the best one. An example of a cost driven algorithm is the best-first algorithm. This algorithm searches the cheapest paths first to reach its goal.

As can be seen, a cost-driven algorithm won’t always pick the fastest route only the one that is cheapest.

Heuristic-driven algorithms, as annotated by the green line, consider the distance from the target. Using the map as an example, the heuristic driven algorithm will take the path: Arid > Sibiu > Fagaras > Bucharest. This is because these are nodes are closest to the target. For example, from Sibiu, Fagaras is closer than Rimnicu Vilcea to Bucharest, so the heuristic-driven algorithm chooses Faragas as the next node to search. (Thompson, 2016).