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

Description

• Fly-in is an algorithmic simulation and routing project designed to manage a fleet of autonomous drones navigating a complex, interconnected graph.

• Goal: The primary objective is to calculate and execute collision-free paths for a specified number of drones traveling from a starting hub to a destination hub. The simulation must dynamically balance traffic, respect physical capacities, and optimize travel times across varying terrain types.

• Overview: The project is driven by a robust logic backend and a structured terminal execution engine. The backend parses custom map files containing nodes (hubs) and edges (links) with strict capacity limits. It implements an advanced Cooperative Pathfinding system to safely guide the fleet through different zones—including normal areas, time-penalizing restricted zones, and highly efficient priority zones—without exceeding hub limits or causing mid-air collisions. The execution engine then outputs this calculated timeline directly to the standard output, utilizing a custom ANSI color-coding system to visually distinguish the different zone types and provide a clear, verifiable log of the algorithmic traffic flow.

Instructions

• Prerequisites:

  • Python 3.x
  • Standard Python libraries (math, heapq, re, etc.)
  • pydantic [ For Parsing File ]

• Installation:

  • make venv (to create a virtual envirenemant)
  • make install (to install dependencies)

• Execution:

  • make run (to run the program with the map.txt file)

Resources

• Documentation & References:

  • djikstra algo : https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
  • Multi-agent pathfinding : https://en.wikipedia.org/wiki/Multi-agent_pathfinding
  • Python Official Documentation (heapq for priority queues, re for regex parsing)

• Use of Artificial Intelligence:

  • Debugging Precision: Diagnosing floating-point synchronization issues when implementing the 0.9 weight logic for priority zones.
  • Code Architecture: Structuring the Object-Oriented design separating the HubModel, Pathfinder, and Engine.
  • etc . . .

Algorithm Choices & Implementation Strategy

To successfully route multiple drones without collisions, this project utilizes a modified Space-Time Dijkstra approach combined with a centralized Reservation Calendar.

1. The Pathfinding Strategy:

Instead of searching through a standard 2D graph, the algorithm searches through a 3D Space-Time graph using a tuple of (Hub_Name, Turn_Number). Drones are planned sequentially. When Drone 1 finds its optimal path, it locks its coordinates and travel times into the master Reservation System. When Drone 2 plans its route, it treats Drone 1's future locations as dynamic obstacles, forcing it to either wait at its current hub or take a detour.

2. Handling Zone Weights & Priorities:

Normal: Costs 1 turn.

Restricted: Costs 2 turns.

Priority: Implemented with a mathematical trick using a cost of 0.9 during the Dijkstra search. This forces the algorithm to heavily favor priority links as tie-breakers. When communicating with the physical engine and the reservation calendar, this 0.9 is rounded up using math.ceil() to exactly 1 turn, maintaining perfect synchronization with the game clock.

3. The Execution Engine:

The simulation ticks forward turn-by-turn. To prevent false collision reports (e.g., Drone A failing to move forward because Drone B hasn't stepped out of the way yet), the engine sorts the drone fleet in descending order based on their path progress (step_index). By processing the drones at the front of the line first, the engine effectively "clears the pipe," allowing continuous, fluid traffic movement.

Visual Representation

• Features:

  • ANSI Color-Coding: Hub movements printed to the terminal are dynamically colored based on their zone types using a custom color department class. This allows the user to instantly differentiate between normal, restricted, and priority zones directly in the text output.

  • Turn-by-Turn Logging: Drones are logged as they move across the links and wait inside the hubs, clearly printing multi-turn actions for restricted zones.

• Enhancing the User Experience:

Reading hundreds of lines of standard terminal output makes it incredibly difficult to track the simulation. By injecting dynamic colors directly into the output strings, the terminal log is transformed from a wall of plain text into an intuitive, readable traffic report. Evaluators can easily verify that drones are serving their penalties in restricted zones or utilizing priority lanes just by looking at the color of the output.

Input & Output Examples :

• The Input Should Be Like This : "python3 main.py map.txt" Like in The Make Run !

• Output Will Be Different For Every Map .

  • Example of Output :

1. D1-waypoint1
2. D1-waypoint2 D2-waypoint1
3. D1-goal D2-waypoint2
4. D2-goal

• The [D*] is The Drone Number
• The Name After The Minus is The Zone_Name