# A* Pathfinding

Aug 29 2019, 9:29 AM 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