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

[hedwards]

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

[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

[Locke2005]

That's the one where Ms. Pacman keeps stopping to ask for directions, right?

Re:Programming lesson

[moexu]

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

[JxcelDolghmQ]

Why don't you shut the fuck up and get back in the kitchen?

Re:Programming lesson

[isama]

so that's why you are still around here?

Re:Programming lesson

[Anonymous Coward]

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

[psithurism]

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

[notionalTenacity]

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

[sub67]

When is modern science going to find a cure for a woman's mouth?

Re:Programming lesson

[Anonymous Coward]

Heh heh heh. My pacman would have a gun!

Re:Programming lesson

[Anonymous Coward]

She was probably jealous!

Re:Programming lesson

[Machtyn]

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

Re:Programming lesson

[MechaStreisand]

What do you mean, "some"?

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

[Machtyn]

Perhaps a better site: P-Robots

Re:Programming lesson

[Anonymous Coward]

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

[notionalTenacity]

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

[notionalTenacity]

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

[Anonymous Coward]

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

[obarthelemy]

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

Re:Programming lesson

[Anonymous Coward]

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

Re:Programming lesson

[syousef]

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

http://robocode.sourceforge.net/

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

Re:Programming lesson

[Lazareth]

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

[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

[Anonymous Coward]

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

[darthdavid]

Get back to the kitchen and make me a sandwich!

Re:Programming lesson

[Anonymous Coward]

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

[dgatwood]

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

[Schadrach]

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

[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

[masterzora]

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

[notionalTenacity]

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

[notionalTenacity]

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

[Sir_Lewk]

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

[Daniel Dvorkin]

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

[jefelex]

Got that right! :-)

Re:Programming lesson

[Anonymous Coward]

Listen, if you are arguing it is equal because women can hurt your feelings, shut up, you are a loser.

Don't like it, move out. Not quite the same as a guy beating the crap out of a woman and threatening her on what will happen if she tries to leave.

Re:Programming lesson

[samoanbiscuit]

When it finds a cure for yours...

Re:Programming lesson

[samoanbiscuit]

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.

Yes anonymous coward, you're SOOO brave!! /sarcasm

Re:Programming lesson

[Anonymous Coward]

I know, but that doesn't make it suck any less on both sides of the issue. The unfortunate part is that we'll only be as welcoming as are loudest, most intolerant, and most idiotic, not our best and brightest. Look at the southern US for a great example of that.

Re:Programming lesson

[dgatwood]

Trust me. You can do far more damage to someone psychologically by not hitting them physically. Imagine this. You wake up and find your head shaved and/or your hair glued to the pillow. You step out of bed onto an emptied box of thumbtacks. When you get downstairs, you find out that your pet dog is hanging from the ceiling fan with its guts strewn on the floor. Your elementary school daughter's class schedule is missing from the front of the refrigerator, and the words "You're next" are written in the dog's blood on the kitchen floor.

You run out of the house to go pick up your daughter, but your car door locks are glued shut. And the ignition lock. And the tires are flat. You run inside to call someone for a ride, when the phone rings and you hear heavy breathing. You suddenly notice a bloody knife beside the phone that was not there when you walked out to the car.

You quickly hang up and call the police, then call someone to get a ride to work. When you go to lunch, you find out that your credit cards have been reported stolen and your bank account is now empty. And then you find out that your psycho ex has accused you of molesting your daughter, resulting in a year-long court battle. And then she hides child porn on your computer. And then you lose your job, your freedom, your child, and your sanity, all without a single direct physical act of violence against you.

Yes, this is an extreme example, but to suggest that you have to physically beat someone to cause serious injury to that person is utterly foolish.

Re:Programming lesson

[IICV]

I've actually come to realize that I have what can only be described as "color dyslexia", especially with pink and purple. I can tell the shades apart - if you put something pink and something purple in front of me, I can tell you that they're different - but when you show me a pink item and ask me what color it is, half the time I'll tell you it's purple.

It's really weird.

Re:Programming lesson

[fishexe]

You realize that your argument is logically equivalent to, "I can say anything I want about black people because many of them say racist things about white people", right? "I'm sure that there are some black people out there that genuinely consider racism to be wrong, but I don't see them because I'm too busy noticing the racist blacks and the people who only complain about black-on-white racism" is basically a direct paraphrase of what you're saying with race substituted for sex. It's like you're trying to be the Dr. Laura of sexism.

Re:Programming lesson

[fishexe]

When is modern science going to find a cure for a woman's mouth?

After it finds a cure for thinking with your dick.

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

[fishexe]

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!

Yeah, because the only type of humor is humor that demeans women. No other humorous statements are possible, or even conceivable!

Re:Programming lesson

[fishexe]

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.

How is it mincing words to refrain from insulting 50% of the world's population just for a chuckle? If you don't go around gratuitously demeaning everyone you possibly can then you're being a pussy?

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

I'll admit that that sucks, but you're basically saying that if we start respecting women's intelligence and individuality then we'll automatically end up there. I don't think that's an accurate appraisal of the situation. The biggest reason education is as f---ed up as it is (and believe me I know, my wife teaches high-school special ed) is because you're dealing with people's children, and people are really touchy about their children. Also, in public education (as opposed to private) you basically have everyone in there from every background all lumped together so that's bound to include some people who are super-sensitive about race and some who are super-sensitive about sexuality and some who are super-sensitive about religion (where I went to school it was Magic cards that were the big un-PC controversy, because some of them depicted demons). I don't think that's in any way connected to whether the FOSS community decides to be more thoughtful towards the other half, it more has to do with the nature of the educational beast.

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.

You don't think the off-color jokes are part and parcel of the boys' club status? Really? Do you know of any boys'-club-type culture without them?

Re:Programming lesson

[DewDude]

Ok...wait wait...hold on a second. Your attempt at humor makes no sense. Seriously. No sense of direction? It's a pretty known fact (or should be) that the ghosts in the original Pac-Man followed a pre-determined path. People memorized the patterns. The ghosts in Pac-Man might seem like they have some sort of behavior, but it's just pre-programmed phooey. Now, Ms Pac-Man...that's where the ghosts attempted to hone in on your position and chase you. No more memorizing patterns. The ghosts have two basic modes....attack Ms Pac and avoid Ms Pac. So, remember...original arcade Pac-Man: programmed ghosts. Ms. Pac: "chase" ghosts. Please don't make me cram Pac-Man arcade boards in to any of your orifices....they're very wide and long and I'm sure would be quite painful...plus you'd have the Z80 aux. board dangling down.

Re:Programming lesson

[uninformedLuddite]

WTF?

Re:Programming lesson

[uninformedLuddite]

and how many men were offended by this? I hazard a guess that the answer would most likely be zero. On the other hand what about if it had been a saggy breast joke?

Re:Programming lesson

[uninformedLuddite]

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

But, that is what your you will get

Re:Programming lesson

[Anonymous Coward]

You must have one hell of an ego.

Re:Programming lesson

[Anonymous Coward]

This was actually my assignment for an introductory artificial intelligence class I did. It was easily the best assignment I've ever had.

Re:Programming lesson

[Anonymous Coward]

I would argue it is the biggest factor in any function of navigation.

Re:Programming lesson

[WaroDaBeast]

Seriously now... Why the hell was this modded funny?

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

[dzfoo]

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

[Anonymous Coward]

and make me a sandwich! ... am I doing it right?

Re:Programming lesson

[BeanThere]

+1 Thank you. If I had mod points, I'd mod you up.

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

[dzfoo]

Actually, in the original Pac-Man, the ghosts did not follow a "predetermined path," but actually made decisions based on some very simple logic. This was done dynamically throughout game-play. These rules, although very simple, fall still under "artificial intelligence,' since they form the basis of decision making, and thus affected the behaviour of each ghost.

The reason that memorizing patterns helped beat the game was because, based on the same conditions, the ghosts will make the same decisions every time. The speeds and timers changed throughout the levels, but were picked from tables in ROM, guaranteeing the same values on the same level for every quarter. Even the pseudo-random number generator used to pick directions during "Frightened" mode was reset with the same seed on every level and on every life lost. This meant that the behaviour was perfectly predictable. However, you had to maintain the conditions exact, which was hard; missing a corner, or turning on a junction even one pixel too late would throw off the pattern.

Ms. Pac-Man, on the other hand, did not add much more to the game than randomness. The simple behavioural rules for the ghosts were updated, but remained simple. However, a random factor was added to almost every decision, and the pseudo-random generator was re-seeded with different values at various times. The other major addition was changing maze layouts as the game progressed.

The source code for both has been widely disassembled and studied, and the differences well documented.

So, if you consider Pac-Man as being stupid and predictable, then Ms. Pac-Man is just slightly less stupid and much less predictable. Ms. Pac-Man was an incremental update to Pac-Man; more like "Pac-Man v1.5".

      -dZ.

Re:Programming lesson

[kaizokuace]

on paper...

Re:Programming lesson

[Anonymous Coward]

I've known quite a few abusive people. My mother and stepfather abused me, emotionally and physically.

Many years ago, one of my workmates, admitted to me that she was both physically and emotionally abusive. She'd been through a divorce, and (incredibly, for my country that almost exclusively sides with the woman) lost her kids to her husband. I have the highest respect for this woman, both for admitting it, and for doing something about it.

I once got a low mark on a report card, indicative of a learning disability, so they stood me in front of them and shouted at me for an hour, then my stepfather put both hands in a wristlock while my mother smacked me around the face for a while, for my own good they told me. I've been pushed into windows and door frames, and on one occasion my mother tried to stab me with a knife because I wouldn't eat some meat that had gone off.

One of my exs spent all her time trying to manipulate me and bully me into doing whatever she wanted, whenever she wanted. Unfortunately, I didn't realise this until some years after the relationship ended. I wasn't strong enough nor did I have sufficient self-esteem, to end that relationship, even after to tried to force me to beat up one of my friends.

She was very good at doing it, too, especially at pretending to be the hurt party.

I'm a stocky guy, so she found it to be particularly easy to get other people to think I was the aggressor.

I think the best example of this is the time I told her that I liked the watch that a friend's girlfriend bought for him. She waited until everyone around had left, and started heating things up, and then as soon as she heard them coming back, she turned on the waterworks and then started cringing, and similar physical movements suggesting I had hit her. Of course, everyone sided with her.

One of my friends was attacked by a woman with a knife. The police arrested him, even though he was bleeding and needed stitches. They also charged him, and won a conviction, because the woman obviously had to act in self-defense.

Another of my friends was protecting his son, as the baby's mother was hurting him (the baby). The police arrested my friend, because no woman would ever hurt an infant.

This woman has also assaulted my friend repeatedly in the past, and all the police had done was take photos and warn my friend that next time he might be arrested. They also charged him, and won, in spite of the woman being forced to admit that her testimony was all a lie, and the officer who testified was caught fabricating his responses.

The judge said that such a serious matter as assault on a female should be punished seriously, but since it was a first offence my friend wouldn't be going to jail. This naturally confuses everyone else who is familiar with the case, as the evidence indicates that the assault was committed by the woman.

My ex, mentioned above, attacked this friend of mine with a weapon, and he absolutely did not respond except to raise his hands to protect his face. It might have got worse for him, except I dragged her off him. (I think he didn't press charges out of respect for me, which is a pity. The bitch deserved it.)

I sincerely doubt you'll find accurate information about gender-related levels of abuse.

Re:Programming lesson

[Anonymous Coward]

I suppose he doesn't want to lose his job? He did say "I work in the education field, and it's completely pathological there"

Re:Programming lesson

[Lazareth]

Yes. I can agree with some moderation and that jokes should be without malicious intent, but the whole "thou shall not offend" attitude is a slippery slope.

Re:Programming lesson

[Lazareth]

True. I can agree with moderation. But I personally prefer a humouring community to a sterile one.

Thing is, if you want something disallowed because it offends you it is a slippery slope from there to disallow jokes overall. As some of the "rougher" jokes gets pushed out, the standard for what is a "rough" joke gets lowered and with an attitude of censoring you'll soon find yourself in a community that chips away at what is allowed. Yes I'm showcasing an extreme but I'm only doing so to make a point.

Re:Programming lesson

[Lazareth]

I personally don't really prefer those kinds of jokes, unless the situation makes the juxtaposition really humourous, but my point (that you're either failing to grasp or sarcastically ignoring) is that an censoring attitude to any kind of joke that offends you is a slipperly slope to disallow any jokes regardless of subject.

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

[stefski66]

and of course, the supposedly better performances of men at 3D things has nothing to do with culture i.e. how did men/women learn to acquire this ability during childhood ?
"boy, go outside and play football" "girl, why don't you stay inside, and do some paintings instead" - this happens even in today's schools !

and of course, a statistically "significant result" (p.05) is always significant (67% vs 66,9% for example), and can be generalized to everyday activities such as parking a car. And parking a car has nothing to do with the behavior of men looking at you while you do so.

about humor vs discrimination: try replace "women"/"blond" by "jewish/black/arab", and see how your "humor" is impacting your humor-mates.

and the comparison with color-blindness is particularly bad: one knows that he is colorblind, and it's easy to detect. What you think about one woman's ability to drive a car is completely different, its "determinism", "I don't know about (this particular) her, but I generalize on suspicious beliefs, and I take for granted that she's bad at it".

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

[el3mentary]

When is modern science going to find a cure for a woman's mouth?

After it finds a cure for thinking with your dick.

We've had that for years, it's called Porn

Re:Programming lesson

[Anonymous Coward]

http://www.youtube.com/watch?v=pIrvpn3k9A4

It's been done!

Re:Programming lesson

[digitalchinky]

I think Cartman had it pretty much spot on - "You get your bitch ass back in the kitchen, and make me some pie" : )

(I would not actually say this, but it's still makes me chuckle)

Re:Programming lesson

[Macthorpe]

The problem you seem to have is that you can't distinguish attempted humour from actual sexism. There is a lot of difference between "haha women can't park" and "durhur men a jerks", and actual sexist behaviour. And before you start, I'm gay, so yes I do know what both are like.

I think this is something you need to work on rather than attempt to change everyone around you.

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

[do0b]

That would make an excellent movie!!

Re:Programming lesson

[fishexe]

I personally don't really prefer those kinds of jokes, unless the situation makes the juxtaposition really humourous, but my point (that you're either failing to grasp or sarcastically ignoring) is that an censoring attitude to any kind of joke that offends you is a slipperly slope to disallow any jokes regardless of subject.

I completely grasp and am not ignoring your point. In fact, I completely agree, and I expressed my agreement with your point elsewhere in the thread. MY point, which I won't accuse you of either failing to grasp or sarcastically ignoring because it couldn't be clear from such a short post, is that what you call "an censoring attitude to any kind of joke that offends you" is not what's going on here. You can have care and caution to what kind of atmosphere you're creating without having a "censoring attitude".

Censoring attitude: "You can't say that. It offends people."
non-Censoring attitude: "You really ought to think about what it does to people when you say that, then continue to say it only if you still think it's worth it."
See the difference? The first one leads to a death of culture. The second one leads to people not being assholes and douchebags to each other quite as often.

Re:Programming lesson

[fishexe]

The problem you seem to have is that you can't distinguish attempted humour from actual sexism.

Once again, no. If you'd actually read my post you would know this was not the case. I can distinguish perfectly well between a joke and a discriminatory belief, but the entire point I was making was that even though they are different, the one reinforces the other in most cases.

There is a lot of difference between "haha women can't park" and "durhur men a jerks", and actual sexist behaviour.

And apparently you believe "actual sexist behaviour" arises in a vacuum with no reinforcement from people in the environment saying sexist things. The two can't possibly be related, can they?

And before you start, I'm gay, so yes I do know what both are like.

I don't see how this makes you any sort of authority. I do understand how the "hey, faggot" that Dan Savage used to print at the beginning of each of the letters he answered is different from the "hey, faggot" said by a jock as he shoves another kid to the ground. Even so, people need to take account of whether the "jokes" they make create a better or worse environment for bigotry and react accordingly, and Mr. Savage ended up dropping the tongue-in-cheek "hey, faggot" greetings because he decided they weren't helping.

I think this is something you need to work on rather than attempt to change everyone around you.

So every time somebody says gays should be denied all rights, or should all be murdered, and you have a problem with it but then they claim they were just joking, how about I tell you it's something you need to work on rather than attempt to change everyone around you?

Re:Programming lesson

[fishexe]

When is modern science going to find a cure for a woman's mouth?

After it finds a cure for thinking with your dick.

We've had that for years, it's called Porn

I keep trying it, but the problem only gets worse!

Re:Programming lesson

[HBI]

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

Re:Programming lesson

[Macthorpe]

So every time somebody says gays should be denied all rights, or should all be murdered, and you have a problem with it but then they claim they were just joking, how about I tell you it's something you need to work on rather than attempt to change everyone around you?

Wouldn't that come under knowing the difference between attempted humour from actual sexism? Why is it in your world, you're the only one enlightened to the difference while everyone else is completely oblivious?

As many people have stated, you're not improving society - you're just making society less tolerant in your own way, which doesn't actually fare better in the long run than allowing people to make bad jokes.

Re:Programming lesson

[Anonymous Coward]

I read the article, and it seems what I coded in my version of pacman on an Apple II back in 1981, was Blinky.
A few kilobytes, all functional including graphics.
Man, I was young and bright back then!

Re:Programming lesson

[fishexe]

Why is it in your world, you're the only one enlightened to the difference while everyone else is completely oblivious?

You're the ONLY one in this exchange who has accused someone of not knowing the difference. I don't consider myself enlightened and haven't acted like I am. I'm just trying to have a discussion of sexism, its effects, and how to fix it. That's all.

As many people have stated, you're not improving society - you're just making society less tolerant in your own way, which doesn't actually fare better in the long run than allowing people to make bad jokes.

I am in favor of allowing people to make bad jokes. The fact that you're posing my actions as the opposite of "allowing people to make bad jokes" when "allowing people to make bad jokes" is EXACTLY WHAT I AM ADVOCATING shows that you're not really applying logic to this discussion, you're just sticking to your pre-conceived notions and rationalizing them. Which is certainly your right, but it shoots to hell any claims you make that others are making society less tolerant, especially the very people whose engagement in this thread is entirely an effort to loosen pre-conceived notions on all sides.

Re:Programming lesson

[scubamage]

I remember reading a bunch of these in my undergrad psych classes. Good citations.

Re:Programming lesson

[Macthorpe]

I've gone back and read your comments, and I have no idea how I came to the conclusion that I did.

You have my apologies.

Re:Programming lesson

[MokuMokuRyoushi]

Interestingly, that's not the first time I've heard something like that. My little brother swore for years that school buses were orange.

Re:Programming lesson

[MokuMokuRyoushi]

This probably won't mean much to you, but I just wanted to thank you for a well written comment containing a constructive argument. I really am happy to see it.

Re:Programming lesson

[thesandtiger]

It's always nice to read a sincere compliment, regardless of the venue. Thanks :)

Re:Programming lesson

[VisceralLogic]

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.

Aha! I see what you did there! ;)

Re:Programming lesson

[masterzora]

Unfortunately, my uni library doesn't seem to have a copy on hand. However, I do have access to just about every journal ever, so if you could just cite the studies that this book references, I'd love to check them out.

Re:Programming lesson

[masterzora]

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.

That's where we get into some shady areas. For one, if it's an environmental difference, but only in the American population in 2008, it doesn't even come close to proving that men are better at it (although you might get away with the statement that, currently in the United States men are better at 3D perceptualisation, so long as the rest of the conditions I listed have been filled, but that's a vastly different statement). Similarly, an environmental distance, even in a worldwide study, from 1970 would be worthless now except as a historical view.

Secondly, if it shows to be a strictly environmental distance, especially one caused because of an environment negative towards women (such as constantly saying that women are bad at driving), then the continuation of jokes of women being bad at driving and the notion that science has proven it okay would be, not only mistaken, but also setting up a self-fulfilling prophecy that I'm not really okay with.

So, yes, the difference between environment or inheritance is a big deal here, even though your first sentence is strictly correct.

Re:Programming lesson

[masterzora]

I agree with you almost entirely, but there is a wide difference between "you should at least carefully consider what you are doing" and "we should eliminate all of culture".

Re:Programming lesson

[Lazareth]

I see your distinction. I don't quite agree with it, but I see where you're coming from. The rest is shades of subjectivity. I personally think people ought to soak the stuff when it is obviously not malicious and give the benefit of doubt when it is not quite clear. Rather weather the humour instead of risking being cross about somebody being light-hearted.

Re:Programming lesson

[Anonymous Coward]

If we look at the (quite inaccurate) RGB model, we find:

Yellow = #FFFF00
Orange = #FFA500
School bus yellow = #FFD800

I.e. the school bus yellow is about midway between yellow and orange. But school buses are seldom freshly painted and squeaky clean, they dip towards darkness, which is perceived as orange.

Or, we can ditch the practical argument and instead look at the logic behind the colours.
Pink is to red like yellow is to orange, i.e. a brighter variety of the same hue.
If something is in-between red and pink in colour, we define it as a red even if it could also be called pink.
Ergo, if something is in-between orange and yellow in colour, we should define it as an orange even if it could also be called yellow.

If insisting that school buses are yellow instead of orange, one should also argue that oranges are yellow and not orange.

Re:Programming lesson

[Anonymous Coward]

I make jokes about every race, creed, religion, gender, physical deformity....anything. Nothing is taboo to me.

Yes, we've noticed that Anonymous Coward is an equal opportunity basher.

Sometimes I think that /. would have been a more open place if everybody posted as AC. But then I have my second cup of coffee and realise that if we can't play our games of favouritism and ego boosting through "karma", the board would quickly become a ghost town.

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.

Re:Programming lesson

[xe3r]

The ghosts will always win if the programmer is clever.

Re:Programming lesson

[phision]

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.

And another wise man said: "If someone can't take a joke - fuck it" (Tucker Max).
A little rude, but you can't be fun, honest and polite at the same time. I (like him) prefer tossing the politeness out.

Re:Programming lesson

[dzfoo]

A direct link to the actual Dossier page can be found here here.

        -dZ.

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.

[Anonymous Coward]

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.

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

[Anonymous Coward]

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.

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

[TheLink]

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.

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

[fishbowl]

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.

[fishbowl]

What is sophisticated is the "less is more" minimalism involved.

Re:Always fascinating.

[Surt]

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.

[BenihanaX]

Ever consider you're just playing the wrong games? Read up on Total War's AI, which learns from your tactics and modifies its own (I'm not asserting that it's the first to do so). http://images.bit-tech.net/content_images/2009/03/how-ai-in-games-works/totalwarplan2.jpg

Re:Always fascinating.

[August_zero]

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)

Re:Always fascinating.

[rgmoore]

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.

[fishbowl]

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.

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

[Anonymous Coward]

This is called a glitch in the Matrix.

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.

[Vryl]

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

Re:Always fascinating.

[jzuccaro]

What exactly happens if you shoot a ghost? it dies?

Re:Always fascinating.

[Anonymous Coward]

Like most good things in life the algorithms are actually very simple, while the maths needed to come up with them or to understand how they work aren't. But that part was handled by bearded people who couldn't care less about their applications in game design and who will never see a pence from your game "devs".

And path finding is nothing more than a crotch to make up for the fact that the AI is unable to tell it has to move to a place where .wall==0.

We don't use path-finding algorithms to move around objects. We use spatial memory and common sense, two things game AI lacks. Using path finding for a monster that is supposed to have been living there for years waiting for the hero only tells everyone your AI sucks.

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]

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

Re:Always fascinating.

[cowscows]

As long as you don't cross the streams.

Re:Always fascinating.

[drinkypoo]

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

Only if you redefine "Modern" and my preprocessor threw a flag when you tried. In terms of the total time that computer software has existed, Pac-Man is an antique, a relic.

Re:Always fascinating.

[drinkypoo]

That's not building a smart AI, that's building a successful AI. A "Smart" AI is hard to build, that's an AI that has the same amount of information you do (i.e. a series of still images and sounds) but still manages to whip your ass. An AI that seems clever is also hard to build, in that you typically need cues embedded in the level. Making the AI look clever is easy. But again, none of that is actually building a smart AI.

and their accuracy in moving, aiming, etc is limited only by the precision of floating-point data types.

This is actually the only advantage they have over humans. We do all that other stuff, including the precomputed decision trees. It's called neural pathways. Why exactly did you think that practice made you better at something?

Re:Always fascinating.

[pommiekiwifruit]

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.

[nedlohs]

"AI appears more stupid and easier to foil today" doesn't have anything to do with minimalism, and all to do with the non-stupidity of the AI.

Re:Always fascinating.

[nicky_d]

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 group will disperse, but there are grunts firing on you and lobbing grenades. Grunts are an easy kill if you can get them in your sights, but the Elite is pounding you with plasma whenever you break cover - and the jackals' otherwise laughable defensive creep is turning into a serious flanking situation.

That's on Legendary, I'm obliged by law to specify.

Crush roller

[marcello_dl]

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

Re:Crush roller

[BitterOak]

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.

Re:Crush roller

[Froggels]

In the arcade version of the game the "ghosts" were called "monsters". They were not referred as "ghosts" until the game became available for the Atari 2600. Under the Atari 2600 version of the game they were called "ghosts" because of the way they flickered on the screen.

Chase, scatter, frightened ....

[Stooshie]

... Otherwise known as snog, marry, avoid. :-)

don't click the link...

[waddgodd]

the server's slashdotted

Re:don't click the link...

[DarkKnightRadick]

I already managed to read the article. :p

Re:don't click the link...

[mhh91]

tumblr's servers are almost always down

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

[Anonymous Coward]

mod up

Re:Breaking news!!!!

[Anonymous Coward]

No.

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.

Re:Breaking news!!!!

[dzfoo]

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, but reading the explanation of the same from this new article made the algorithm more clear.

But I concede your point, other than that specific point, everything else seemed like a watered down version of The Pac-Man Dossier without the depth.

        -dZ.

Clone exercise

[Anonymous Coward]

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

(: is upside-down

[Anonymous Coward]

(:

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

Re:(: is upside-down

[DarkKnightRadick]

No, it's a left-handed emoticon. (:

Re:(: is upside-down

[Anonymous Coward]

be careful, it looks like the "your balls on my chin" sign.

Re:(: is upside-down

[Anonymous Coward]

:pood:

Two people licking balls.

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

[Sapwatso]

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

[VortexCortex]

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

[seeker_1us]

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:Interesting but from my memory

[Sapwatso]

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

[Digana]

Did you read the Pacman Dossier 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.

Re:Interesting but from my memory

[pommiekiwifruit]

The PRNG is simply reading the bottom two bits of the ROM space in a certain access pattern. So it is repeatable if you are frame-perfect. But it theoretically varies between different builds of the game (i.e. Japanese versus US).

Re:Interesting but from my memory

[al0ha]

Ah interesting, I believe you are correct. From analysis I think the problem was weak seed states which obviously allowed the use of patterns.

Re:Interesting but from my memory

[al0ha]

When I say repeat the pattern, I mean it, and the patterns include ghost behavior, as they always behave the same and you always trigger and eat them exactly the same way because they stick to the pattern as well and you know where they will go and which route to take to eat all four every time.

However I did not say that you did not have to be skilled to adapt if you blew it for even a split second at the higher levels as the ghosts are moving really quick. In fact if you could not adapt, you could not learn the pattern at the next level, so you pretty much sucked at the game. That said, and you can take this to the bank, in my day patterns are the key to achieving high scores on the original Pacman. We're talking 1981 - 82 here; not 1999.

From the TFA: "Patterns were quickly created to exploit this fact and, for any player able to get past the first 20 levels, the game now became a test of endurance to see how many points you could rack up before losing focus and making a mistake. High scores soared into the millions and most players agreed the game simply went on forever. Eventually, a few highly-skilled players were able to complete 255 consecutive levels of play (scoring over three million points and taking several hours to accomplish) and found a surprise waiting for them on level 256. It was a surprise no one knew about—not even the developers at Namco."

NAM-CAP

[El_Oscuro]

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!

Pac Men's heath magazine

[mrmeval]

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

The interesting part...

[Anonymous Coward]

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

Look at the Slashdot censorship

[fishexe]

Look at that, you make a valid point that the community would do well to heed and the mods try to censor you by modding you down so far (currently Score: -1) nobody will read what you have to say. Then somebody responds by saying, basically, "Men are only sexist because you women are mostly hypocritical bitches" and that poster gets modded up (currently Score:4, Insightful) while the one who responds by pointing out flaws and counterexamples to that "Insightful" post gets modded down and hit with another (Score:4 Insightful) response that presents no insight but more unsupported assertions.

Kinda makes you feel like the mods are compensating for something, doesn't it? Maybe you hit too close to home...

Re:Look at the Slashdot censorship

[uninformedLuddite]

Kinda makes you feel like the mods are compensating for something, doesn't it? Maybe you hit too close to home...

Is this a joke about small penises? I hope the girls aren't offended too much.

Re:Look at the Slashdot censorship

[fishexe]

Kinda makes you feel like the mods are compensating for something, doesn't it? Maybe you hit too close to home...

Is this a joke about small penises? I hope the girls aren't offended too much.

I intended to imply that they were compensating for their guilt by attacking the messenger, but I am also aware of the sexual implications and am perfectly fine if people take it that way, too. I don't think anyone already on /. will be offended, and if you think that's what this discussion is about, you probably should go back and read the original link.

Re:Look at the Slashdot censorship

[Anonymous Coward]

No, the rating of Offtopic is accurate for the GP, because this discussion is supposed to be about the algorithms used for the ghost behaviours in pac-man, not sexism at open source conferences. All of your posts and other child posts so far have fallen into that category too by the way. I hope you're happy about this derailment.

The insightful thing about Pacman...

[Anonymous Coward]

If they had named it Puckman, the idiom "Fuckman" would be in wide use, resulting in a very different world. A world without 4chan, mayhaps.

There is a fourth mode

[Enigmafan]

Ghosts returning to their den after they've been eaten by pacman, that's the fourth mode ghosts can be in,

Re:There is a fourth mode

[dzfoo]

Well, if you're counting, then there's also "Caged" mode and "Cage Exiting" mode, and there's also "Invisible" (AKA "Just Been Eaten By Pac-Man") mode.

Presumably the "three modes" mentioned by the article refer to those that affect the state of game-play.

      -dZ.

Programming lesson: early examples

[handy_vandal]

Laurentius de Voltolina meets Pac-Man

Pac-Man's Last Supper

So you have a problem with mild sexist jokes, but

[Anonymous Coward]

... are wildly enthusiastic about porn?

Really? I somehow doubt the PC police and radical feminists will be happy about your support for their causes.

Mod Parent +Insightful

[handy_vandal]

Well said.