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

Jul 02 2018, 4:04 PM PST 5 min

A* ( pronounced A star ) is a pathfinding algorithm that uses heuristics to reach its goal. A* will combine the Articles/Best First Search method of calculating the probable distance left from the current node to the finish with the distance from the start to the current node like in Articles/Dijkstra s Algorithm.

Heuristics

The heuristics is of A* is usually represented by
F = G + H
where

G is the movement cost from the start to the current node along the path.

H is the probable cost from the current node to the finish along the path.

Procedure

  1. From current node, find the neighboring nodes (all moveable nodes that aren’t in the closed set) and insert them into the open set. If node is already in the open set, then check if the G cost for that node is lower if we use the current square to get there. If it is, change parent node to the current node. If not, do nothing.
  2. Find the node from open set with the least cost based on F = G + H.
  3. Take newly found node from open set to closed set.
  4. Repeat until finish is found in the open set

Pseudo Code

--searching `map`
function A_star(start, finish)
    closed = {}
    open = {}
 
    open[start] = true
 
    --start is the start so it has a g of 0
    start.g = 0
    --h calculated normally
    start.h = estimated_cost_between(start, finish)
    --f = g + h
    start.f = start.g + start.h
 
    while #open > 0
        current = node in open with minimum f
        if current == finish then
            --reconstruct the path to goal
            return create_path(current)
        end
        closed[current] = true
        open[current] = nil
 
        for _, v in ipairs(current:neighbors()) do 
            if not closed[neighbor] and not open[neighbor] then
                neighbor.g = current.g + current:distanceTo(neighbor)   --g is distance from start along path
                neighbor.h = estimated_cost_between(neighbor, finish) --h is estimated distance from node to finish along path
                neighbor.f = neighbor.g + neighbor.h                    --f=g+h
                open[neighbor] = true
            end
        end
    end
end
Tags:
  • pathfinding
  • concept
  • lua