Maze_Path_Finder, Comparison between A star and Dijkstra algorithm.

About A star and Djikstra algorithm

Both the A* algorithm and Dijkstra's algorithm are widely used for pathfinding in graphs, including grid-based maps like mazes.

Dijkstra's Algorithm:

Dijkstra's algorithm is a greedy algorithm that finds the shortest path from a starting node to all other nodes in a weighted graph. It works by iteratively selecting the node with the smallest distance from the starting node and relaxing its neighboring nodes. Dijkstra's algorithm guarantees the shortest path from the starting node to all other nodes in the graph.

A star Algorithm

The A* algorithm is an extension of Dijkstra's algorithm with an added heuristic function to guide the search towards the goal node more efficiently. Like Dijkstra's algorithm, it explores nodes in order of their shortest known path from the starting node. However, in A*, the priority queue used to select the next node to explore is based on a combination of the actual cost of reaching a node from the start, known as the "g-score," and an estimate of the cost to reach the goal from that node, known as the "h-score" or heuristic. The key insight of A* is to prioritize nodes that are closer to the goal, which can significantly improve performance, especially in scenarios where a good heuristic is available. A* guarantees finding the shortest path from the starting node to the goal node under certain conditions, such as consistent and admissible heuristics.

About the project

This code is a Python implementation of solving mazes with obstacles using the A* algorithm. Let's break down what each part does:

1. Initialization:

   • It imports necessary libraries like pygame, random, time, and SortedSet from sortedcontainers.
   • Initializes Pygame.
   • Defines constants like screen size, colors, and indicators for different elements of the maze.

2. Generating Obstacles:

   • The generate_obstacles() function randomly generates obstacles on the maze grid. It ensures that essential squares, defined in imp_boxes, are not obstacles to facilitate better maze generation.

3. Creating Maze:

   • The create_maze() function creates the maze grid, populating it with obstacles generated by generate_obstacles().

4. Drawing Maze:

   • The draw_maze() function renders the maze on the screen using Pygame's drawing functions.

5. Heuristic and Neighbors:

   • heuristic() calculates the Manhattan distance heuristic between two points.
   • neighbours() generates neighboring cells for a given cell, excluding obstacles.

6. Solver Algorithm : (A) and Djikstra*:

   • The solver_algorithm() function implements the A* algorithm to find the optimal path from the start to the end of the maze. We can use Djikstra instead of A* by changing the f_score to updated_G_score.

7. Main Function:

   • The main() function orchestrates the whole process:
     • It creates the maze.
     • Displays the initial maze.
     • Runs the A* algorithm to find the solution path.
     • Updates the maze with the solution path.
     • Draws the maze with the solution path.
     • Sets up a game loop to keep the window open until the user decides to quit.
     • Quits Pygame when the user closes the window.

Overall, this code provides a comprehensive implementation for generating mazes with obstacles and solving them using the A* algorithm, with visualization provided by Pygame.