A semester assignment that focuses on utilizing various path finding algorithms such as A Star and then comparing the results with evolutionary searches such as Genetic Algorithms. The second part of this assignment explores different tools for routing purposes.
The h_of_n_calculator function calculates the heuristic (estimated cost) using the Euclidean distance between two points. It's an important part of the A* algorithm.
This function checks whether a potential move is valid. It ensures the move is within the grid boundaries and does not collide with obstacles.
This function helps in tracking and reconstructing the path from the destination back to the starting point based on the previously stored 'previous' nodes.
The A* (A-star) algorithm implemented in this code is a highly efficient pathfinding method widely used for finding the shortest route from a starting point to a destination on a grid. This algorithm takes into account obstacles and grid boundaries and operates by maintaining a priority queue, the open_list, which determines the order in which nodes (representing grid positions) are explored. Each node is assigned two critical values which is the the g_score, which signifies the cost of reaching that node from the starting point, and the f_score, which is the sum of the g_score and a heuristic estimate, h_score. We base the heuristic on Euclidean Distance.
We explore the closest nodes, selecting the one with the lowest f_score from the open_list. For each node explored, the algorithm evaluates its neighbors, checking if moving to a neighbor results in a shorter path. If a shorter path is found, the g_score and f_score for the neighbor node are updated. This optimization process continues until the destination node is reached or if no other possible move exists.
This function is responsible for the whole GUI process.
After seeing the results, the A* algorithm is an optimal approach for finding the shortest path in various applications. It consistently provides the shortest cost path due to its ability to consider both the distance from the start (the g_score) and the estimated distance to the end (the heuristic h_score), shown by the optimal f_score.
Moving from (1,2) to (7,8) with a few obstacles in between, let's see how A star works out:
We start with a population of random paths, ensuring they are a minimum distance from the start and destination.
In each generation, the fitness of each path is assessed based on the total cost, considering distances from the start to the first position, from the last position to the destination, and between intermediate positions. We use our A star code to find optimal distances.
Paths with lower fitness values (shorter total distances) are chosen as parents for the next generation.
New paths are created by combining genetic information from the selected parents using crossovers (splits).
With a low probability, individual grid positions in offspring paths are randomly altered so that we add diversity.
The new population is formed by combining parents and offspring. This process repeats for several generations.
After multiple generations, the best path with the lowest total cost is chosen as the final solution.
The final coordinates are then connected using the A* algorithm, ensuring it respects obstacle constraints and grid boundaries and gives closer or actual optimized values.
Moving from (1,2) to (7,8) with a few obstacles in between, let's see how GA works out:
Our GA more often than not gives the shortest path which is also optimal as shown by A star's cost. This is due to an efficient fitness function and utilization of A star between points generated by GA.
The values can be changed to incoperate other grid sizes or parameters too.