Slashdot Mirror
Pac-Man's Ghost Behavior Algorithms
An anonymous reader writes "This article has a very interesting description of the algorithms behind the ghosts in Pac-Man. I had no idea about most of this information, but that's probably because it's difficult to study the ghosts when I die every 30 seconds. Quoting: 'The ghosts are always in one of three possible modes: Chase, Scatter, or Frightened. The "normal" mode with the ghosts pursuing Pac-Man is Chase, and this is the one that they spend most of their time in. While in Chase mode, all of the ghosts use Pac-Man's position as a factor in selecting their target tile, though it is more significant to some ghosts than others. In Scatter mode, each ghost has a fixed target tile, each of which is located just outside a different corner of the maze. This causes the four ghosts to disperse to the corners whenever they are in this mode. Frightened mode is unique because the ghosts do not have a specific target tile while in this mode. Instead, they pseudorandomly decide which turns to make at every intersection.'"
Or half of the class writes ghost algorithms while the other half writes an algorithm controlling pac-man himself, and then the algorithms are pitted against each other!
A 30-year-old game featured AI more sophisticated than what you'll find in most games today.
I'm not sure "deciding whether to turn right or left at the fork in a 2D maze" can really compare to the ridiculously complex AI behavior in many games today. Team combat, terrain navigation, etc. Advance-to-cover squad-based tactical combat is hardly If PAC_MAN_INVINCIBLE == FALSE; Chase().
is currently in frightened mode
Yawn... This stuff that already been posted on the Pacman Dossier for years. Not really "news for nerds".
Now, what would really be "news for nerds" is the analysis of the ghosts' behavior in Google Pacman, which is very similar, but subtly different.
Of course, since Google Pacman's source is available, this can theoretically be deduced straight from the source, but it's more fun to figure it out by trial and error. Great timekiller. There are definitely notable differences -- like certain directions the ghosts will never turn to if they enter the intersection from one direction, but will if they enter the same intersection from the opposite direction.
Following exact patterns work because that generates the same exact pseudo-random number pool that the ghosts use to pick directions.
In other words they are retarded, which is good because there are four of them and they'd box the player in in about 10 seconds if they weren't.
Yes. There's this persistent myth that smart game AI is hard to build. It's not. A really smart, impossible-to-beat game AI is easy to build (for most types of games). What's hard to build is a sort-of-smart-but-often-fallible AI that's just competent enough that it makes you feel like you're accomplishing something worthwhile when you finally beat it. For extra bonus hardness points you can try building an AI that makes the same kind of sub-optimal choices that a human would make so that it feels "alive". That's hard to do.
Game AIs have all kinds of advantages that make it easy (again, for most types of games) to build them to be unbeatable. They have always have instant reaction time, they can consider a large number of disparate data streams simultaneously, they always have perfect knowledge of their environment, they can have vast libraries of pre-computed decision trees, and their accuracy in moving, aiming, etc is limited only by the precision of floating-point data types. (An aside: the reason why real-world robotics is so hard is largely because real-world robots have really terrible knowledge of their environment, unlike game AIs.) The trick to writing a top-quality game AI is to figure out how to degrade and handicap all of those advantages in ways that leave them beatable while not leaving them looking stupid.