A*

Analysis

A* is a Breadth First Search Algorithm that searches for shorter paths.

A* uses the formula f = g + h durings it's course.

• G is the cost of moving from one node to the other node and is the least cost from one node to the next node
• H is the heuristic path between the current node to the destination node.
• F is the parameter of A* which is the sum of G and H.

With the above variables we can explain the algorithm:

• 1. Within a grid, we set a start-node and end-node.
• 2. We initialise two arrays, openSet and closedSet.
• 3. We push the startNode to OpenSet.
• 4. For all neighbouring nodes, find the least cost F node
• 5. We push the current Node to the closedSet
• 6. We loop through the current neighbours
• a. If a neighbour is the endNode, we stop.
• b. If a neighbour is a wall, or already in the closedSet, we skip.
• c. neighbour.g = neighbour.g + 1 (all nodes have a distance of 1 in our implementation)
• d. If a neighbour with a lower g (+ 1 distance) exists in the openSet, skip this neighbour.
• e. We calculate the distance from the parent to neighbour by calling the heuristic function

Time complexity

It may takes us to travel the entire edge of the graph to reach the destination node. So the worst case time complexity is O(n), where n is the number of edges in the graph.