A* Pac-Man Solver

Overview

The A Pac-Man Maze Solver* is an intelligent simulation built entirely in Python using Pygame. While traditional Pac-Man relies on human input, this project implements an autonomous agent that navigates complex, customizable mazes to consume all food pellets as efficiently as possible.

By utilizing the A* (A-Star) Search Algorithm, the agent calculates the optimal path through the grid. The simulation extends the classic mechanics by introducing new constraints and power-ups, making the pathfinding process significantly more dynamic.

Core Mechanics & AI Implementation

1. The A* Search Algorithm

At the heart of the agent is the A* pathfinding algorithm. The AI uses a custom heuristic function based on the Manhattan Distance to the closest food item. This allows for efficient pruning of the search space, ensuring that the agent doesn't waste computational resources exploring unpromising paths.

The algorithm continuously evaluates the cost of moving to adjacent tiles g(n) and the estimated cost to the nearest food pellet h(n), always choosing the path with the lowest f(n) = g(n) + h(n). The frontier is managed using a Min-priority queue (Heapq) to guarantee optimal performance even on larger maps.

2. Custom Mechanics & Power-ups

The pathfinding isn't just about avoiding walls. The environment introduces unique elements that the AI must factor into its path calculations:

• Wall-Pass Power-up (Pie): When the agent collects a green Pie, it gains the temporary ability to move directly through solid walls for the next 5 steps. The algorithm dynamically adjusts its pathing graph to treat walls as traversable during this window.
• Corner Teleportation: The corners of the map act as connected nodes. Stepping onto a corner tile instantly teleports the agent to the opposite corner, providing potential shortcuts that the A* algorithm must evaluate when planning the global route.

Technical Architecture

• Language: Python 3.x
• GUI & Audio: Pygame is used to provide a smooth, step-by-step animation of the pathfinding process, complete with retro sound effects for food collection and power-ups.
• Data Structures: Python's built-in heapq module powers the Min-priority queue, ensuring high-speed access to the most promising nodes in the A* frontier.
• Map Parsing: The grid layout is highly customizable. The simulation dynamically loads standard text files where different characters represent the starting position (P), walls (%), food (.), and power-ups (O).

Further Reading & Source Code

For a deep dive into the algorithmic implementation and to test the simulation with your own custom maps, please visit the repository: https://github.com/LPH1110/pacman-agent.