This project explores how different pathfinding strategies behave in a dynamic 3D environment with moving obstacles.
The simulation compares Greedy Best-First Search and Breadth-First Search (BFS) by controlling the same agent (Mario) under identical conditions.
- Environment: 3D grid
- Goal: Reach the target (Princess)
- Obstacles: Monsters that actively chase Mario
- Constraint: Monsters create danger zones that Mario must avoid
At every step, Mario recomputes his next move while monsters reposition dynamically.
- State-space modeling in a 3D grid
- Online path replanning
- Local vs global decision-making
- Dynamic obstacle avoidance
- Algorithm comparison using measurable metrics
- Chooses the locally best move using Manhattan distance
- Fast and lightweight
- Can get stuck or trapped due to lack of global awareness
- Explores all safe reachable states level-by-level
- Finds the safest available path if one exists
- Expands significantly more nodes
Both algorithms avoid:
- Monster positions
- Cells adjacent to monsters
- Previously visited states
- Monsters move greedily toward Mario
- Monsters act as moving obstacles
- Mario replans every step
- Simulation ends when Mario:
- Reaches the goal
- Gets caught
- Becomes stuck
- Greedy: number of neighbor evaluations
- BFS: number of expanded nodes
These metrics highlight the tradeoff between efficiency and robustness.