What is A* algorithm?
A* (A star) Search algorithm is one of the best and popular technique used in path-finding and graph traversals.
Informally speaking, A* Search algorithms, unlike other traversal techniques, it has “brains”. What it means is that it
is really a smart algorithm which separates it from the other conventional algorithms.
It is also worth mentioning that many games and Google Maps (and others) use this algorithm to find the shortest path very
efficiently
I leave the Wikipedia documentation and also this useful link where you can dig deeper.
Explanation
In the example below we have a square grid having many obstacles (the black squares) and we are given a starting cell (top left)
and a target cell (bootom right). We want to reach the target cell (if possible) form the starting cell as quickly as possible
moving in all 8-ways.
At each step A* needs to determine which of its paths to extend. It does so based on the cost of the path and an estimate of the
cost required to extend the path all the way to the goal. Specifically, A* selects the path that minimizes:
\[f(n) = g(n) + h(n)\]
where:
- nis the next node on the path
- g(n) is the cost of the path from the start node to n
- h(n) is a heuristic function that estimates the cost of the cheapest path from n to the goal.
A* terminates when the path it chooses to extend is a path from start to goal or if there are no paths eligible to be
extended.
Example
In the following example i created a canvas (that is not responsive, so i'm sorry if you can't enjoy it properly on smaller devices) with the current settings:
canvas size of 800x800; each square has size 20x20; obastacle probability 35%, that means that if you reload the page the ostacles will be re-arrangeed differently,
so different paths each time with (almost) the 35% of the squares are black. I set the animation frames at 15 FPS as you can apprecciate it better
The flow of the script is based on this Pseudo-code.
In the canvas you will see the computation of the algorithm at each step that checks its surroundings to find the correct square to move on. As said before, the black are
the obstacles, the withe ones are "free path", the red squares are the squares that the algorithm considers at least once as "current path", the blue are the squares that
A* looks at, but it finds out that has greater cost than the current, so it's not the ideal path and it discards those.
When (if) A* reaches the goal square the shortest path is been highlighted in green.
As usual feel free to check the GitHub repo and play with the settings or
improve the algorithm by finding a better heuristic!
