Become a fan of Slashdot on Facebook

typodupeerror

## Pac-Man's Ghost Behavior Algorithms194

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.'"
This discussion has been archived. No new comments can be posted.

## Pac-Man's Ghost Behavior Algorithms

• #### Programming lesson (Score:5, Insightful)

on Friday December 03, 2010 @07:03PM (#34438876) Homepage

Take note CS professors: writing a Pac Man ghost algorithm would be an awesome exercise.

• #### Re: (Score:3)

Writing a Pac Man MAN algorithm would be better.

• #### Re:Programming lesson (Score:5, Interesting)

on Friday December 03, 2010 @07:07PM (#34438914) Journal
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!
• #### Re:Programming lesson (Score:4, Funny)

on Friday December 03, 2010 @07:10PM (#34438954) Journal

Then you'll get one kid who goes "Aww man. I totally thought this was Ms Pacman! I built it with no sense of direction whatsoever!"

• #### Re:Programming lesson (Score:4, Funny)

on Friday December 03, 2010 @07:52PM (#34439308)

Don't be sexist. Chicks hate that.

• #### Re: (Score:2)

on paper...
• #### Re:Programming lesson (Score:5, Funny)

on Friday December 03, 2010 @07:52PM (#34439312)
Ms. Pacman might not have a sense of direction. Mr. Pacman also has no sense of direction but he won't pull over to ask for help.
• #### Re: (Score:2)

That's the one where Ms. Pacman keeps stopping to ask for directions, right?
• #### Re:Programming lesson (Score:4, Informative)

on Friday December 03, 2010 @07:14PM (#34438986) Journal
A.K. Dewdney came up with a similar idea back in 1984. It's called corewars [corewars.org].
• #### Re: (Score:3)

There's absolutely nothing in common between these. Core Wars are about trying to overwrite each other's code, the exercise GP proposed has programs secure about their integrity and controlling something in a model -- not that different from, say, Chess.

• #### Re: (Score:2)

I remember my high school Pascal teacher introducing something like the above-mentioned AI algorithm game. Each person writes an algo' to "defeat" the other person's bot.

Mmmm... google is my friend P-Robots [sources.ru]
• #### Re: (Score:2)

Perhaps a better site: P-Robots [corewar.co.uk]
• #### Re: (Score:3)

Considering there's 4 vs 1 and only 4 orthogonal directions you can go the ghosts have a clear advantage if they work together properly.

• #### Re: (Score:2)

Already similar things out there but with robots, not pacman. Here's one of the more popular Java/.NET versions:

http://robocode.sourceforge.net/ [sourceforge.net]

This wasn't the first. There are a whole stack of them for the C language.

• #### Re:Programming lesson (Score:5, Interesting)

on Friday December 03, 2010 @09:53PM (#34440436)

Take note CS professors: writing a Pac Man ghost algorithm would be an awesome exercise.

I wrote a PacMan in GWBasic when I was around 13 or so.

The Ghost algorithm was one of the more interesting problems. The chase rules were simple... at each intersection the ghost chose to move towards pac-man, with the one caveat that it wasn't allowed to simply reverse direction. There was also a smallish random chance that the ghost would go a different direction if available.

This made them mostly but not entirely predictable, and also helped break them up when multiple ghosts ended up in the same place behind pac-man. And was the only way they used the left-right 'teleporter'

It worked well enough and by fine tuning the random chance of going in a random direction I was able to get a pretty satisfactory game.

The algorithm was actually based more on my observations of lode-runner than of PacMan. (I desperately wanted to be able to write a lode-runner type game, but I was self-taught... and didnt' under stand data modelling. My pacman sprites navigated the maze by acutually looking a the pixel colors around them... white was a wall.

My next project was tetris a couple years later, in pascal, with the same sort of inspect the pixels to see if a row was complete, and to stop falling, see if rotations were allowed, etc.

I remember having the data model epipaphany when I was trying to write a variable width font word processing thing (again in basic), and I couldn't for the life of me figure out how to support 'backspace'; looking backwards at the screen and comparing the pixels with the bitmaps for the different letters was simply a mess...hmmm... instead of simply drawing the letters as I type and moving the cursor forwards what if I put the letters I typed into a string as well... ooooooooooh.

A real personal Eureka moment there.

• #### Re: (Score:2)

By coincidence, I've been working for the past 6 months on a port of Pac-Man to the Intellivision platform (CP-16010 CPU). I've based much of my game logic on the insight I gained from reading Jamey Pittman's The Pac-Man Dossier.

An even bigger coincidence is that this weekend I had started working on Ghost AI.

-dZ.

• #### Re: (Score:3)

the insight I gained from reading Jamey Pittman's The Pac-Man Dossier. [gamasutra.com]

FTFY. The article is fantastic and really deserves linkage.

• #### Re: (Score:2)

Congratulations on your ownership of Microsoft Basic PDS 7. It was a fine toy back in the day.

• #### Programming lesson: early examples (Score:2)

Laurentius de Voltolina meets Pac-Man [handyvandal.com]

Pac-Man's Last Supper [handyvandal.com]

• #### Always fascinating. (Score:3, Interesting)

on Friday December 03, 2010 @07:06PM (#34438906)

I've known about this for years, but it's still quite fascinating. A 30-year-old game featured AI more sophisticated than what you'll find in most games today. Or at least AI appears more stupid and easier to foil today.

If I remember correctly Ms. Pac-Man added a randomization factor to avoid ghosts falling into set patterns.

• #### Re: (Score:3)

I remember there were special patterns which made cool things happen.

If you moved just the right way, then as you came down a corridor, you would go through one of the ghosts. It had to be some sort of "collision detection" bug or optimization. How the first person isolated it and documented it (at a quarter a game), who knows.

There were 30 of them in the book I bought. I was much better at Ms pacman than pacman (but only like level 12 or 13).

• #### Re:Always fascinating. (Score:4, Informative)

by Anonymous Coward on Friday December 03, 2010 @07:25PM (#34439102)

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.

• #### Re: (Score:3)

That is correct. On an unrelated note, I discovered I was a nerd when I found myself reading up on Pac Man AI a few years ago.

• #### Re: (Score:2)

That is true. It is reproducible typically after a level has been playing for a while (during Cruise Elroy), when Blinky is going at the same speed as Pac-Man. It's pretty cool. It's predictable enough that there are some patterns exploiting this feature.

-dZ.

• #### Re: (Score:2)

That is correct. The varying speeds of pacman and the ghosts are also done using bit strings rather than fixed point arithmetic.
• #### Re:Always fascinating. (Score:5, Insightful)

on Friday December 03, 2010 @07:13PM (#34438974) Journal

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().

• #### Re: (Score:3)

Yeah, it might seem easier to foil some current game AI, but only because the gameplay allows you way more options than just "move in one of 4 directions." If Pac-Man had a gun and could drop proximity mines, the ghosts would seem a lot less intelligent.

• #### Re: (Score:2)

In most games they're not going to be that complex, otherwise you'd lose most of the time, or it stops getting fun.

Because most games humans play can be mastered by computers.
• #### Re:Always fascinating. (Score:5, Insightful)

on Friday December 03, 2010 @07:14PM (#34438982) Journal

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...

• #### Re: (Score:3)

AI today is significantly more complex and sophisticated. It is playing much more complex games against you. I can assure you that this is almost a purely 'oh the good old days' sort of thinking.

• #### Re:Always fascinating. (Score:5, Insightful)

on Friday December 03, 2010 @07:49PM (#34439288)

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.

• #### Re:Always fascinating. (Score:5, Insightful)

on Saturday December 04, 2010 @02:52AM (#34441836)

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.

• #### Re: (Score:2)

The thing is though, is that it isn't complex, it is actually quite simple. The beauty of the algorithm is that it produced complex and interesting behavior using minimal resources, that behavior however is absolutely predictable and exploitable to top-level players. There is a charm to the lack of randomness though, and even the modern Champion Editions of Pac-Man, use very similar chase algorithms to the originals, and thus share the deterministic nature of the originals.

I can't read the actual article si

• #### NAM-CAP (Score:2)

Back in those days, we didn't have fancy graphic systems like CGA so I had to make do with VT100 and NCURSES. My ghosts were reverse video double quotes which looked good enough. Unfortunately, the 9600 baud transfer rate only allowed 2 ghosts to be playable. With that in mind, I put together a really simple chase algorithm:

1. When a ghost comes to an intersection, if it can turn towards the player, it does except randomly 1 in 4 times it turns another direction.
2. If it can't turn towards the play it pick
• #### Re: (Score:2)

When you can beat bastard mode tetris, get back to me...

• #### Re: (Score:2)

What this reminds me of more than anything is the AI in Halo. You have a number of enemy types with comparatively simple behaviour rules, and if the game featured any one of them alone it'd be very dull indeed, like a game of Pacman where all the ghosts behave like Blinky. But the enemies are always presented in mixed groups - an Elite, several grunts, a couple of Jackals - and there's great synergy in the combination. If you can land a plasma shot on the Elite then you can take him down quickly and the gro

• #### Crush roller (Score:3)

on Friday December 03, 2010 @07:08PM (#34438932) Homepage Journal

The most interesting behavior that i recall in those arcades was crush roller's. Only 2 "ghosts" but damn clever.

• #### Re: (Score:2)

The most interesting behavior that i recall in those arcades was crush roller's. Only 2 "ghosts" but damn clever.

I agree. Those fish were way smarter than the PacMan ghosts.

• #### Chase, scatter, frightened .... (Score:2)

... Otherwise known as snog, marry, avoid. :-)
• #### Save the best for last... (Score:3)

on Friday December 03, 2010 @07:24PM (#34439086) Journal
FTA

One final special case to be aware of are the four intersections that were colored yellow on the simplified maze diagram. These specific intersections have an extra restriction — ghosts can not choose to turn upwards from these tiles. If entering them from the right or left side they will always proceed out the opposite side (excepting a forced direction-reversal). Note that this restriction does not apply to Frightened mode, and Frightened ghosts may turn upwards here if that decision occurs randomly. A ghost entering these tiles from the top can also reverse direction back out the top if a mode switch occurs as they are entering the tile, the restriction is only applied during “regular” decision-making. If Pac-Man is being pursued closely by ghosts, he can gain some ground on them by making an upwards turn in one of these intersections, since they will be forced to take a longer route around.
• #### It appears their web server (Score:5, Funny)

on Friday December 03, 2010 @07:25PM (#34439100)
is currently in frightened mode
• #### Breaking news!!!! (Score:5, Informative)

on Friday December 03, 2010 @07:32PM (#34439170) Homepage

Yawn... This stuff that already been posted on the Pacman Dossier [comcast.net] 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 [google.com], 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.

• #### Re: (Score:3)

Yup. At the end the writer cited the two sources where he got his info from: Jamey Pittman and Don Hodge. I have no idea what the purpose of that write-up is because the writer did not add any new or original information. A link or two would have been sufficient.
• #### Re: (Score:2)

I think his explanation of the the targeting decision of Inky was more accessible than Jamey Pittman's. I love The Pac-Man Dossier, and it has proven indispensable in writing my own Pac-Man port for the Intellivision (my current project). However there are some parts, like the doubling of Inky's target direction-vector based on Blinky's position, that were either under-defined, or not very clearly explained.

I've re-read that section of the Dossier multiple times to make sure I understood it completely, bu

• #### Interesting but from my memory (Score:4, Interesting)

on Friday December 03, 2010 @07:55PM (#34439340) Journal
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.
• #### Re:Interesting but from my memory (Score:5, Informative)

<VortexCortex.project-retrograde@com> on Friday December 03, 2010 @09:57PM (#34440460)

Following exact patterns work because that generates the same exact pseudo-random number pool that the ghosts use to pick directions.

• #### Re: (Score:2)

Actually, i think they are referring to the original. The random number generator was pseudo-random. If you kept your pattern right, it would always pick the right ones.
• #### Re: (Score:2)

Did you read the Pacman Dossier [comcast.net] linked from TFA? They specifically say how the best player in the world doesn't play by memorising a pattern, because that's too inflexible. If you make a mistake while executing the pattern, memorisers are at loss to how to recover from that mistake. On the other hand, learning ghost behaviour allows you to adapt much better and removes that inflexibility, and this is how the best player in the world racked up a perfect score.
• #### Pac Men's heath magazine (Score:2)

If you don't want to be this http://www.nextnature.net/2008/01/pacmans-skull/ [nextnature.net] quit eating this http://truckbearingkibble.com/comic/2008/06/17/pellets-of-langerhans/ [truckbearingkibble.com]

#### Related LinksTop of the: day, week, month.

"I'm not afraid of dying, I just don't want to be there when it happens." -- Woody Allen

Working...