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

Comments

Programming lesson

[MrEricSir]

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

Re:Programming lesson

[Monkeedude1212]

Writing a Pac Man MAN algorithm would be better.

Re:Programming lesson

[Rickz0rz]

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

[Monkeedude1212]

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

[camperdave]

A.K. Dewdney came up with a similar idea back in 1984. It's called corewars.

Re:Programming lesson

[KiloByte]

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:Programming lesson

[Shikaku]

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:Programming lesson

[Anonymous Coward]

Shut up.

Re:Programming lesson

[CharlyFoxtrot]

Don't be sexist. Chicks hate that.

Re:Programming lesson

[seeker_1us]

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:Programming lesson

[Monkeedude1212]

It's been scientifically proven that statistically men have better 3D perceptualization than women - yes some women are better at it than men, but when you plot it all out you get the regular bell curves, and men typically have higher preforming scores.

So it's not like jokes revolving around a woman's ability to park a car, or judging how far away an object is, or any of the things that seem to be related to navigation - they do have SOME foundation to it. (if you don't believe me, Google "Women's Depth Perception")

Much in the same way that colourblindness is strictly a male thing - if a woman is colourblind, it typically means that some dominant male gene actually took control when their eyes developed, which is quite rare in women. But also in Women its rare that they sometimes get a 4th "cone" in their eye that helps identifying in colours. This is why women tend to be better at items like interior design and Fashion, so the jokes about how "Men can't dress themselves" also have a good foundation. Like before, "some men are better than women at that sort of stuff" - but statistically speaking, this is a good strong point for women.

So - now that the science is out of the way - what does this have to do with Offensive jokes? That's the thing, they are just jokes. I mean in it in a light tone and while some might take it as derogatory, there are any number of things someone could make fun of me for (as you might have pointed out, my apparent lack of tact and manners!).

It boils down to this: do I value a good joke over someone elses potential feelings? Personally, I do enjoy a good joke. I think that the enjoyment it brings to me and others outweighs the possible negative feelings that a small contingent might actually feel - after all not ALL women are offended by such jokes.

A wise man once said... well I can't remember the exact words, but it was something along the lines of "Wisdom starts with humility". If you can't laugh at yourself than thats something you should work on. Recognising your shortfalls is the first step to overcoming them.

Now - the biggest problem I have with people is when they can't seperate Discrimination, prejudice, or harassment from humour. Like when you're at an Open source conference, and you're a women, like the article you linked. Guys taking upskirt photos of women? Yeah sexual harassment. Ignoring females because they are believed to be non-technical? Yeah discrimination. A picture of a girl in a Bikini during a slide show to say "That was just to get your attention" - Thats humour! It's meant in light fun, I bet if you had enough girls around you'd find them chuckling at the idea as well.

Point is - people need to lighten up. If more people could understand the difference between humour and harassment - the world would be a much better, and funnier place.

Re:Programming lesson

[Anonymous Coward]

Top scientists think the reason decreased depth perception arose in women is because of the thousands of years men have been convincing them that something 5inches long is actually 8inches.

Re:Programming lesson

[vux984]

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:Programming lesson

[masterzora]

It's been scientifically proven that statistically men have better 3D perceptualization than women - yes some women are better at it than men, but when you plot it all out you get the regular bell curves, and men typically have higher preforming scores.

Really now? Can you link me to a few unbiased studies the topic with statistically significant sample sizes and shows results of men having, not only higher scores, but statistically significantly higher scores? I assume, of course, that you also have available the justification for why we can trust the tests to be testing purely for 3d perceptualisation, without testing for additional unrelated factors (such as how well you can decipher difficult instructions, a common additional factor in such tests). And I also trust that these studies have properly isolated for sex, ensuring that additional factors such as training and practice in related skills or a lifetime of "you can do anything" vs. "oh, you're just a girl" have no bearing on the final results?

I'll be rather impressed if you can show me any such study. Now, I'll be the first to admit that not all people are created equal and that it is quite possible that people of different sexes and genders and races and sexual orientations have some amount of differences. However, I think you'll find that most of these studies in these topics are entirely inconclusive after you consider all of the factors surrounding them.

It's also worth noting the striking parallels to the number of 19th century studies "proving" that black people were strictly inferior to white people. Confirmation bias can prove anything, as it turns out.

Re:Programming lesson

[fishexe]

It's awful that some people have gone so far off the deep end that simple jokes cannot be told without questioning their intentions.

I don't think anyone was questioning the intentions. They were questioning the effects that such jokes have on the culture, particularly when they are so one-sidedly against women all the time. It's great that you're an equal-opportunity offender and I salute that, but the FOSS community as a whole is not. Even if the individual jokes themselves are all meant in good fun, taken together they create a boys'-club atmosphere that is not healthy to the growth of the community.

On the other hand, folks are overly sensitive about some things. No one granted anyone the 'unalienable right' to not be offended. Some shit offends me too, but I get over it.

I would re-read the link notionalTenacity posted. It isn't about safeguarding the right not to be offended, because of course no such right exists. It's about creating an environment that encourages all to participate, which is not something we have a "right" to but would be a very smart thing for the FOSS community to foster.

Have you tried getting over it and trying to have a sense of humor? Not about things like the dude sticking his hand down the chick's pants....that's messed up and he should at least have the hell beaten out of him a few good times for it. About things like "hur hur, women ain't got no direction smarts!"

You don't think the two are related? Really, would a man really try to stick his hand down a woman's pants at a conference where people didn't make repeated jokes about the entire female sex and there weren't pictures of women in bikinis in the presentations? One sexist joke is harmless, if it's the only one, but that kind of pervasive behavior creates an environment where men literally think, "these women are here to pleasure me, not to participate in tech talk", and that mindset leads directly to the odd one attempting the ol' scoop-n-grab.

Re:Programming lesson

[wootest]

If someone says "stop being an asshole" and your conclusion is "but then I will have nothing to say", what the hell is wrong with you?

I am continually amazed with what people defend this behavior with. You don't need to be devoid of humor or steeped in forced neutrality, you don't need to stop speaking your mind or fear that you can't have an open and honest discussion. You just need to stop being a dick. (Which would probably help any arguments you're trying to make in any case.)

("You" doesn't refer to parent or grandparent; it's just a placeholder. "One" doesn't sound good.)

Re:Programming lesson

[BeanThere]

Domestic violence is serious and the vast majority of it is man-on-woman.

That is a common myth, there is a significant percentage of women-on-men violence, and many studies and meta-studies suggest the rates may be equal.

"Martin S. Fiebert of the Department of Psychology at California State University, Long Beach, provides an annotated bibliography of over two hundred scholarly works which demonstrate that women and men often exhibit comparable levels of IPV violence.[110] In a Los Angeles Times article about male victims of domestic violence, Fiebert suggests that "...consensus in the field is that women are as likely as men to strike their partner but that—as expected—women are more likely to be injured than men."[111] However, he noted, men are seriously injured in 38% of the cases in which "extreme aggression" is used." (http://en.wikipedia.org/wiki/Domestic_violence#Gender_aspects_of_abuse)

Women-on-men violence is both common, and extremely serious. In fact, in some ways it is more serious, because society not only all but ignores it, there is a tendency to regard it as funny, so men are additionally humiliated.

http://www.dvrc-or.org/domestic/violence/resources/C61/#mal

Surveys find that men and women assault one another and strike the first blow at approximately equal rates.

Men and women engage in overall comparable levels of abuse and control

http://www.oregoncounseling.org/Handouts/DomesticViolenceMen.htm

In 100 domestic violence situations approximately 40 cases involve violence by women against men.
http://www.silentwitness.net/sub/violences.htm

Never assume something is a fact just because you've heard it repeated a billion times before.

Re:Programming lesson

[aamcf]

Gay, Straight, and the Reason Why: The Science of Sexual Orientation covers various physical and psychological differences between males and females. Pages 107 to 109 refer to the studies that may be of interest to you.

Re:Programming lesson

[djupdal]

And I also trust that these studies have properly isolated for sex, ensuring that additional factors such as training and practice in related skills or a lifetime of "you can do anything" vs. "oh, you're just a girl" have no bearing on the final results?

But that is not really necessary if you simply want to know something about the current population. If the cause of the observed difference (if any) is environment or inheritance is really a different thing.

Re:Programming lesson

[thesandtiger]

While there have been numerous studies showing that there is a statistically significant difference between women and men in regards 3D thinking, that statistically significant difference turns out to not be particularly meaningful when taken out of the lab and applied to real-world activities. It's the same for the studies that prove that women have a statistically significant edge over men when it comes to processing language - women have the edge in controlled experiments, but when brought into the real world the edge is lessened.

What's interesting, however, is that this difference translates in many cases to a preference to engage in activities that utilize each sex's advantage. Men will frequently gravitate towards areas where the mental manipulation of 3D is done, women to areas where communications are important. This increased exposure over time leads to advantages that, over time, become both statistically significant AND meaningful.

On a side note, another interesting factor that comes into play in the experiments is that when people are told, prior to taking the tests in the experiments, "Your gender is really bad at this stuff, so don't feel bad if you have difficulty," there is a negative effect on performance - but it's only a significant (and meaningful) effect with women. On the flip side, when women are told "Women are really good at this stuff, so you shouldn't have any trouble at all," women performed just as well as their male counterparts! Men, when told they have a better natural facility, tended to not improve much.

How much of that seeming immunity to social expectation is natural in men, vs. learned? How much of the ability to be greatly affected by expectations is natural in women, vs. learned? It's hard to say - experiments trying to figure that out are rather hard to design, since by the time we're able to communicate such concepts people have already been greatly socialized.

The takeaway from all of this is that while there are differences between the genders in their natural aptitudes, those differences, outside of reinforcement through life experience, are not meaningful. It's the life experience that builds on natural advantages that makes things different as well as the social environment surrounding individuals in that environment.

An environment where one group is continually told, even in jest, that they are bad at certain tasks or likely to find them difficult because of our gender can actually over time lead to rather skewed demographics. It also makes it understandable why you'll often hear "But I was only joking!" from guys when women are taking those jokes seriously - guys performance is less affected by social expectations, so jokes about those expectations can have less of an impact.

Full disclosure: I'm a woman and a research scientist, reasonably facile with maths, and because I've been an avid gamer since I was about 6 and my folks brought home an Apple ][, my spatial reasoning and mental 3D manipulation abilities are pretty decent when working in the abstract. Yet, funny enough, I am absolutely the WORST driver on the planet, and my colleagues know to give me an extra 10 minutes when attending meetings on East Campus because I still manage to get lost in the maze of nearly identical buildings over there.

Re:Programming lesson

[fishexe]

Thanks. The other guy contesting my claim presented no evidence other than his own certainty; what you've given me is much more useful in adjusting my beliefs.

Re:Programming lesson

[vidnet]

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

FTFY. The article is fantastic and really deserves linkage.

Always fascinating.

[MaWeiTao]

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:Always fascinating.

[Maxo-Texas]

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.

[DIplomatic]

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:Always fascinating.

[Monkeedude1212]

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:Always fascinating.

[cowscows]

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:Always fascinating.

[Anonymous Coward]

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:Always fascinating.

[Surt]

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.

[nedlohs]

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.

[Surt]

But there are behavior trees handling a huge number of potential situations, as well as a lot of good games doing things like genetic algorithms to try to find new behaviors. There's a lot, lot more going on there than pacman's 3 state AI.

Re:Always fascinating.

[fishbowl]

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

Re:Always fascinating.

[Bozzio]

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:Always fascinating.

[zippthorne]

That's hardly a fair criticism. It's if-then-else all the way down, no matter how complex you make it...

Furthermore, it's not the complexity, but the simplicity of the pac-man monster rules that is impressive, specifically just how challenging and fun and unpredictable a game could be with basically four simple rules and a maze.

Re:Always fascinating.

[MMORG]

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:Always fascinating.

[dzfoo]

>> We don't use path-finding algorithms to move around objects. We use spatial memory and common sense, two things game AI lacks.

Are you aware that modern games attempt to mimic precisely this? The behavioural systems are much more complex than they were back in the early days of Pac-Man--not necessarily because the programmers didn't know how to do it, but because the systems did not offer enough computational resources to accomplish it.

          -dZ.

Crush roller

[marcello_dl]

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

Save the best for last...

[Rooked_One]

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

[RapidDemon]

is currently in frightened mode

Breaking news!!!!

[mrsam]

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.

Re:Breaking news!!!!

[assantisz]

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.

Interesting but from my memory

[al0ha]

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

[VortexCortex]

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