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

📝 Description

Fly-in is a high-performance simulation system designed to route a fleet of drones from a starting hub to a target destination through a complex network of connected zones. The core objective is to minimize the total number of simulation turns while strictly adhering to movement constraints, zone types, and capacity limits.

Built with a focus on Object-Oriented Programming (OOP) and Static Type Safety, this project implements a custom routing engine without the use of external graph libraries like networkx.

---

⚙️ Instructions

Prerequisites

• Python 3.10 or later.
• uv package manager for fast and reliable dependency management.

Installation & Execution

The project includes a Makefile to automate all tasks:

1. Install dependencies:

   make install

2. Run the simulation:

   make run

3. Run in Debug mode (pdb):

   make debug

4. Linting & Type Checking:

   make lint-strict

---

🧠 Algorithm & Strategy

Dynamic Cost Dijkstra

The routing engine utilizes a custom Dijkstra-based algorithm adapted for multi-agent simulation. Unlike static pathfinding, our approach uses a Dynamic Cost System:

• Congestion Awareness: The weight of a path is not just its physical distance or zone type (normal, restricted, priority).
• Dynamic Penalties: As a path becomes more "crowded," its traversal cost increases. This forces drones to distribute themselves across different disjoint paths to maximize throughput.
• Capacity Management: The algorithm respects max_drones per zone and max_link_capacity per connection, preventing deadlocks and collisions.

Scheduling Logic

Drones move simultaneously. The system evaluates the state turn-by-turn, ensuring that:

1. Drones moving out of a zone free up space for incoming drones in the same turn.
2. Restricted zones (2-turn cost) are handled by forcing the drone to occupy the connection during transit.

---

📊 Performance Benchmarks

My implementation significantly beats the "Hard" targets set by the subject.

Map Type	Map Name	My Score	Target	Status
Easy	01_linear_path	3	$\le 6$	✅
	02_simple_fork	4	$\le 6$	✅
	03_basic_capacity	4	$\le 8$	✅
Medium	01_dead_end_trap	4	$\le 15$	✅
	02_circular_loop	11	$< 20$	✅
	03_priority_puzzle	5	$\le 12$	✅
Hard	01_maze_nightmare	10	$\le 45$	✅
	02_capacity_hell	18	$\le 60$	✅
	03_ultimate_challenge	26	$\le 35$	✅
Challenger	01_the_impossible_dream	43	45	✅

---

🎨 Visual Representation

The project provides dual-layer feedback for an enhanced user experience:

1. Pygame GUI

• Navigation: Click and drag to pan across large maps; use the scroll wheel to zoom.
• Simulation Control: * Right Arrow: Step forward one turn.
  • Left Arrow: Step backward to review previous movements.
• Real-time Data: Visualizes drone IDs, zone capacities, and restricted transit paths.

2. Terminal Output

• Standardized output format for drone movements (e.g., D1-roof1 D2-corridorA).
• Color-coded text for hubs and zones based on the input metadata.

---

📚 Resources & AI Use

References

• Python typing module documentation for strict type hinting.
• Pygame Library Documentation for GUI development.

AI Disclosure

AI was utilized as a pedagogical tool during development:

• Learning Pygame: Generated tutorials and code snippets to understand the event loop and coordinate transformation (zoom/drag).
• Knowledge Verification: Consulted to validate the logic of the dynamic penalty system and ensure no edge cases in capacity handling were overlooked.
• README: This README was generated by AI based on detailed technical specifications and logic provided by the author
• Documentation: Generated comprehensive docstrings and internal comments to ensure code maintainability and clarity.
• Logic Optimization: Assisted in rethinking and restructuring the priority system to improve efficiency and decision-making logic.