A comprehensive implementation of various maze generation and solving algorithms, featuring traditional search methods, evolutionary algorithms, and cutting-edge neural network approaches.
- Recursive Backtracker - Creates mazes with long, winding corridors
- Prim's Algorithm - Generates mazes with more branching patterns (3x faster)
- Depth-First Search (DFS) - Memory efficient, good for deep mazes
- Breadth-First Search (BFS) - Guarantees shortest path
- A Search* - Optimal pathfinding with heuristic guidance
- Genetic Algorithm (GA) - Evolution-based pathfinding with optimized fitness function
- Deep Q-Network (DQN) - Reinforcement learning approach with PyTorch implementation
| Algorithm | 20x20 Maze (Avg) | 30x30 Maze (Avg) | Time Complexity |
|---|---|---|---|
| A* | 88 cells, 0.0006s | 106 cells, 0.002s | ⭐⭐⭐⭐⭐ |
| BFS | 88 cells, 0.001s | 106 cells, 0.003s | ⭐⭐⭐⭐ |
| DFS | 89 cells, 0.006s | 107 cells, 0.002s | ⭐⭐⭐ |
| GA | 73 cells, 21.5s | 125 cells, 4.9s | ⭐⭐ |
| DQN | In Progress | In Progress | ⭐ |
| Module | Purpose | Key Components |
|---|---|---|
| config/ | Project configuration and settings | Global settings, neural network hyperparameters |
| maze/generators/ | Maze creation algorithms | Recursive Backtracker, Prim's Algorithm |
| maze/solvers/traditional/ | Classical pathfinding algorithms | DFS, BFS, A* implementations |
| maze/solvers/genetic/ | Evolutionary computation approach | Genetic algorithm with fitness optimization |
| maze/solvers/neural/ | Machine learning solutions | Deep Q-Network with PyTorch |
| examples/ | Demonstration scripts | Algorithm usage examples and comparisons |
| visualization/ | Rendering and display utilities | Maze visualization and result plotting |
| output/ | Generated content | Solved maze images and performance data |
All traditional algorithms guarantee finding a solution if one exists:
- A* uses Manhattan distance heuristic for optimal performance
- BFS explores level by level, ensuring shortest path
- DFS uses minimal memory with depth-first exploration
- Population Size: 100 individuals
- Mutation Rate: 2%
- Crossover Rate: 80%
- Selection: Tournament selection with elitism
- Fitness: Path length + goal reaching bonus
- Architecture: Fully connected neural network (64-64 hidden layers)
- State Representation: [agent_pos, goal_pos, local_maze_info]
- Training: Experience replay with epsilon-greedy exploration
- Framework: PyTorch with CUDA acceleration
- A* provides the best balance of speed and optimality
- Genetic Algorithm can find shorter paths than traditional methods but requires significantly more time
- DQN shows promise but requires extensive training for larger mazes
- Prim's Algorithm generates mazes better suited for neural network training
A comprehensive implementation and comparison of maze generation algorithms and solving techniques, featuring traditional search methods and evolutionary approaches.
Our project implements two distinct maze generation approaches, each producing unique maze characteristics:
 |
 |
| Recursive Backtracker Creates long, winding corridors Memory efficient generation |
Prim's Algorithm More branching patterns 3x faster generation |
 |
 |
 |
 |
| Original Maze | DFS Solution Memory efficient Deep exploration |
BFS Solution Shortest path Level-by-level |
A* Solution Optimal pathfinding Heuristic guided |
 |
 |
| Initial Maze | Genetic Algorithm Solution Evolution-based pathfinding Can find creative shorter paths |
| Maze Size | Algorithm | Avg Path Length | Avg Cells Explored | Avg Time (s) |
|---|---|---|---|---|
| 20x20 | DFS | 78.67 | 168.67 | 0.00632 |
| 20x20 | BFS | 77.33 | 136.33 | 0.000855 |
| 20x20 | A* | 77.33 | 126.00 | 0.000756 |
| 20x20 | GA | 73.00 | 18866.67 | 21.4908 |
| 30x30 | DFS | 106.67 | 334.33 | 0.001659 |
| 30x30 | BFS | 106.00 | 271.67 | 0.003468 |
| 30x30 | A* | 106.00 | 208.33 | 0.001951 |
| 30x30 | GA | 124.67 | 1633.33 | 4.85979 |
🏆 Optimal Path Length: Genetic Algorithm finds shortest paths (73 cells vs ~77 for traditional)
⚡ Fastest Execution: A* algorithm provides best speed-accuracy balance (0.0008s)
🔍 Most Efficient Exploration: A* explores fewest cells (126) while maintaining optimality
⏱️ Time Trade-offs: Traditional algorithms 1000x faster than Genetic Algorithm
| Algorithm | Average Path Length | Exploration Efficiency | Time Complexity | Optimal Solution |
|---|---|---|---|---|
| A* | ⭐⭐⭐⭐⭐ | Excellent (Fewest cells explored) | Fast | ✅ Guaranteed |
| BFS | ⭐⭐⭐⭐⭐ | Good (Systematic exploration) | Moderate | ✅ Guaranteed |
| DFS | ⭐⭐⭐⭐ | Fair (Deep exploration) | Fast | ❌ Not guaranteed |
| Genetic Algorithm | ⭐⭐⭐ | Variable (Evolution-based) | Slow | 🔄 Can improve over generations |
Our testing includes multiple trials across different maze sizes:
 |
 |
 |
| Trial 1 Results | Trial 2 Results | Trial 3 Results |
 |
 |
 |
| Trial 1 Results | Trial 2 Results | Trial 3 Results |
- GA Path Length Fix: Implemented unique position counting for fair comparison
- Neural Network: Enhanced state representation with local maze information
- Visualization: Real-time rendering of solution paths and exploration patterns
- All traditional solving algorithms
- Genetic algorithm with optimized fitness function
- Prim's maze generation algorithm
- Comprehensive performance comparison
- Visualization system
- DQN Optimization: Improving training stability for larger mazes
- Progressive Training: Starting near goal, expanding outward
- Alternative Neural Networks: Exploring MazeNet and PPO approaches
- Additional maze generation algorithms (Wilson's, Hunt-and-Kill)
- Web interface for interactive maze solving
- 3D maze support
- Multi-agent pathfinding
Contributions are welcome! Please feel free to submit pull requests or open issues.