Pacman
Agent Intelligence.
Implementing classic AI search algorithms to solve complex spatial problems. From Depth-First Search to A* heuristics, this project explores how agents perceive and navigate dynamic state spaces.
Language
Python 3.x
Algorithms
DFS, BFS, A*
Focus
Path Optimization
State Space
Complex/Dynamic
The Challenge
The core of Game AI lies in pathfinding. While a human player relies on intuition, an autonomous agent must evaluate thousands of potential states to determine the most efficient route.
In this project, I transformed Pacman from a player-controlled character into a decision-making entity. By implementing various search strategies, I analyzed the trade-offs between completeness, optimality, and time complexity.
Algorithm Visualization
DFS/BFS Path Exploration
Uninformed Search
Implemented DFS, BFS, and UCS to navigate static mazes where the cost of every step is uniform or varying.
Informed (Heuristic) Search
Utilized A* Search with custom Manhattan and Euclidean heuristics to find the mathematically optimal path.
Multi-Goal Optimization
Solved the 'Corners Problem' and 'Food Search' by designing heuristics that account for multiple target states.