The other day, I was reading through the course syllabus for a second-year AI class, as one does, when I noticed that the assignment for the sixth week was to turn in a working version of PacMan. Which is kind of weird, because the actual algorithm for PacMan involves more or less zero AI. It involves something else, and one of my favorite words: stigmergy.

Alright, so, here's the algorithm in a nutshell: PacMan is played on a 29-by-26 square grid of cells. Everything else is special effects. There is a clock cycle: every cycle, the characters move from one square of the grid to another. If PacMan and a ghost share the same cell in a cycle, PacMan loses a life. There's an animation engine running to make it look smoother than it is, but that's the basic game.

The grid is actually three different grids layered together: One grid constrains movement by providing the walls. One grid tracks the dots that have been eaten. (The actual end-of-round tracking is done with a counter.)

The last grid is the stigmergy grid: every clock cycle, PacMan moves forward in a direction. The grid he just left is given a number: 255. Every clock cycle, the stigmergy grid is scanned for these numbers, and they're reduced according to some formula until they reach zero. A ghost wandering the maze has a few rules: when it reaches a cell that has more than one neigbor, it chooses a direction based on a formula, and part of that formula includes adding in the stigmergy number of the neighboring cells. Blue ghosts use a reverse strategy; "dead" ghosts use a simple vector-weight strategy to go back to the center room.

In short, the ghosts are following PacMan's scent, in much the same way ants follow a trail laid down by other ants.

There's also a clock-cycle counter that causes the ghosts to reverse themselves from time to time, but that's the basic gist of it. Unfortunately, the random number generator is seeded with the same number every level, so it became possible to master the game and play infinitely long. As smooth as the game looks, you actually have half a second of leeway time between moves, which is well within the average video gamer's skill to master. Ms. PacMan fixed the seeding issue, and the game is significantly harder to play for a long time.

That's it. You could implement PacMan in a few hundred lines of Javascript and HTML. Some animate CSS using the FLIP trick would be awesome. There's no magic, and certainly no AI about it.