# Best-First Search

Aug 29 2019, 9:31 AM PST 5 min

Best-first search is a pathfinding algorithm that uses heuristics to reach its goal. Best-first search is the basic form for all heuristic search algorithms. It contains both an open and closed set, then explores the node with the least cost first.

### Heuristics

There are many different heuristics that can be used for a best-first search. Usually you will want to adapt which heuristic you use based on the type of map you’re using.

#### Manhattan Distance

The Manhattan Distance is taking the distance from going all the way on the X axis and adding that to the distance all the way on the Y axis to go from point A to point B. This heuristic should usually be used whenever the AI can only move in the 4 cardinal directions.

``````movement_cost = math.abs(node.x-end.x)+math.abs(node.y-end.y)
``````

#### Chebyshev/Diagonal Distance

The Chebyshev Distance is used whenever you’re allowed to move in diagonally, so in 8 directions. Assuming both straight and diagonals cost the same, this code should work sufficiently.

``````movement_cost = math.max(math.abs(node.x-end.x),math.abs(node.y-end.y))
``````

#### Pythagorean Distance

The Pythagorean Distance is the most common form of distance, and is used when you can move in all directions:

``````movement_cost = math.sqrt((node.x-end.x)^2 + (node.y-end.y)^2)
``````

### Procedure

• Take the best node from the open set ( based on heuristic cost ) and add it to the closed set.
• If the node is the goal, trace back to start from that node.
• Otherwise add the neighboring nodes to the open set that are movable and aren’t in the closed set.
• Repeat until the end is found or no possible options.

### Pseudo Code

``````function best_first(start, finish)
closed = set({})
open = set({start})

score_of = {}
score_of[start] = calculate_heuristics(start)

while not open.is_empty do
-- find node with minimum f
current = min(open, function(node) return score_of[node] end)
if current == goal then
--reconstruct the path to goal
return create_path(current)
end
open.remove(current)

for neighbor in current:neighbors() do
if not closed.contains(neighbor) then
--calculate the heuristics for neighboring node
score_of[node] = calculate_heuristics(neighbor)
--add neighboring node to open set