==== A* search algorithm ====

This is probably the most common path finding algorithm used in games, as it is relatively fast. It makes use of a heuristic, which cuts down on computation time through estimation. The algorithm will look to each possible move and measure how far it is from the current position and how far it is from the target position. At each point it will make the optimal choice to move closer to the target. You can expand on the algorithm by adding additional metadata which impacts the cost of different moves.

**Visual Representation of A***

{{:design_pattern:null-op-astart.jpg?250|A* algorithm in action}}

**Pseudo code**
<code>
create priority queue of open nodes, initially contains starting node
create a set of closed nodes, initially empty
while (open nodes is not empty) {
    current node = best node from open nodes
    add current node to closed set
    if (current node == target node) break

    for (neighbor in current node) {
        if (neighbor node is in closed set 
                and current cost to neighbor < cached cost to neighbor) {
            remove neighbor from closed
        }
        if (neighbor node is in open queue 
                and current cost to neighbor < cached cost to neighbor) {
            remove neighbor from open
        }
        if (neighbor is not in open or closed) {
            neighbor.parent = current
            neighbor.cached cost = current cost
            neighbor.weight = calculateWeight(neighbor, target)
            add neighbor to open queue
        }
    }
}
</code>

==== See Also ====

  * [[Grid]]
  * [[Path Finding]]

==== References ====

  * [[http://www.anotherearlymorning.com/2009/02/pathfinding-with-a-star/|Another Early Morning - Pathfinding with A*]]
  * [[http://www.cokeandcode.com/pathfinding|Path Finding on Tile based Maps with A* - Coke And Code]]