This project has been created as part of the 42 curriculum by dporhomo
Fly-in is a highly optimized, dual-mode logistics simulation engine designed to coordinate a swarm of autonomous vehicles.
The goal of this project is to parse abstract topological maps and calculate mathematically optimal, collision-free routing for a multi-agent fleet traveling from a starting hub to an end goal.
The engine ingests raw map data, processes it into an abstract graph, resolves complex traffic bottlenecks, and visualizes the real-time execution of the fleet in a professional, dynamic radar command interface.
This project uses a standard Makefile to automate environment setup, execution, debugging, and strict code compliance checking.
To simply launch the program, once you copy the repository to your local folder, go into that folder and simply run the command make run.
# 1. Install dependencies and set up the isolated Python virtual environment
make install
# 2. Check the installation of dependencies and execute the simulation (defaults to the basic 01_linear_path.txt map file)
make run
# 3. Execute the simulation with a specific map
make run MAP=maps/challenger/01_the_impossible_dream.txt
# 4. Run the simulation in debug mode (PDB)
make debug MAP=maps/easy/03_basic_capacity.txt
# 5. Validate code compliance (Flake8 & MyPy with mandatory subject flags)
make lint
# 6. Validate strict code compliance (Flake8 & MyPy --strict)
make lint-strict
# 7. Clean up temporary cache files (__pycache__, .mypy_cache)
make clean
# 8. Remove the program's virtual environment (venv) and clean up temporary cache files (__pycache__, .mypy_cache)
make fclean
Provided that venv has been already installed in the system, the program can be run directly, as follows:
For CLI output only:
python fly-in.py <a map file, e.g. maps/easy/01_linear_path.txt>For graphical output:
python fly-in.py <a map file, e.g. maps/easy/01_linear_path.txt --visual>CLI output demonstrates parsing of the provided map and the solution generated by the algorithm.
make run
[+] Setting up Python Virtual Environment...
[+] Upgrading pip and installing dependencies...
[!] Install Complete. Use 'make run' to launch the simulation.
[+] Launching Fly-in Engine...
pygame 2.6.1 (SDL 2.28.4, Python 3.13.1)
Hello from the pygame community. https://www.pygame.org/contribute.html
--- Executing Simulation Pipeline: maps/easy/01_linear_path.txt ---
[+] Calculating Cooperative Space-Time Routes...
[+] SIMULATION TERMINAL OUTPUT:
-------------------------------------------------
D1-waypoint1
D1-waypoint2 D2-waypoint1
D1-goal D2-waypoint2
D2-goal
-------------------------------------------------
--- Simulation Metrics ---
Total Simulation Turns : 4
Average Turns per Drone: 3.50
[+] Launching Pygame MVC Engine...
[+] Simulation window closed.
Image of the first level:
*Video of the full operation of the program:
Fly-in_demo_audio.mp4
Once the Pygame simulation launches, the user has full real-time control via a simple user interface:
- [SPACE] : Play / Pause Simulation
- [M] : Toggle Aerial (Vector Radar) / Ground (Cityscape) Logistics Mode
- [LEFT / RIGHT] : Cycle seamlessly through map files in the directory
- [UP / DOWN] : Adjust simulation playback speed
- [+ / -] : Dynamically inject or remove drones from the fleet and recalculate space-time routes instantly.
- [R] : Reset Timeline
- [ESC] : Quit
To successfully route multiple agents without collisions, this engine implements Cooperative Space-Time A*.
Instead of traditional A* which only maps
- The Reservation Table: As each drone finds a path, it reserves its required edges and nodes at specific timestamps in a global "Reservation Table."
- Dynamic Waiting: When subsequent drones calculate their routes, they view these temporal reservations as temporary walls. If a corridor is blocked on Turn 5, the drone mathematically evaluates whether it is faster to "wait in place" at a hub for one turn, or take a longer, winding detour.
- Optimized Results: This strategy successfully navigated the highly constrained "Impossible Dream" challenger map in an optimal 43 turns (beating the baseline 45-turn constraint).
To understand the necessity of a 3-Dimensional Space-Time matrix, it is vital to analyze the evolutionary steps of standard pathfinding algorithms and why they fail in a highly constrained, multi-agent environment like Fly-in.
-
Breadth-First Search (BFS)
-
Mechanism: Explores the grid equally in all directions, radiating outward like a water ripple.
-
Analysis: While it guarantees the shortest path on an unweighted grid, it is entirely "blind." It wastes massive computational resources exploring irrelevant areas of the map ($O(V + E)$). Furthermore, it cannot account for variable movement costs (like priority or restricted zones).
-
Dijkstra’s Algorithm
-
Mechanism: Explores paths based on the cumulative actual cost from the starting node ($g(n)$).
-
Analysis: Dijkstra is mathematically guaranteed to find the cheapest path on a weighted graph ($O((V+E) \log V)$). However, for point-to-point routing, it is highly inefficient because it explores in all directions rather than heading toward the goal.
-
Current Implementation: While too slow for individual drone routing, this engine utilizes a Reverse Dijkstra algorithm natively. By running it backwards from the goal, it perfectly calculates the true shortest-path distance from every node in the city to the end hub, generating a flawless heuristic map for the chosen A* logic.
-
Greedy Best-First Search
-
Mechanism: Explores paths based purely on a heuristic estimate of the remaining distance to the goal ($h(n)$).
-
Analysis: It is incredibly fast because it aggressively bee-lines toward the target. However, it is easily trapped by concave obstacles and dead-ends (like in "Maze of Despair" challenger map) and makes no guarantees about finding the optimal or shortest path.
-
Standard A Search*
-
Mechanism: The gold standard of single-agent pathfinding. It combines the accuracy of Dijkstra with the speed of Greedy Best-First by evaluating
$f(n) = g(n) + h(n)$ (Actual Cost + Estimated Remaining Cost). -
The Multi-Agent Failure: Standard A* is flawless for a single drone. However, it only understands 2-Dimensional space (
$X, Y$ ). If 25 drones independently run standard A*, they will all calculate the exact same "optimal" path, resulting in massive swarm collisions at the first restricted bottleneck.
The Solution: Cooperative Space-Time A* maps where to go, and when it is safe to be there. By injecting the temporal
To ensure the engine can handle enterprise-scale logistics, the architecture is designed around the following computational realities:
- Algorithmic Efficiency: Cooperative Space-Time A* is a "decoupled" planner. Because it solves for drones sequentially rather than simultaneously, it evaluates paths drastically faster than exhaustive search models, successfully routing complex maps in fractions of a second.
- Swarm Scalability: The algorithm handles a large number of drones exceptionally well, provided the network graph has sufficient capacity. Because paths are calculated iteratively, the computational overhead grows linearly with the fleet size, rather than exponentially. However, at extreme saturation (where physical space approaches zero), the sequential nature can theoretically lead to forced deadlocks.
-
Time Complexity: The pre-computation of the spatial heuristic via Reverse Dijkstra operates at
$O(E \log V)$ , where$E$ is edges and$V$ is vertices. The subsequent Space-Time A* search for$N$ drones operating over$T$ max time steps yields a worst-case complexity of$O(N \cdot T \cdot (V + E) \log(T \cdot V))$ . - Caching vs. Recalculation: The engine employs a hybrid strategy. The spatial heuristic distances to the goal are calculated exactly once and heavily cached. However, the actual Space-Time paths are explicitly recalculated for each drone against the dynamic Reservation Table. When the user injects a new drone via the UI, the engine recalculates the entire timeline matrix from scratch to guarantee safety.
-
Memory Impact: Memory footprint is highly optimized. The graph and heuristic caches consume minimal space ($O(V)$). The heaviest structure is the Reservation Table, which requires
$O(V \cdot T)$ space to track node and edge occupancy across the timeline. - Visualizing the Mathematics: The visual representation directly translates this complex Space-Time matrix into intuitive feedback. By rendering drones visibly "parking" at a hub while another passes, or fracturing into separate spatial lanes, the UI clearly demonstrates the temporal axis of the A* algorithm—making the invisible mathematics instantly understandable to the user.
Theoretical Future Expansion: While Cooperative A* routes drones sequentially, a future iteration could implement Conflict-Based Search (CBS) as well as Neural-Symbolic & Machine Learning Hybrids to guarantee absolute mathematical optimality for the entire swarm simultaneously, completely eliminating order-dependency.
The visualization engine was built using a strict Model-View-Controller (MVC) architecture to separate pathfinding mathematics from Pygame rendering. The visuals enhance the user experience through several advanced features:
- Dual-Mode Rendering: Users can toggle between Aerial Mode (a sleek, dark-mode vector network representing flight paths) and Ground Mode (a bright, architectural schematic representing rover logistics).
- Procedural WFC Cityscape: Instead of chaotic, random maze generation, Ground Mode utilizes a pseudo-Wave Function Collapse (WFC) algorithm. It dynamically spawns solid 4x4, 3x3, and 2x2 "city blocks" around the guaranteed A* routes, creating a highly realistic, Manhattan-style urban grid.
- Procedural Vector Graphics: Relying on OS-level emojis caused rendering overlaps across different operating systems. Hence, static fonts were replaced by dynamic Vector Graphics, mathematically drawing Cyan Chevrons and Amber Cargo Blocks using Pygame's native 2D primitives for pixel-perfect scaling.
- Dynamic Audio Engine: To simulate a professional flight-control room, the engine features an algorithmic audio mix. It plays a sweeping "zip" when a drone reaches its goal and a subtle "blip" when passing a hub, carefully mixed to prevent audio-stacking distortion during massive swarm movements. It also loops a 60Hz ambient radar-room hum.
- Red Blob Games: Introduction to A* Pathfinding - Fundamental concepts for grid and graph routing.
- Multi-Agent Path Finding (MAPF) - Literature on Cooperative A* and Conflict-Based Search architectures.
- Pygame Community Edition (CE) Documentation - Vector graphics (
pygame.draw), audio mixing, and surface transformations. - Wave Function Collapse Algorithm - Inspiration for the constraint-based procedural cityscape generation.
Artificial Intelligence (Large Language Models) was utilized during the development of this project in the following specific capacities:
- Architectural Refactoring: Used as a pair-programming assistant to map out the transition from a monolithic "God Class" visualizer into a strict PEP-8 compliant MVC architecture (
state.py,renderer.py,controller.py). - Procedural Geometry Math: Assisted in calculating the coordinate points for the
pygame.draw.polygonvector assets (e.g., rotating the Cyan Chevron dynamically based on the current tick-rate). - Audio Synthesis: Used to generate the mathematical formula (
math.sinarrays) required to synthesize the pure-audio 60Hz ambient background hum and UI blips without relying on external.mp3or.wavfile dependencies.