PcoWSkbVqDnWTu_dm2ix
We use cookies on this site to enhance your user experience

Best-First Search

Best-First Search

Jul 05 2018, 3:52 PM 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
        closed.add(current)
        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
                open.add(neighbor)
            end
        end
    end

    -- there is no path to the goal
end
Tags:
  • pathfinding
  • algorithms
  • coding
  • concept