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.'"
Take note CS professors: writing a Pac Man ghost algorithm would be an awesome exercise.
There's no -1 for "I don't get it."
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().
A 30-year-old game featured AI more sophisticated than what you'll find in most games today.
In defense of games today, things where a whole lot easier when you were on a strictly 2D, non-altering, fully 100% visible plane, and where an AI that knows your exact position regardless of things like noise and line of sight wasn't considered unfair, and where the only abilities an AI had to worry about were "Move My XY coordinates to = Player XY Coordinates" -
Well I think you're getting the picture...
is currently in frightened mode
I read somewhere If pac-man leaves tile A entering tile B on the same clock pulse as a ghost leaving tile B enters tile A, the machine will switch their positions on that pulse; they never occupy the same tile.
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.
More sophisticated?
They are constrainted by the paths and when they have to make a choice they pick the one that gives the shortest straight line distance to their destination.
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.
based on being really good at the original pacman, achieving a high score was simply a matter of learning patterns, so they must not really be referring to the original pacman here because I think that algorithm must have been pretty simple. To be a great player on the original pacmac you run pacman through the same pattern every time in every level you've learned, hitting the energizer pellets precisely when you know you can always run the same pattern and eat the four ghosts as the flee. Always the exact same pattern for each level until you finally reach a level where you have to learn the pattern. It was really crazy playing because you could do all the levels you'd memorized pretty much with your eyes closed, so when you got really good; it took a frigging long time to get to a level you did not know.
Did you ever wake up in the morning, with a Zombie Woof behind your eyes? -- FZ
>Well, the behavior is complex in today's games, but the algorithms are not.
Study up on the path-finding, grouping, and line-of-sight algorithms in "today's games", before you lodge this kind of insult at their developers please.
-fb Everything not expressly forbidden is now mandatory.
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.