This project has been created as part of the 42 curriculum by mkhoubaz.

Fly-in

Description

Fly-in is a path-finding algorithm in graphs data structure with zone(node) occupancy rules and movement and turn mechanics. The goal of this project is routing a shorted path from a starting zone to a end zone to reach different number of drones.

Instructions

To compile the project, run the following command in the terminal

• Install project dependencies:

    make install

• Run the project:

    make run FILE={path_of_map_file}

• Clean the project:

    make clean

Resources

• Python builtin function: python docs
• Pydantic: pydantic docs
• Regex: regex101 python regex docs w3schools
• Graph data structure: geeksforgeeks wikipedia NeuralNine video
• Dijkstra algorithm: w3schools FelixTechTips video Computer Science Lessons video b001 video
• Binary heap(heapq): Spanning Tree video Python docs

Algorithm choices and implementation strategy

Algorithm Selection

The primary problem in this project is to find the shortest path in a graph while considering zone occupancy rules in other word cost, so my choice was between: BFS (O(V + E)): BFS is a simple algorithm that explores all neighbors at the present depth before moving on to the nodes at the next depth level. However, it does not account for varying edge weights, which is crucial in our case due to zone occupancy rules. Dijkstra's Algorithm (O((V + E) log V)): Dijkstra's algorithm is designed to find the shortest path in a weighted graph, making it suitable for our problem A* Search Algorithm (O(E)): A* is an extension of Dijkstra's algorithm that uses heuristics to guide the search, potentially reducing the number of nodes explored. However, it requires a well-defined heuristic function, which may not be straightforward to design for our specific problem.

Given the need to account for varying edge weights due to zone occupancy rules, Dijkstra's algorithm was the most appropriate choice for this project. It efficiently finds the shortest path while considering the costs associated with each zone.

Implementation Strategy

The strategy for implementing Dikstra's algorithm in this project focused on use min-heap (priority queue).

1. Graph Representation: The graph is represented using an adjacency list, where each node (zone) has a list of its neighboring nodes along with the associated costs (weights) based on occupancy rules.
2. Priority Queue: A min-heap is used to keep track of the next node to explore based on the lowest cumulative cost from the starting node. This allows for efficient retrieval of the next node to process.
3. Cost Calculation: All nodes are initialized with an infinite cost in a dictionary with name of zone as key and the cost as value, except for the starting node, which is set to zero. As nodes are explored, the costs are updated based on the occupancy rules and the cumulative cost from the starting node.
4. Path Reconstruction: Once the heapq is empty the dijkstra finshed with other dictionary to keep track of the previous node for each node, allowing for the reconstruction of the shortest path once the end node is reached.
   1. Convert the dictionary of previous nodes into a list of zones representing the shortest path from the starting zone to the end zone.
   2. Check if the len of the path is more than one zone, if yes then return the path else return UnsolvableGraphError. because if the last zone doesn't have any connection with any zone and we start from start_hub zone the are no path to reach the end_hub zone.

Visual Representation Features

The project include a terminal visual representation of the drones movement with it id and the zone it is in, and connection if type of zone restricted, with color for each zone use rich library.