Python: Comprehending A* Path Algorithms and Implementation

The A* algorithm is one of the most effective path-finding algorithms used to find the shortest path between two points. It was first published in 1968 by Peter Hart, Nils Nilsson, and Bertram Raphael [1]. Although it can initially be seen as an extension of Dijkstra’s algorithm, it has become one of the most frequently used pathfinding algorithms today. To access the project directly, please click the provided link.

The A* algorithm basically reaches the optimum result by calculating the positions of all the other nodes between the starting node and the ending node. In addition, it is faster than Dijkstra’s algorithm due to the heuristic function[2].

f(n) = g(n) + h(n)

f(n) : Calculated total cost of path

g(n): The cost of path between the first node and the current node

h(n): Heuristic function

If we want to find the shortest path in Figure 2 using the above function;

Let’s say we are trying to get from point X to point Y. Since point X is not moved to a different node, the g(n) cost does not occur, and its value is 0. The heuristic value of this point is the value 5 written on the node in red. In such problems, the heuristic value, in general, is the air distance between the current node and the desired node. There are two points to go from point X. In the case of going to point A, g(n) = 5 (path cost) because it moves to a new node. The heuristic is set to h(n) = 1. The f(n) value of point A is found as 5+1 = 6. If we want to find the f(n) values ​​of all points using this method,

X— A => g(A) + f(A) = 5 + 1 = 6,

A — Y=> g(Y) + f(Y) = 6+ 0= 6,

X— B => g(B) + f(B) = 1+ 4= 5,

B — C => g(C) + f(C) = 3+ 2= 5,

C — Y=> g(Y) + f(Y) = 5 + 0= 5,

As seen in the simple example above, the shortest path is the X-B-C-Y route. The cost of this road is 5 units, while the cost of the alternative X-A-Y route is 6 units. The example in Figure 3 can be examined in more detail once we have fully understood how to use the above equation.

Let’s say we want to reach node A from node J. There are 2 points (B and F) that can be reached from point A. Calculating the overhead costs, we get f(B) = 8 + 6 = 14 and f(F) = 3+6 =9.Since the least cost is at point F, the A* algorithm continues from here. There are 2 paths at point F. f(G) = 4 +5 = 9 and f(H) = 10 + 3 = 13. Since the least cost is at point G, we can do it from that point. Then, following the I and J nodes, we get f(I) = 7 + 1 = 8 , f(J) = 10. Since all the values ​​obtained after going to the F node are less than the f(B) node, it was not returned to the B node. But in a different scenario, let’s assume that f(I) is greater than f(B) after nodes F and G (f(I) > 14).

In this case, according to the A* algorithm, the process is interrupted here, and the path is continued with the B node. Here, as soon as f(C) > f(I), the path determination process continues again from the I node.

Implementation with Python

All of the codes below are available at https://github.com/ademakdogan/Implementation-of-A-Algorithm-Visualization-via-Pyp5js-

First, the grid structure is created. Some nodes here are marked as obstacles. Then the start and end nodes are determined, and the shortest path between these two points is found with the A* algorithm [3]. The working logic of the algorithm is basically based on two lists named open_set and closed_set. While there are nodes that can be processed in open_set, there are node paths that are processed in closed_set and, therefore, should not be repeated (In some approaches, obstacles are also thrown directly into the closed_set list, while in some approaches, it can be added as one of the qualifying properties of each node produced as an object.). As a result of various processes, these lists are filled and emptied, and the final result is reached.

Pseudocodes of all stages can be viewed on Wikipedia.

Github

Figure 4 shows the Python implementation of the A* algorithm. The Pyp5js library was used to visualize this work. In addition, the A* algorithm can work according to the obstacle list to be given specifically, the coordinates of the start and end nodes, and the size of the grid structure.

Thus, this project can also be used against specific problems.

python AStar.py -c 25 -r 25 -s 1 -q 3 -e 23 -t 21 -l True

As a result,

The way found!!!
23 20
23 19
23 18
23 17
23 16
23 15
23 14
23 13
23 12
23 11
23 10
23 9
23 8
23 7
23 6
23 5
23 4
23 3
22 3
21 3
20 3
19 3
18 3
17 3
16 3
15 3
14 3
13 3
12 3
11 3
10 3
9 3
8 3
7 3
6 3
5 3
4 3
3 3
2 3
1 3

Pyp5js

Pyp5js is a framework for visualizing Python codes on the browser. It enables the use of the p5.js javascript library via Transcrypt with Python. After the necessary installations are made, it is simply run with the following command.

$ SKETCHBOOK_DIR**=**'~/my-custom-sketchbook' pyp5js serve

Afterward, the necessary config settings are made by accessing the interface section via http://localhost:5000/. In the specified folder (SKETCHBOOK_DIR), operations are performed according to the codes in the Python file that is the same name as the project name. If you want to examine this project in detail, https://berinhard.github.io/pyp5js/ can be visited.

As a result, the A* algorithm is one of the most frequently used path-finding algorithms.

In this article, the working principles of this algorithm and its coding with Python are discussed. All codes can be found at github. The pyp5js library was used to visualize the algorithm. In the next articles, comparisons of different path determination algorithms with the A* algorithm will be discussed.

Project Repo : https://github.com/ademakdogan/Implementation-of-A-Algorithm-Visualization-via-Pyp5js-

Github : https://github.com/ademakdogan

Linkedin : https://www.linkedin.com/in/adem-akdoğan-948334177/

References

[1] Hart, P. E.; Nilsson, N. J.; Raphael, B. (1968). “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”. IEEE Transactions on Systems Science and Cybernetics. 4 (2): 100–107.

[2] Zeng, W.; Church, R. L. (2009). “Finding shortest paths on real road networks: the case for A*”. International Journal of Geographical Information Science. 23 (4): 531–543.

[3] Hetland, Magnus Lie (2010), *Python Algorithms: Mastering Basic Algorithms in the Python Language*, Apress, p. 214, ISBN 9781430232377.

Also published here.