**A-Star (š“*)**

Dijkstraās Algorithm is used for finding the shortest path in a graph where edgesā/arcsā weights are already known. Dijkstraās algorithm is a special form of dynamic programming and it is also a breadth first search method. The basic idea behind is to keep a running cost for nodes and pick the lowest cost one in the frontier to explore until you reach the goal.

**Dijkstraās Pseudocode**

**A-Star (š“*)**

A-Star (š“*) is an extension of Dijkstraās algorithm, which reduces the total number of states by introducing a heuristic estimation of the cost from the current state to the goal state. Cost function is given by

š(š„) =š(š„) +ā(š„) , where š(š„) is the cost from start state to current state š„, ā(š„) is the heuristic estimation of the cost of an optimal path from current state š„ to goal state. š(š„) is the total cost of the node.

**Steps:**

1) Add the starting square (or node) to the open list.

2) Repeat the following:

a) Look for the lowest F cost square on the open list. We refer to this as the current square.

b) Switch it to the closed list.

c) For each of the 8 squares adjacent to this current square ā¦

If it is not walkable or if it is on the closed list, ignore it. Otherwise do the following.

If it isnāt on the open list, add it to the open list. Make the current square the parent of this square. Record the F, G, and H costs of the square.

If it is on the open list already, check to see if this path to that square is better, using G cost as the measure. A lower G cost means that this is a better path. If so, change the parent of the square to the current square, and recalculate the G and F scores of the square. If you are keeping your open list sorted by F score, you may need to resort the list to account for the change.

d) Stop when you:

Add the target square to the closed list, in which case the path has been found (see note below), or Fail to find the target square, and the open list is empty. In this case, there is no path.

3) Save the path. Working backwards from the target square, go from each square to its parent square until you reach the starting square. That is your path.

**A* Pseudocode**

Following the example below, you should be able to implement A* in any language.

// A* (star) Pathfinding// Initialize both open and closed list

let the openList equal empty list of nodes

let the closedList equal empty list of nodes// Add the start node

put the startNode on the openList (leave itās f at zero)// Loop until you find the end

while the openList is not empty // Get the current node

let the currentNode equal the node with the least f value

remove the currentNode from the openList

add the currentNode to the closedList // Found the goal

if currentNode is the goal

Congratz! Youāve found the end! Backtrack to get path // Generate children

let the children of the currentNode equal the adjacent nodes

for each child in the children // Child is on the closedList

if child is in the closedList

continue to beginning of for loop // Create the f, g, and h values

child.g = currentNode.g + distance between child and current

child.h = distance from child to end

child.f = child.g + child.h // Child is already in openList

if child.position is in the openListās nodes positions

if the child.g is higher than the openList nodeās g

continue to beginning of for loop // Add the child to the openList

add the child to the openList

**A* vs Dijkstraās**

Dijkstraās is essentially the same as A*, except there is no heuristic (H is always 0). Because it has no heuristic, it searches by expanding out equally in every direction. As you might imagine, because of this Dijkstraās usually ends up exploring a much larger area before the target is found. This generally makes it slower than A*.