Autonomous Pacman AI

THE PROJECT

I transformed the classic arcade game into a simulation of a computer science student navigating the internship hunt. The core challenge was building an autonomous agent capable of solving the Traveling Salesperson Problem on a grid in real time. The bot calculates the most efficient path to collect tech company logos while actively avoiding dynamic ghost enemies.

ALGORITHMIC ARCHITECTURE

To achieve high performance on large maps, I engineered a highly optimized, multi-layered routing system in Java.

• Strategic Targeting: The high-level planner uses A* search to determine the optimal order to consume pellets. To keep the algorithm lightning fast, I implemented Prim's Algorithm to calculate a Minimum Spanning Tree (MST) heuristic.
• Tactical Movement: For physical grid navigation, the agent relies on Breadth-First Search (BFS). It categorizes neighboring tiles by risk level, allowing Pacman to proactively route around threats and recalculate paths when a ghost gets too close.
• Performance Optimization: As the board size increases, the state space explodes. I built custom distance and heuristic caching mechanisms to prevent redundant mathematical calculations, allowing the agent to scale seamlessly without freezing.

RESULTS AND PERFORMANCE

The optimized algorithmic architecture produced a highly performant and intelligent agent. By implementing custom distance caching and a hybrid search logic, the AI drastically reduced its computational overhead, consistently clearing complex 13×13 mazes well under the strict 20 second efficiency threshold. Additionally, the risk-aware navigation allowed the bot to successfully evade dynamic ghost threats and maintain a high win rate, proving that the underlying pathfinding logic is both lightning fast and highly adaptable to dangerous environments.