Pac-Man AI
ABOUT THIS PROJECT
An agent that plays a Pac-Man-style game on its own, and usually wins.
The goal was an autonomous agent, not a hard opponent: Something that reads the board, picks a route, and commits to it. It finishes with an 84% win rate in AI-vs-environment mode, and most of the remaining losses come from situations where every route is already cut off.
Building the maze graph
Walked the tile grid directly into a HashMap keyed by coordinate, then checked the four neighbours of every PATH tile to add edges. A BFS or DFS discovery would also have worked, but nothing downstream depends on visiting tiles in a particular order, so the straight iteration is simpler to reason about and cheaper than maintaining a frontier just to end up at the same graph.
A heap with an index map
The priority queue is a binary min-heap in an ArrayList paired with a HashMap from each element to its current index in that heap. That pairing is the whole point: without it, decrease-key has to scan the heap linearly to find the entry, and decrease-key is the operation Dijkstra performs most. Both invariants, heap order and the index agreeing with the heap, are written out and checked in assertInv.
Shortest non-backtracking path
Dijkstra over that queue, with the reverse of the previous edge excluded from consideration. Without that constraint a pursuer can resolve an awkward route by reversing on the spot, which is optimal on paper and reads as broken to a player watching a ghost turn around in a corridor.
The agent, and measuring it
PacMann runs a BFS out to the nearest dot that is not within a set radius of any ghost, so it prefers safe progress over greedy progress. If no safe target exists it falls back to the nearest dot regardless, because a policy with no fallback stalls and loses on time rather than on being caught. While ghosts are in FLEE it inverts and hunts them instead. A batch runner plays repeated non-interactive games and prints wins over total, which is where the 84% comes from rather than from one lucky session.
MORE PROJECTS
Hex Minesweeper
puzzleSpace Shooter
arcade
2025 – nowNexus Rush
roguelike tower defenseDuke vs The Gang
2D actionCrush the Hero
stealth puzzleCumulo-Climb
platformerGhostLine
platformerGreenPlate
web app