A* Pathfinding Algorithm

Pathfinding

Have you ever wondered how one can find the shortest possible path from point A to point B? The easiest way to find out would be to explore and memorize every possible path that exists and pick the shortest one out of that list. That is called the Dijkstra’s Algorithm. But that is a very time-consuming and slow process for both humans and computers. And that’s why the A* Algorithm exists. Here’s a comparison:

How A* works:

Here’s the map I used above. Let’s make it smaller for better understanding:

The core idea behind this algorithm is that for every neighboring spot of your current position you set a score for the distance it is away from the starting point (G cost, top left number) and the distance from the target point (H cost, top right number).

You take the sum of that evaluation, which we can define as F cost (middle large number), compare F cost score of every neighbor and pick the neighboring spot with the lowest score i.e. the spot that is the best choice to explore next. Rinse and repeat until you find the target spot.

There is a Wikipedia page about the A* algorithm which has an implementation of it in pseudocode, which I took as reference when building my version of it in p5.js: