Best First Search - Falmouth-Games-Academy/comp250-wiki GitHub Wiki

Overview

Heuristic value,
Determines the new routes forth,
Traverse till goals found

While an Uninformed Search essentially searches a tree blindly, a Best-First Search selects new nodes to explore based on a measure of the node's value in finding the goal. A function of some sort is used to determine the value of nodes and the algorithm usually explores the highest value (closest to goal) node first. While this form of search can be vastly more efficient than Uninformed searches, the reliability of Best-First Searches is largely determined by the heuristic used to determine the cost of nodes.

Greedy Best-First Search

The most basic implementation of a best-first search is a greedy search. This algorithm always chooses the node with the best value, without considering the total value of previous nodes explored [3]. The value is often the distance to the destination. This means that while at first, the search will head in the direction that appears to be the best, it may have missed much better paths that could only be reached by a node with a low value.

Because of this, it can be a very unreliable algorithm, especially in complex trees. However, in cases where situation causes the heuristic values to present a clear and unobstructed route to the goal, a best-first search can be a very fast algorithm.

A* Search

The most well-known best-first search algorithm is A* Algorithm. It is used for autonomous agents' pathfinding and by choosing nodes and finding the best and shortest way from point A to point B. A* pathfinding is usually understood as navigation in 2D or 3D space [Cite needed]. It first started as a simple algorithm, but due to its simplicity, it's been expanded to "cope with large, deceptive spaces ... including hierarchical versions of S*, real-time heuristic search, jump point search for uniform-cost grids, 3D pathfinding algorithms, planning algorithms for dynamic game worlds that enable the animation of crowds in collision-free paths and approaches for pathfinding in navigation meshes." As an example, it is being used in one of the biggest MMORPGs - World of Warcraft (Blizzard Entertainment, 2005) - for both enemies and NPCs.

However, it can also be used for planning rather than simply navigating through the world [1]. This can be much more effective and it's been evidenced in 2009 Mario AI Competition [1].

References