What is A Star Algorithm?

A* algorithm is a search algorithm usually used in path finding. It guarantees to find a complete and optimal path if there is one (the target is not surrounded by walls on all sides). Since it is an informed search, we have the control over where the target is and the distance between each nodes.

Why did I do it?

A* algorithm is one of the most frequent algorithms that I used during my undergraduate study. The map system for the hospital app, robot which explores the maze, and other projects all uses A* for path finding. Since I lost access to most of the project code, I would really like to rewrite the algorithm. I could also use this algorithm in the future projects if needed.

How did I do it?

I first implemented A* on nodes connected with edges. This was represented using a graph. I used priority queue for the algorithm because this data structure perfectly blends with A*'s property(v.0.1.0 release on GitHub).

Part 2

A* is cool in action. I decided to visualize the A* using a simple interactive UI. The Swing library was my first UI library, it's enough for a simple UI to use.

The Program

(The start of the program.)

(When we click on the Manual A* button, it proceeds with 1 step of A* search.)

(This is A* auto mode. This finds the path with 1 click.)

Time & Space Complexity

Time Complexity

In the worst case scenario, the time complexity is O(b^d), where b is the branching factor, and d is the depth of the solution. The branching factor is how many nodes we are comparing in an iteration. The depth is the the minimum number of nodes we need to take to reach the target(shortest path). The time complexity is exponential, because each node has 4 (or 8 if including diagonal nodes) neighbors to expand.

Space Complexity

The space complexity is the same as Time Complexity; O(b^d).