A* Algorithm, A Simple Explanation

Let’s dive into A*, a clever yet easy to grasp pathfinding algorithm.

Photo by Tamas Tuzes-Katai on Unsplash

Description

The A* algorithm is a pathfinding algorithm that works on any 2D graph or grid. Given a starting point and a destination, it will compute and return the shortest path between the two — if one exists — and avoids any obstacles on the way. This algorithm is often used in video games.

Brief explanation

The algorithm uses a clever way of functioning. From the starting point, each possible path — the neighbours from the starting point — is evaluated and given a score. Then the point with the lowest score is taken, and the process starts again and again until the point assessed is the destination.

Score calculation

The score given is a combination of two things:

• the distance from the starting point to the current point, often called g
• A heuristic, is the estimation of the remaining distance between the current point and the destination. We call it h. The distance can be calculated in many…