?

Log in

No account? Create an account
entries friends calendar profile Elf Sternberg's Pendorwright Projects Previous Previous Next Next
PacMan doesn't need AI - Elf M. Sternberg
elfs
elfs
PacMan doesn't need AI

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.

3 comments or Leave a comment
Comments
mg4h From: mg4h Date: October 14th, 2016 06:55 pm (UTC) (Link)
Ah! That explains why while I could memorize the pattern for PacMan, I had to adapt the rules for Ms PacMan. It still *had* rules, but it didn't start each map the exact same way - so I had guidelines on which part of the map to clear out first, but the ghosts didn't always cooperate so it changed up.

I always wondered about that. Thanks!
resonant From: resonant Date: October 15th, 2016 09:15 pm (UTC) (Link)
Quite clever, compared to how it would be done today by a new grad.
omahas From: omahas Date: October 16th, 2016 04:28 pm (UTC) (Link)
I believe that idea behind asking students to develop an AI for PacMan was to learn about AI using an old game that everyone knows and respects/likes in some way. It would also be relatively simple to do. So students learn some basics of AI using something they all know and should be able to do.
3 comments or Leave a comment