×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Pac-Man's Ghost Behavior Algorithms

Soulskill posted more than 3 years ago | from the i-hate-the-pink-one dept.

Classic Games (Games) 194

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

cancel ×
This is a preview of your comment

No Comment Title Entered

Anonymous Coward 1 minute ago

No Comment Entered

194 comments

Programming lesson (4, Insightful)

MrEricSir (398214) | more than 3 years ago | (#34438876)

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

Re:Programming lesson (2)

Monkeedude1212 (1560403) | more than 3 years ago | (#34438884)

Writing a Pac Man MAN algorithm would be better.

Re:Programming lesson (5, Interesting)

Rickz0rz (831049) | more than 3 years ago | (#34438914)

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 (3, Funny)

Monkeedude1212 (1560403) | more than 3 years ago | (#34438954)

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 (-1, Offtopic)

notionalTenacity (1526919) | more than 3 years ago | (#34439212)

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!"

Here's an interesting article you might like to read, which covers the area of sexism etc. Considering this sort of thing is topical in the community at the moment, you might like to consider whether your joke could have unintended consequences. Maybe a joke is just a joke, I'm not sure - but its food for thought. http://lwn.net/SubscriberLink/417952/306ab90f60276bf2/ [lwn.net]

Re:Programming lesson (2, Funny)

Anonymous Coward | more than 3 years ago | (#34439264)

Shut up.

Re:Programming lesson (0, Offtopic)

hedwards (940851) | more than 3 years ago | (#34439370)

And I'm sure that the GP will care as soon as women start caring about the unintended consequences of all the sexist things they say and do. It's really easy to be sanctimonious if you're OK ignoring the hypocrisy involved with it. Personally, I'd take sexism significantly more seriously if I wasn't expected to put up with so much sexual harassment and jokes that are far worse than the one the GP made.

I'm sure that there are some women out there that genuinely consider sexism to be wrong and do their best not to involve themselves in it either way, but I don't see them because that's a subtlety that isn't particularly easy to pick up on. What I do however see is the leering, the sexist comments about what scum men are and how serious domestic violence is, but mysteriously defining it as man on woman.

Re:Programming lesson (0, Offtopic)

moexu (555075) | more than 3 years ago | (#34439470)

I care about the consequences of sexism towards men, FWIW. I had a female supervisor who used to say sexist things and expect me to agree with them when a) I didn't and b) there were 8 guys in the room that I had to work with. It was very uncomfortable.

Re:Programming lesson (0)

notionalTenacity (1526919) | more than 3 years ago | (#34439884)

I sympathise with your post, in that some of the 'political correctness' brigade only care about sexism when it happens in the direction that negatively effects them. However, in so far as your post defends the GP, it does so purely on the basis of 'two wrongs make a right' - which isn't a very interesting argument.

Re:Programming lesson (-1)

fishexe (168879) | more than 3 years ago | (#34440398)

And I'm sure that the GP will care as soon as women start caring about the unintended consequences of all the sexist things they say and do. It's really easy to be sanctimonious if you're OK ignoring the hypocrisy involved with it. Personally, I'd take sexism significantly more seriously if I wasn't expected to put up with so much sexual harassment and jokes that are far worse than the one the GP made.

Could you give us an example?

I'm sure that there are some women out there that genuinely consider sexism to be wrong and do their best not to involve themselves in it either way, but I don't see them because that's a subtlety that isn't particularly easy to pick up on.

I am a man who frequently confronts other men when they say sexist things about women, and also confronts women when they say sexist things about men. You assume notionalTenacity must be a woman because he or she criticized a stupid generalization about women.

What I do however see is the leering, the sexist comments about what scum men are and how serious domestic violence is, but mysteriously defining it as man on woman.

Domestic violence is serious and the vast majority of it is man-on-woman. How is observing that empirical fact "mysteriously defining it" as such? Do the people you're talking about say, or even believe, that women can never commit domestic violence against men? Somehow I doubt it.

Re:Programming lesson (0, Offtopic)

dgatwood (11270) | more than 3 years ago | (#34440864)

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

Only if you define it narrowly to be reported physical domestic violence. If you look at it more broadly and include emotional abuse and unreported abuse, I think you'll find that men and women are roughly equal opportunity offenders. It just looks like it's mostly men on women because:

  • Statistically men are stronger than women on average. Thus men are far more likely to be able to physically overpower women than the other way around, and men are likely to cause more damage to women on average than the other way around.
  • Men are statistically less likely to put up with it and stay in the relationship, so domestic violence against men tends to be more distributed, making it harder to spot. You're less likely to notice that a girl gave a different guy a black eye every week than to notice that a girl has gotten a black eye every week.
  • Women are more likely to abuse people in ways that don't leave a physical scar. You know, like boiling your bunny.

Just saying.

Re:Programming lesson (3, Interesting)

Monkeedude1212 (1560403) | more than 3 years ago | (#34439424)

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

Anonymous Coward | more than 3 years ago | (#34439906)

She was probably jealous!

Re:Programming lesson (2, Funny)

Anonymous Coward | more than 3 years ago | (#34439938)

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

Anonymous Coward | more than 3 years ago | (#34440008)

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.

Like the vast majority of slashdotters talking about biology you're pulling shit out of your arse. The sex-linked colour-blindness genes are rarely (if ever) dominant, they are recessive. The term "male-dominant" gene doesn't mean anything.

Re:Programming lesson (1)

Schadrach (1042952) | more than 3 years ago | (#34440890)

Besides, to be more specific, color blindness is caused by a recessive gene on the X that isn't matched on the Y. So it's carried by women, but a woman has to inherit it from both parents to be colorblind, a man needs only inherit it from his mother, and a woman who is hybrid for it actually has better color perception that "normal", as the gene in question causes one type of cone to favor an abnormal color range. If a woman is hybrid for the gene, she gets both the normal and abnormal versions of the cone, causing her to see "extra" colors.

Re:Programming lesson (1, Troll)

notionalTenacity (1526919) | more than 3 years ago | (#34440018)

One great thing about hacker culture has always been the ideal that individuals are evaluated on their merits. How does the "Ms Pacman had no sense of direction because she was a Ms" type of thinking gel with this?

Now, you make a lot of good points there, many of which I agree with.

I agree that there has to be a distinction between harassment, and humour.

My concern is that its easy for people to accidentally create a culture which makes the people at the butt of the jokes feel bad. People often don't see that when they aren't at the receiving end.

The 'science' bit is irrelevant. I'm not in any way attacking the joke because of its scientific inaccuracy.

By way of analogy, statistically, black males have a higher tendency to do prison time in the united states. If the original context somehow the ghosts been in jail all the time, because they were black, would it be ok? What if slashdot had a strong neo-nazi sub-community - would that change how OK the joke was?

I think the context is important. I think in the current context of women feeling harassed in the open source community, we should think about whether such jokes are ok. There are few enough women in the community - thats fine, if thats their choice - but maybe we should err a little on the side of caution, to make sure the culture we create is welcoming for the rest?

Re:Programming lesson (0)

Anonymous Coward | more than 3 years ago | (#34440098)

I think the context is important. I think in the current context of women feeling harassed in the open source community, we should think about whether such jokes are ok. There are few enough women in the community - thats fine, if thats their choice - but maybe we should err a little on the side of caution, to make sure the culture we create is welcoming for the rest?

Oh yes. If there's ONE FUCKING THING WE NEED, it's another community so afraid of offending anyone, we walk around mincing words and generally acting like complete pussies. I work in the education field, and it's completely pathological there. You can get fired, directly or indirectly, for saying anything not politically correct. (Indirectly is a lot more common, by the by.)

That's not to say that we couldn't use more women in computer science, but it honestly doesn't have so much to do with off color jokes, but more with the boys' club status it currently has. Attend a SWE meeting some time and see for yourself.

Re:Programming lesson (1)

notionalTenacity (1526919) | more than 3 years ago | (#34440942)

I'm not advocating a community so afraid of offending, that nothing gets said.

I'm just point out that what you've got is a community thats not a nice place to be in, for one of the minorities in that community.

I'm not saying 'Thought Police - Make An Arrest!' - I just asked the OP to re-consider their comment, and how it might affect women within the community, in light of the current issues the broader community have.

There's a difference between people having the freedom to say what they want, and thinking that all things are equally good to say.

Re:Programming lesson (-1)

Anonymous Coward | more than 3 years ago | (#34440036)

Sexism is funny, rape victims are asking for it, black people just need to work harder, etc.

Stop making excuses for being a bigot.

Re:Programming lesson (0)

obarthelemy (160321) | more than 3 years ago | (#34440150)

you're assuming depth perception is the sole parameter in parallel-parking skill.

Re:Programming lesson (0)

Anonymous Coward | more than 3 years ago | (#34440716)

He's doing nothing of the sort. It's (obviously) at least a contributory parameter and (I think likely) one of the most important factors. But, even if it is only one of many, it still contributes, and therefore a statistical skew in depth-perception would manifest as a skew in parallel-parking skill.

Re:Programming lesson (0)

Sir_Lewk (967686) | more than 3 years ago | (#34440990)

No, he is suggesting that it is an important factor. As a male with very poor vision in my left eye, I can assure you it is quite important.

Next time you're trying to parallel park try closing one of your eyes. Will it be possible? Of course. It'll also be a shitton more difficult.

Re:Programming lesson (0)

Anonymous Coward | more than 3 years ago | (#34440860)

Much in the same way that colourblindness is strictly a male thing - if a woman is colourblind,

That would mean it actually is not "strictly" a man-thing, wouldn't it?

If you're going to post a diatribe about why you'll continue to tell and appreciate offensive jokes, I might recommend not contradicting yourself. That way, you'll distinguish yourself from the insensitive chauvinistic morons who also enjoy offensive humor.

Re:Programming lesson (3, Interesting)

masterzora (871343) | more than 3 years ago | (#34440896)

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

Daniel Dvorkin (106857) | more than 3 years ago | (#34441004)

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.

Men making misogynistic jokes aren't laughing at themselves. They're laughing at other people. That's pretty much the opposite of humility.

Re:Programming lesson (0)

Anonymous Coward | more than 3 years ago | (#34439694)

I make jokes about every race, creed, religion, gender, physical deformity....anything. Nothing is taboo to me. I've been known to make harmless jokes about women (things like the gp's comment and worse). I say them in a joking manner, and I make sure everyone knows that they're not off limits. It's awful that some people have gone so far off the deep end that simple jokes cannot be told without questioning their intentions. The people that began taking things too far should be shot because it fucks things up for the rest of us.

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

Re:Programming lesson (0)

notionalTenacity (1526919) | more than 3 years ago | (#34440034)

Yeah, I hear you.

I'm just concerned about the accretion of such jokes into the community culture. (see my other post).

We aren't talking about rights - I dont want anyone jailed or chastised! I'm just asking people if this is the sort of culture we want to create - because the jokes we make, and upvote, effect the culture we create, and how welcoming it might be to women.

And right now, open source has some questions to answer about how welcoming it is, as a culture, to women.

Re:Programming lesson (1)

Lazareth (1756336) | more than 3 years ago | (#34440254)

I have this nice movie you really should watch. It's called Equilibrium (or Cubic in some places). I really see the great thing with no humour (and culture) that they got going. I mean really, no wars!

Re:Programming lesson (1)

masterzora (871343) | more than 3 years ago | (#34440906)

I'm amazed by how your brain leaped from "Do we want our culture to be degrading to women?" to "We should have no culture." Is that really what that post said to you?

Re:Programming lesson (1)

notionalTenacity (1526919) | more than 3 years ago | (#34440958)

Yeah, its not a bad movie, but its kind of unsubtle.

Anyway, I was just asking the OP if they would rethink making jokes like that in the interest of a more welcoming community.

There's a difference between people having the freedom to say what they want, and thinking that all things are equally good to say.

Re:Programming lesson (3, Funny)

CharlyFoxtrot (1607527) | more than 3 years ago | (#34439308)

Don't be sexist. Chicks hate that.

Re:Programming lesson (1)

isama (1537121) | more than 3 years ago | (#34439518)

so that's why you are still around here?

Re:Programming lesson (-1)

Anonymous Coward | more than 3 years ago | (#34440316)

Oh, man, that was clever! How long did you have to sit and think to come up with that? I bet you're always the life of the party...

Re:Programming lesson (4, Funny)

seeker_1us (1203072) | more than 3 years ago | (#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:Programming lesson (3, Informative)

camperdave (969942) | more than 3 years ago | (#34438986)

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

Re:Programming lesson (2)

KiloByte (825081) | more than 3 years ago | (#34439134)

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

Machtyn (759119) | more than 3 years ago | (#34439926)

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:Programming lesson (-1)

Anonymous Coward | more than 3 years ago | (#34440114)

Same here. But instead of bots, it was penises. We would slap them at each other to determine the winner. Sometimes, you'd get a buddy to distract your opponent with a rear-end surprise. Fun times, too bad AIDS had to ruin it.

Re:Programming lesson (2)

Shikaku (1129753) | more than 3 years ago | (#34439186)

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

psithurism (1642461) | more than 3 years ago | (#34439788)

have a clear advantage if they work together properly.

Perfect, assign a different student to each ghost and have an Aesop after the simulation, about how coders are antisocial but really need to corroborate, when 3 ghosts get stuck in the same corner on the occasion they move at all, and the last just can't manage to catch pacman by itself.

Re:Programming lesson (0)

Anonymous Coward | more than 3 years ago | (#34439888)

Heh heh heh. My pacman would have a gun!

Re:Programming lesson (0)

Anonymous Coward | more than 3 years ago | (#34440174)

Indeed it was http://inst.eecs.berkeley.edu/~cs188/pacman/pacman.html

Re:Programming lesson (4, Interesting)

vux984 (928602) | more than 3 years ago | (#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.

Always fascinating. (2, Interesting)

MaWeiTao (908546) | more than 3 years ago | (#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:Always fascinating. (2)

Maxo-Texas (864189) | more than 3 years ago | (#34438962)

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. (4, Informative)

Anonymous Coward | more than 3 years ago | (#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:Always fascinating. (2)

Bozzio (183974) | more than 3 years ago | (#34440700)

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

Anonymous Coward | more than 3 years ago | (#34440748)

This is called a glitch in the Matrix.

Re:Always fascinating. (1)

rgmoore (133276) | more than 3 years ago | (#34440096)

This is mentioned in the article; it happens with Pinky because of his chase algorithm. He's designed to ambush the player by targeting the space 4 tiles ahead of Pac Man*. If Pinky and Pac Man are on a head-on collision course, that point will eventually be behind him, which will force him to turn to the side if that's an available course.

*There's actually a bug in the routine that makes him target the space 4 above and 4 to the left when Pac Man is moving up.

Re:Always fascinating. (5, Insightful)

DIplomatic (1759914) | more than 3 years ago | (#34438974)

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

cowscows (103644) | more than 3 years ago | (#34439038)

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. (1, Informative)

Anonymous Coward | more than 3 years ago | (#34439174)

Well, the behavior is complex in today's games, but the algorithms are not. The behavior trees are hand-scripted IF/THEN/ELSE for the most part. Then otherwise for the most part it's a bit of pathfinding and other simple AI techniques and the AI itself is not really that impressive.

Re:Always fascinating. (2)

Surt (22457) | more than 3 years ago | (#34439294)

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. (4, Insightful)

fishbowl (7759) | more than 3 years ago | (#34439374)

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

zippthorne (748122) | more than 3 years ago | (#34440960)

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

TheLink (130905) | more than 3 years ago | (#34439344)

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. (4, Insightful)

Monkeedude1212 (1560403) | more than 3 years ago | (#34438982)

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

Anonymous Coward | more than 3 years ago | (#34439036)

Some AI these days is just heavy scripting. Not scripting because developers are lazy, but scripting so the characters will always do exactly what they are supposed to do when they are supposed to do it.

Re:Always fascinating. (2)

Surt (22457) | more than 3 years ago | (#34439280)

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

fishbowl (7759) | more than 3 years ago | (#34439410)

I guess I could point out that we still use algorithms like A*, which was already mature and well-known at the time of the first Pac Man.

Re:Always fascinating. (1)

Surt (22457) | more than 3 years ago | (#34439728)

Yeah, but A* is just for path finding and:

compared to pac-man AI, A* is complex.
compared to A*, modern AI is complex.

So in case that was unclear:

Modern AI is vastly more complex than A* is more complex than pac-man.

Modern AI is a complex beast built on top of fundamental algorithms like A*.
 

Re:Always fascinating. (1)

fishbowl (7759) | more than 3 years ago | (#34440222)

My point was more that Modern AI has existed somewhat longer than Pac Man.

I'm not out of touch -- I do realize how much progress has been made in recent years, but it is definitely all on the shoulders of giants who managed to get us *very* far along without even having the benefit of actually using computers as we know them and take for granted. I find that quite amazing.

Re:Always fascinating. (4, Insightful)

nedlohs (1335013) | more than 3 years ago | (#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. (1)

August_zero (654282) | more than 3 years ago | (#34439918)

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 since their hosting has been crushed, but I read an article about the algorithm a couple years ago, and always found it funny that Pinky's chase code had an error in it causing him to target the wrong square when pacc-man was moving upwards (if I remember right correctly that is)

NAM-CAP (1)

El_Oscuro (1022477) | more than 3 years ago | (#34440462)

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 picks one of the directions it can turn

All of the other rules of the original PAC-MAN (player is faster when no dots, slower when eating them, faster in corners, and ghosts are slower in tunnels) were implemented. The hardest part was the random generator. 128 bit shift-register written in 8080 assembly (my dad helped a bit). By the time it was all done, my 2 ghosts were harder than the 4 in the original. They also seemed to be predictable as well. Every time one of them would hit that random turn it always seemed to be the one that hosed you completely!

Cool (-1, Redundant)

DarkKnightRadick (268025) | more than 3 years ago | (#34438908)

Interesting article. (:

(: is upside-down (0)

Anonymous Coward | more than 3 years ago | (#34439208)

(:

Does that mean you have an upside-down face like that kid on Family Guy? :)

Crush roller (2)

marcello_dl (667940) | more than 3 years ago | (#34438932)

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

Re:Crush roller (1)

BitterOak (537666) | more than 3 years ago | (#34439704)

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.

Save the best for last... (2)

Rooked_One (591287) | more than 3 years ago | (#34439086)

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.

Breaking news!!!! (5, Informative)

mrsam (12205) | more than 3 years ago | (#34439170)

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:Breaking news!!!! (0)

Anonymous Coward | more than 3 years ago | (#34439184)

mod up

Re:Breaking news!!!! (0)

Anonymous Coward | more than 3 years ago | (#34439242)

No.

Re:Breaking news!!!! (2)

assantisz (881107) | more than 3 years ago | (#34439870)

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.

Clone exercise (0)

Anonymous Coward | more than 3 years ago | (#34439194)

I was already slowly working on a clone as a programming exercise, this is a nice coincidental help.

Interesting but from my memory (4, Interesting)

al0ha (1262684) | more than 3 years ago | (#34439340)

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

Sapwatso (461933) | more than 3 years ago | (#34440422)

What you're describing sounds consistent with the article to me. The ghost behaviors are complex, but not random. They are determined by the location of Pac-Man, the location of other ghosts, the number of dots eaten, and by timers. If you run the same pattern every time, those factors will generate the same behavior each time.

If you still remember the patterns, it might be interesting to run through them again and see if you can see why they work after reading this article.

Re:Interesting but from my memory (1)

Sapwatso (461933) | more than 3 years ago | (#34440520)

Oops, I wasn't thinking about frightened mode. As others have said, presumably the PRNG generating the same series causes patterns to work there.

Re:Interesting but from my memory (5, Informative)

VortexCortex (1117377) | more than 3 years ago | (#34440460)

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

Re:Interesting but from my memory (1)

seeker_1us (1203072) | more than 3 years ago | (#34440472)

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.

The interesting part... (0)

Anonymous Coward | more than 3 years ago | (#34440652)

...is that the movements of the ghosts are completely deterministic. Expert players eventually learned to exploit this with the rote memorization of "patterns".

Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Sign up for Slashdot Newsletters
Create a Slashdot Account

Loading...