A medieval pathfinding visualization comparing BFS, DFS, UCS (Dijkstra), and A*
Navigate infected city streets as a plague doctor rushing to save a patient
- Overview
- The Problem
- Algorithms Explained
- Quick Start
- Detailed Usage
- Understanding Seeds
- Project Structure
- Technical Implementation
- Performance Analysis
- Academic Context
- Future Improvements
- Contributing
- License
This project provides both a command-line tool and an interactive browser visualization to compare four fundamental search algorithms on a weighted grid pathfinding problem.
Most algorithm visualizations show only unweighted graphs. This project demonstrates the critical difference between:
- Uninformed vs Informed Search (BFS/DFS vs A*)
- Unweighted vs Weighted Graphs (BFS/DFS vs UCS/A*)
- Optimal vs Non-Optimal (all variants)
✅ Real-time animation - Watch all 4 algorithms explore simultaneously
✅ Step-by-step mode - Understand each expansion decision
✅ Reproducible maps - Use seeds to share and compare results
✅ Performance metrics - Nodes explored, path cost, execution time
✅ No dependencies - Pure Python stdlib + vanilla JavaScript
✅ Educational focus - Clear visualizations of algorithm behavior
You are a plague doctor in a medieval city. A patient needs urgent care, but the city is partially infected with plague. You must navigate from your clinic to the patient's home.
- Grid-based movement: 20×20 grid, 4-directional (up, down, left, right)
- Obstacles: ~20% of cells are buildings (impassable)
- Infection costs: Streets have risk levels 1-5
- 1 = Safe alley
- 2-3 = Moderate risk
- 4-5 = Plague hotspot (avoid if possible)
- Goal: Find a path that minimizes infection exposure
This models real-world problems:
- GPS navigation (traffic costs)
- Network routing (latency costs)
- Robot pathfinding (terrain difficulty)
- Video game AI (enemy density)
Strategy: Explore all neighbors at distance N before exploring distance N+1
Data Structure: FIFO queue (First In, First Out)
Step 1: Start
Step 2: Explore all 1-hop neighbors
Step 3: Explore all 2-hop neighbors
Step 4: Explore all 3-hop neighbors
...
Guarantees:
- ✅ Finds shortest path by hop count
- ❌ Ignores edge weights (infection costs)
- ✅ Complete (finds path if one exists)
- ⏱️ Time: O(V + E), Space: O(V)
Visual Pattern: Expands in perfect circular rings from start
When to Use: Unweighted graphs, need minimum steps
Strategy: Explore as far as possible down one branch before backtracking
Data Structure: LIFO stack (Last In, First Out)
Step 1: Start → pick a direction
Step 2: Go as deep as possible in that direction
Step 3: Hit dead end? Backtrack and try another branch
Step 4: Repeat until goal found
Guarantees:
- ❌ Not optimal (path length varies by luck)
- ❌ Ignores edge weights
- ✅ Complete with cycle detection
- ⏱️ Time: O(V + E), Space: O(V)
Visual Pattern: Plunges deep, then backtracks (worm-like movement)
When to Use: Exploring all possible paths, maze solving without optimality requirement
Strategy: Always expand the node with lowest cumulative cost so far
Data Structure: Min-heap priority queue (sorted by cost)
Step 1: Start (cost = 0)
Step 2: Expand cheapest frontier node
Step 3: Add neighbors to frontier with updated costs
Step 4: Repeat, always picking lowest-cost unexplored node
Guarantees:
- ✅ Finds optimal path by total cost
- ✅ Considers edge weights (infection costs)
- ✅ Complete and optimal
- ⏱️ Time: O((V + E) log V), Space: O(V)
Visual Pattern: Expands cautiously, avoiding high-cost (red) areas
When to Use: Weighted graphs, need globally optimal solution
Strategy: Like UCS, but use a heuristic to guide search toward the goal
Data Structure: Min-heap priority queue (sorted by f = g + h)
- g(n) = actual cost from start to node n
- h(n) = estimated cost from n to goal (heuristic)
- f(n) = g(n) + h(n) = estimated total cost
Heuristic Used: Manhattan distance × minimum edge cost
h(n) = (|row_n - row_goal| + |col_n - col_goal|) × 1
This heuristic is:
- Admissible: Never overestimates (safe for optimality)
- Consistent: h(n) ≤ cost(n, n') + h(n') for all neighbors n'
Guarantees:
- ✅ Finds optimal path by total cost (with admissible heuristic)
- ✅ Considers edge weights
- ✅ More efficient than UCS (explores fewer nodes)
- ⏱️ Time: O((V + E) log V), Space: O(V)
Visual Pattern: Expands in a directional bias toward goal, avoids wasted exploration
When to Use: Weighted graphs with good heuristic available (most pathfinding)
cd python
python plague_doctor.py --seed 42Output:
=====================================================================================
Plague Doctor's Route - Algorithm Comparison
=====================================================================================
Map: 20x20, Seed: 42, Start: (1, 1), Goal: (18, 18)
=====================================================================================
Algorithm | Found | Hops | Cost | Nodes Explored | Time (ms)
-------------------------------------------------------------------------------------
BFS | YES | 34 | 99 | 323 | 0.77
DFS | YES | 84 | 245 | 178 | 0.48
UCS | YES | 34 | 85 | 323 | 0.98
A* | YES | 34 | 85 | 301 | 1.11
=====================================================================================
- Open
web/index.htmlin any modern browser - Click "Run All" to watch algorithms explore simultaneously
- Use "Step" for frame-by-frame analysis
- Try different seeds to compare map variations
# Basic run (random seed)
python plague_doctor.py
# Reproducible run with specific seed
python plague_doctor.py --seed 42
# Custom grid size
python plague_doctor.py --size 30
# More/fewer obstacles
python plague_doctor.py --obstacle-prob 0.30
# Show ASCII map visualization
python plague_doctor.py --seed 42 --show-map
# Show specific algorithm's path on map
python plague_doctor.py --seed 42 --size 10 --show-path astar
# Export map as JSON for browser
python plague_doctor.py --seed 42 --export-map > map.json| Control | Action |
|---|---|
| Run All | Start continuous animation of all 4 algorithms |
| Step | Advance each algorithm by exactly 1 node expansion |
| Pause | Freeze animation (resume with Run All) |
| Reset | Clear current run, keep same map |
| New Map | Generate fresh random map |
| Speed Slider | Adjust animation speed (1 = slow, 20 = fast) |
| Seed Input | Enter specific seed for reproducible map |
A seed is a number that controls "random" generation, making it reproducible.
Computers can't do true randomness. Instead, they use deterministic formulas:
next_random = (previous × 1103515245 + 12345) % 2^31
The seed is the starting point for this formula.
Seed 42:
42 → formula → generates: 3, 1, 5, 2, 4, 3, 5, ...
Seed 42 again:
42 → formula → generates: 3, 1, 5, 2, 4, 3, 5, ... (SAME!)
Seed 999:
999 → formula → generates: 2, 4, 1, 5, 3, 1, 2, ... (DIFFERENT!)
When generating a 20×20 city map, the program makes 800+ random decisions:
- Cell (0,0): Obstacle? → NO, Cost? → 3
- Cell (0,1): Obstacle? → YES
- Cell (0,2): Obstacle? → NO, Cost? → 5
- ... (800 more decisions)
Same seed = same 800 decisions = identical map every time
# Share interesting maps
"Try seed 7777, there's a narrow corridor the algorithms handle differently!"
# Reproduce bugs
"Seed 12345 causes A* to explore more nodes than UCS—is the heuristic broken?"
# Fair comparison
"All 4 algorithms run on the EXACT same map, ensuring unbiased results"
# Scientific testing
"Run seeds 1-1000 and calculate average performance across varied maps"plague-doctor/
├── README.md # This file
├── .gitignore # Git exclusions
├── requirements.txt # Dependencies (none - stdlib only!)
│
├── python/ # Backend implementation
│ ├── city_map.py # CityMap class
│ │ ├── __init__() # Generate procedural grid
│ │ ├── neighbors() # Get valid moves from a cell
│ │ ├── path_cost() # Calculate infection risk
│ │ └── to_json() # Export for browser
│ │
│ ├── algorithms.py # All 4 search algorithms
│ │ ├── run_bfs() # Breadth-First Search
│ │ ├── run_dfs() # Depth-First Search
│ │ ├── run_ucs() # Uniform Cost Search
│ │ └── run_astar() # A* Search
│ │
│ └── plague_doctor.py # CLI entry point
│ ├── main() # Argument parsing
│ ├── print_comparison_table()
│ └── print_map_visualization()
│
└── web/ # Frontend visualization
├── index.html # 4-panel layout + controls
│
├── css/
│ └── style.css # Medieval dark theme
│
└── js/
├── cityMap.js # Map generator (matches Python)
│ ├── createRNG() # Mulberry32 PRNG (seed-compatible)
│ ├── generate() # Procedural city generation
│ └── neighbors() # Valid moves
│
├── algorithms.js # 4 algorithm generators
│ ├── bfsGenerator() # Yields exploration frames
│ ├── dfsGenerator()
│ ├── ucsGenerator()
│ └── astarGenerator()
│
├── renderer.js # Canvas drawing
│ ├── drawGrid() # Base map with infection colors
│ ├── drawState() # Current exploration state
│ └── drawPath() # Final path overlay
│
├── animator.js # Animation controller
│ ├── step() # Single-step mode
│ ├── runAll() # Continuous animation
│ └── setSpeed() # Animation speed control
│
└── app.js # UI event handlers
Language: Python 3.8+
Dependencies: None (standard library only)
Key Libraries Used:
collections.deque- FIFO queue for BFSheapq- Min-heap priority queue for UCS/A*random.Random(seed)- Seeded RNG for reproducibilitytime.perf_counter()- High-resolution timingdataclasses- Clean result structure
Design Decisions:
- Edge cost = destination cell cost (standard in pathfinding)
- 4-directional movement (no diagonals, simplifies cost model)
- Start at (1,1), Goal at (N-2, N-2) (avoids edge cases)
Language: ES6+ (vanilla JavaScript, no frameworks)
Browser Support: Chrome, Firefox, Safari, Edge (all modern versions)
Key Technologies:
- ES6 Generators (
function*) - Step-by-step algorithm execution - Canvas 2D API - Grid rendering
performance.now()- Millisecond-precision timing- Mulberry32 PRNG - Seed-compatible random generation
Design Decisions:
- No build step - Open HTML directly in browser
- Generators for algorithms - Single
next()call = single expansion - Synchronized RNG - Same seed in Python and JS produces identical maps
| Algorithm | Time Complexity | Space Complexity | Optimal? |
|---|---|---|---|
| BFS | O(V + E) | O(V) | By hop count |
| DFS | O(V + E) | O(V) | No |
| UCS | O((V + E) log V) | O(V) | By cost |
| A* | O((V + E) log V) | O(V) | By cost (if admissible h) |
Where:
- V = number of cells (400 for 20×20 grid)
- E = number of edges (~1600 for 4-directional grid)
Average over 100 random seeds:
| Algorithm | Avg Nodes Explored | Avg Path Cost | Avg Hops | Avg Time (ms) |
|---|---|---|---|---|
| BFS | 310 | 92 | 34 | 0.81 |
| DFS | 145 | 215 | 79 | 0.44 |
| UCS | 308 | 79 | 34 | 1.02 |
| A* | 283 | 79 | 34 | 1.08 |
- A explores 9% fewer nodes than UCS* while finding the same optimal cost
- UCS/A save 14% infection risk* compared to BFS on average
- DFS is 2× faster but produces paths 2.3× more costly
- BFS = UCS hop count (both find 34-hop paths, but UCS picks safer streets)
The execution time includes:
- Algorithm logic (A* has heuristic overhead)
- Python interpreter overhead (heap operations)
In production systems (C++, Rust), A* is consistently faster due to fewer nodes explored.
This project demonstrates concepts from:
AI / Algorithms Courses:
- Uninformed search (BFS, DFS)
- Informed search (A*)
- Heuristic design and admissibility
- Graph traversal algorithms
Data Structures Courses:
- Queue (FIFO)
- Stack (LIFO)
- Priority queue (min-heap)
- Graph representation
Complexity Theory:
- Time/space complexity analysis
- Big-O notation
- Trade-offs between optimality and efficiency
Weighted graph pathfinding appears in:
- Robotics: Motion planning with terrain costs
- Networking: Routing packets with latency costs
- Gaming: NPC pathfinding with danger zones
- Logistics: Delivery routing with traffic costs
- GIS: Navigation with road conditions
Extensions to explore:
- Greedy Best-First: Like A* but only uses h(n), not g(n)
- IDA*: Iterative Deepening A* (memory-efficient)
- Jump Point Search: A* optimization for uniform-cost grids
- Theta*: Any-angle pathfinding (not grid-constrained)
- D* Lite: Dynamic pathfinding for changing maps
- Bidirectional search (start and goal search simultaneously)
- Dijkstra variants (lazy deletion, Fibonacci heap)
- JPS (Jump Point Search) for grid optimization
- 3D city view with WebGL
- Heat map showing "exploration density"
- Path comparison overlay (show all 4 paths simultaneously)
- Replay controls (rewind, fast-forward)
- Dynamic obstacles (moving guards)
- Multi-goal pathfinding (visit multiple patients)
- Real-time map editing in browser
- Export animation as GIF/video
- Performance profiling mode (memory usage tracking)
- Tutorial mode with guided explanations
- Quiz questions about algorithm behavior
- Challenge maps (hand-crafted difficult cases)
- Algorithm pseudocode viewer
Contributions are welcome! This is an educational project, so clarity is prioritized over cleverness.
# Clone the repository
git clone https://github.com/Gabrcodes/plague-doctor-pathfinding.git
cd plague-doctor-pathfinding
# No installation needed! Python stdlib only.
# Just run:
python python/plague_doctor.py --seed 42
# Or open in browser:
# web/index.html- Clarity over cleverness - Code should be readable by students
- No external dependencies - Keep it pure Python/JavaScript
- Test with multiple seeds - Ensure reproducibility
- Document algorithm changes - Explain why, not just what
- Bug fixes in algorithm implementations
- Performance optimizations that maintain clarity
- New visualization modes (heat maps, path overlays)
- Additional algorithms (Bidirectional, JPS, etc.)
- Documentation improvements (typos, explanations)
- Test cases for edge cases
This project is released under the MIT License.
MIT License
Copyright (c) 2024 Abdelrahman Gabr
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
- Algorithm inspiration: Stanford CS106B, MIT 6.006
- Visual design: Medieval manuscript illuminations
- Color palette: Plague-era paintings (muted earth tones)
Abdelrahman Gabr
📧 abdelrahman_gabr@tutanota.com
🐙 GitHub: @Gabrcodes
🎓 Egypt University Of Informatics (EUI)
If this helped you understand search algorithms, please ⭐ star the repo!
Made with ❤️ for algorithm education