Christopher TraftonGet in touch
All work

Fall 2024 · Algorithm Designer

Pacman Path Search

Classic search algorithms (DFS, BFS, uniform cost and A*) implemented to guide Pacman through mazes, including a shortest route that eats every dot.

Role
Algorithm Designer
When
Fall 2024
Discipline
AI & ML

Built with

  • DFS
  • BFS
  • Uniform Cost Search
  • A*
  • Heuristics
Pacman in a blue maze full of dots, with a score of 960.

Overview

Four search algorithms solving the same Pacman mazes. Each picture shows which cells the algorithm explored before it found the goal; brighter cells were explored earlier.

Depth-first search exploring a maze

Depth-first search follows one branch as deep as it goes before backing up.

Breadth-first search exploring a maze

Breadth-first search explores every cell at one depth before going deeper.

Uniform cost search exploring a maze

Uniform cost search always expands the cheapest route so far.

A* search exploring a maze

A* adds a heuristic estimate of the remaining distance to decide which branch to try next.

Eating every dot

The final problem uses A* to find the shortest path that collects all of the dots in the maze.

Pacman following the shortest path that collects every dot

Pacman clearing the maze.