Overview
This project simulates a mine escape scenario where a trapped miner must efficiently navigate through rubble and TNT obstacles to reach safety. The game environment is modeled as a 2D grid, and the escape strategy involves a priority-based search using priority queues to determine the optimal path out of the mine.
Pathfinding & Strategy
The miner must clear rubble tiles (with different difficulty levels) and strategically detonate TNT to open new paths. The escape follows these priority rules:
- First, detonate TNT if available.
- Otherwise, clear the tile with the lowest rubble value.
- Tie-breaking is based on grid position (column-first, then row).
Priority Queue Implementations
The project also involved implementing multiple priority queue data structures, each with different performance trade-offs:
- Heap – Efficient insertions and deletions for optimal tile selection.
- Sorted Array – Ensures quick retrieval of the lowest-cost tile but has costly insertions.
- Pairing Heap – Provides a flexible and adaptive structure for dynamic priority updates.
Optimization & Results
The project analyzed execution times and efficiency across different priority queue implementations. The Binary Heap performed best, balancing fast insertion and retrieval, making it the preferred approach for the mine escape problem.
Key Takeaways
- Implemented efficient pathfinding with dynamic priority-based decision-making.
- Explored trade-offs between different priority queues and their real-world applications.
- Optimized search heuristics for minimal escape time.