Path Finding

http://wiki.gamegardens.com/Path_Finding_Tutorial

The A* ("A star") algorithm has three important properties:

• It will always return the least expensive path if a path exists to the destination, other algorithms may find a path faster but it is not necessarily the "best" path we can take.
• A* uses a heuristic (a "guess") to search nodes considered more likely to lead to the destination first, allowing us to often find the best path without having to search the entire map and making the algorithm much faster.
• A* is based on the idea that each node has some cost associated with it. If the costs for all nodes are the same then the best path returned by A* will also be the shortest path but A* can easily allow us to add different costs to moving through each node.

A* creates two lists of nodes; a closed list containing all the nodes we have fully explored, and an open list containing all the nodes we are currently working on (the perimeter of our search). Each node will have 3 values associated with it; F, G, and H. Each node will also need to be aware of its parent so we can establish how we reached that node.

G 

the exact cost to reach this node from the starting node.

H 

the estimated(heuristic) cost to reach the destination from here.

F = G + H 

As the algorithm runs the F value of a node tells us how expensive we think it will be to reach our goal by way of that node.

   create the open list of nodes, initially containing only our starting node
   create the closed list of nodes, initially empty
   while (we have not reached our goal) {
       consider the best node in the open list (the node with the lowest f value)
       if (this node is the goal) {
           then we're done
       }
       else {
           move the current node to the closed list and consider all of its neighbors
           for (each neighbor) {
               if (this neighbor is in the closed list and our current g value is lower) {
                   update the neighbor with the new, lower, g value 
                   change the neighbor's parent to our current node
               }
               else if (this neighbor is in the open list and our current g value is lower) {
                   update the neighbor with the new, lower, g value 
                   change the neighbor's parent to our current node
               }
               else this neighbor is not in either the open or closed list {
                   add the neighbor to the open list and set its g value
               }
           }
       }
   }

Selecting an appropriate heuristic is critical in determining the performance A* can achieve.

If we choose a value for H greater than the actual cost of reaching our goal we will allow A* to search faster but less accurately and we can no longer be certain of finding a path to the goal. Therefore we normally want to make certain that H is never accidentally greater than the real cost.

If we select a value of H less than the actual cost A* will always find the best possible path. However the lower our value of H the longer A* will take to complete its search. In the worst case of H = 0 our A* will give the same performance asDijkstra's algorithm

the Manhattan distance:

   H = Math.abs(start.x-destination.x) + Math.abs(start.y-destination.y));

Euclidean distance:

   H = Math.sqrt(Math.pow((start.x - destination.x), 2) + Math.pow((start.y - destination.y), 2));

Dealing with terrain:

If we want to add strictly impassable terrain we will need to prevent A* from considering that node entirely. Depending on our game it might also be helpful to stop our path finder if it cannot find a path less than some maximum cost. This would both prevent the path finder from running for an extended period of time and from returning incredibly long or expensive paths.

We have a second concern as well. If our path finder reaches a position where two equal paths exist to the goal it will explore both of them. To save time we would prefer that A* explore only one of these paths if possible.

http://www.codebytes.in/2015/02/a-shortest-path-finding-algorithm.html
With complete code.
OPEN //the set of nodes to be evaluated
CLOSED //the set of nodes already evaluated
add the start node to OPEN

loop
    current = node in OPEN with the lowest f_cost
    remove current from OPEN
    add current to CLOSED

    if current is the target node //path has been found
        return

    foreach neighbour of the current node
        if neighbour is not traversable or neighbour is in CLOSED
            skip to the next neighbour

        if new path to neighbour is shorter OR neighbour is not in OPEN
            set f_cost of neighbour
            set parent of neighbour to current 
            if neighbour is not in OPEN
                add neighbour to OPEN
http://wiki.gamegardens.com/Path_Finding_Tutorial