Path Finding Algorithm

During my studies one of my favorite classes was Algorithms and Data Structures. Hence, I decided to apply my knowledge in a project that demonstrates the behavior of three important path finding algorithms: A-star, Depth-First Search and Breadth-First Search.

I followed this tutorial teaching the A* algorithm in Python using the Pygame library. In addition, I implemented the DFS and BFS algorithms. In this article I describe my pathway to realize the optimization and what I have learned.

My source code is here : )

For a better understanding, it is import to consider the board as a graph where the set of spots are the nodes. A graph is considered a finite set of either unordered pairs of nodes where edges are undirected or a set of ordered pairs for a directed graph.

The edges of a graph can have values (weights) that describe the cost of traversing from one node to the other. However, in this game the weight has value one for each edge. Hence they do not need to be considered.

The start node is rendered yellow, the final node in blue. Nodes that were handled are depicted red and the ones that will be considered next (valid neighbors) in green. Non-accessible nodes (barriers) are colored black. After the algorithm found a path between start and end, the graphic interface will display the found path in purple. The following figures show the different algorithms after conclusion.

Depth-First Search(DFS)

DFS is an algorithm for traversing a Graph (or Tree). The goal is to find a specific node by exploring along a path gathering the possible future nodes that could be explored, designated neighbors. As soon as the algorithm finds a dead end, it backtracks until it finds a new possible way. An important characteristic of DFS is the Stack as linear data structure to store nodes.

Quick recap to Stacks: In a Stack a new element is added in the end and removed in that end only, in a (LIFO - Last In, First Out) manner.

Fig.1 Depth-First Search

Breadth-First Search(BFS)

BFS likewise DFS is a traversing algorithm applicable to graphs and trees. However an essencial distinct characteristic is, it works level by level, a level-order approach. In other words, before making a step further away from the start, it will handle all nodes that have the current distance. The BFS algorithm uses a queue to store found nodes.

It will, by nature, find the shortest path between the start and the final destination.

Keep in mind: a queue works on the first element that was added (FIFO - First in, Fist out).

Fig. 2 Breadth-First Search

A-star

A* is an informed search algorithm and a graph traversal which, based in the nodes weight, aims to find a path to the given goal node having the smallest cost. A* has the benefit to be informed about the distance of the end node, defined by the heuristic. Base on that it can compute the best path, in this case the smallest cost.

Heuristic implementation

The heuristic used in this project is based in Manhattan Distance. The distance between two points is calculate by the sum of the absolute differences of their Cartesian coordinates. The heuristic function calculates the cost of the cheapest path from n to the goal.

In the equation f(n) = g(n) + h(n), the variable n is the next node on the path, g(n) is the cost of the path from the start node to n, and h(n).

Fig. 3 A-star

Applications of A*

  • Video games
  • Informational search with online learning

After implementing this project, I could comprehend the behavior of essential algorithms related with AI and enhance my knowledge in Stacks and Queues, important data structures. During the process I felt challenged to perceive the logic behind drawing the board of the game in the Pygame graphic interface and visualize the pixel coordinates drawn in the screen. Comparing the algorithms I could recognize the advantages and disadvantages of each. Where BFS has the benefit to give the shortest path, on the other hand, DFS can be faster depending the direction it takes, related to the node . A* is the most advanced using heuristic to orientate towards the end node. I truly believe that it is an creative way to teach and learn algorithms.

Nice right :)

Other interesting sources:

Maze Solving - Computerphile Footer © 2022 GitHub, Inc. Footer navigation Terms

Written on October 12, 2022