AlgoWars: Algorithmic Scenarios for Missile Routing and Defense Evasion

Overview

AlgoWars is an educational project for the Design and Analysis of Algorithms course. It models multi-scenario missile routing with constraints (range, stealth, spies, defense) over a weighted graph of cities. Each scenario targets a distinct objective and showcases algorithmic techniques (Dijkstra, A*, greedy, divide-and-conquer, dynamic programming, heuristic search).

Key Features

• Multiple scenarios (1–6) with different objectives and constraints
• Realistic constraints: max range, uncontrolled range, stealth vs defense, spy detection
• Visualizations for paths and attack logs
• FastAPI service to run scenarios and inspect results

Project Structure

• src/
  • algorithms/: pathfinding (Dijkstra, A* variants), heuristics, tracking
  • engine/: scenario implementations scenario_one … scenario_six
  • data_loader/: JSON loaders for cities and missiles
  • map/: graph/city abstractions (base, enemy, spies)
  • visualizer/: plotting utilities
  • api/: FastAPI app, static UI
• data/: cities.json, missiles.json
• src/output/: results and visualizations (auto-generated)

Installation

• Requirements: Python 3.10+, pip
• Install dependencies:

pip install -r requirements.txt

Running Locally (CLI)

• Run all scenarios with visualization:

python -m src.main

• Results are written to src/output/results/ and figures to src/output/visualizations/.

Running the API

• Start the API (development):

uvicorn src.api.app:get_app --reload

• Open http://127.0.0.1:8000/static (or /dashboard) for the UI
• Static artifact mounts:
  • Results: http://127.0.0.1:8000/results
  • Visuals: http://127.0.0.1:8000/visuals

Data Inputs

• Cities: data/cities.json (name, country, x, y, defense_level, city_type, has_spy)
• Missiles: data/missiles.json (name, max_range, uncontrolled_range, stealth, damage, category)

Scenarios (Objectives & Methods)

• Scenario 1 — Advanced pathfinding with realistic spy detection
  • Objective: maximize damage using D1 missiles with reprogramming when needed
  • Methods: find_optimal_path, reprogramming penalty, spy detection simulation
• Scenario 2 — Limited inventory, more missiles
  • Objective: maximize damage with A-type missiles under inventory
  • Methods: greedy target selection, path reprogramming when needed
• Scenario 3 — B/C types with strategic distribution
  • Objective: maximize damage with B/C distribution
  • Methods: A* with reprogramming, spy-aware evaluation, weighted scoring
• Scenario 4 — All-out attack with multiple algorithms
  • Objective: maximize total damage using a pipeline
  • Methods: Greedy target selection, A* (spy-avoidance, reprogramming), Divide & Conquer distribution, DP allocation
• Scenario 5 — Multi-night operations
  • Objective: optimize outcomes over multiple nights under evolving spies/defense
  • Methods: per-night greedy, interception resolution per target capacity
• Scenario 6 — Siren Game (آژیر بازی)
  • Objective: maximize number of nights with at least one detected attack (siren)
  • Methods: early-accept heuristic per night; A* (spy-avoidance, reprogramming) + spy detection; stops when no detected attack is possible
  • Output metric: max_siren_nights in scenario_6.json

Complexity (High-Level)

• Dijkstra/A*: O(E log V) per path query
• Greedy selections: O(K log K) typically (sorting) or early-accept O(K)
• Multi-night loops: O(N_nights × query_cost); Scenario 6 uses early-accept + caching to minimize queries

API Endpoints (Core)

• GET / or /dashboard: UI
• GET /health: liveness probe
• POST /load/defaults: quick metadata for default dataset
• GET /scenario/{num}: scenario info (1–4 described in API; 5–6 available in CLI; extend similarly if needed)
• POST /scenario/{num}: run scenario (1–4 wired). Body:

{
  "cities_path": ".../data/cities.json",
  "missiles_path": ".../data/missiles.json"
}

• POST /pathfinding/demo: run a sample pathfinding demo
• GET /algorithms/pathfinding/steps: pathfinding step trace
• GET /algorithms/spy-detection/steps: spy detection steps
• GET /analytics/attack-data: aggregate recent scenario results

Notes:

• The CLI currently runs scenarios 1–6 with visualizations.
• The API demo routes document 1–4 out of the box; extend scenario_map to expose 5–6.

Output Schema (Example)

• Each scenario_X.json includes:
  • scenario, total_damage, total_attacks, attack_details
  • Scenario-specific fields, e.g. Scenario 6 adds max_siren_nights

Reproducibility & Determinism

• Randomness is limited (fixed seeds where applicable). Graph, cities, and missiles are fixed by data/*.json.
• Run environments: tested with Python 3.10+ on Windows/Linux.

How to Extend

• Add a new scenario: create src/engine/scenario_seven.py exporting run_scenario(cities, missiles, graph); import and wire in src/main.py and optionally in the API.
• Add an algorithm: place under src/algorithms/, expose a clean function with explicit params, and integrate where appropriate.

Acknowledgments

This repository is designed for academic use in algorithm design, emphasizing clarity, reproducibility, and comparative evaluation across strategies.