sjf,

There's a great document about Ms. Pac-Man HERE and in it the author describes the "AI" of the original ghosts. I'll briefly summerize here.

Red: Always tries to shorten either the horizontal or vertical distance between him-self and Ms. Pac-Man, whichever is longer. This rule applies regardless of the maze configuration. - So basically, the ghost always checks whether x or y is greater between himself and the player, and attempts to go that direction.

Pink: When pink is far away from the player she behaves the same as red. When the player is stationary (not moving) or when Pinky is close she does whatever she can to get in front of the player. If she ever becomes directly in front of the player, ie. face-to-face, she'll turn off at the next intersection.

Green: When green is close to red, he takes on the behavior of red. When Green is far away, his own behavior patterns kick in. He prefers to hit from the flank and as such is often seen running "along side" of the player. Also, given the choice between a sharp turn, and turning wide, Green will select wide.

Brown: Brown is the most predictable as he follows a predetermined path depending on what the player does. The author does not provide details as to what the predetermined path is.

So in essence, the ghosts constantly keep track of where they are on a 2d grid (x,y). Depending on the distance from the player or from other ghosts, or depending on the direction the player is currently heading, they will choose to go in different directions when given the opportunity to turn.

Hats off to the original Pacman devs - the AI looks clever and runs on a shoestring budget.
However, tweaking such heuristics until you have good behavior is not what I'd recommend nowadays. You can afford to have the ghosts look at the entire map, search for the shortest path to the player, etc.
When we wrote Pacman for a VR system at Uni, we had to predict the player's movement to compress it into a small 6x6m holodeck. This opened all sorts of interesting possibilities: the ghosts could actually head off the player and surround him. The implementation was something similar to a Markov chain, taking into account position of the other ghosts and pills remaining to be collected.

Quote:Jan Wassenberg, could you go into more detail?

Glad to - just successfully demo-ed the current project, so I have breathing room :)
On what front? The original Pacman AI, our Uni project in general, the holodeck+motion compression, ghost AI, the prediction scheme, ..?

Quote:I hope I get to tackle a project like you've explained.

Indeed :D We were rather lucky, looks like; came across it by chance.

I had wrote a pacman clone last year (called bACMAN, look it up on libsdl.org), and I found that the AI wasn't too complex to do, though my code had gotten very unmanagable, given at how lazy I was.

Anyways, I came to these conclusions.

When travelling down a hallway, the ghosts can't change direction, no AI needed.
When aligning with a mapcell, count the number of exits.
o 1 exit: hit a deadend, go back the way we came.
o 2 exits: take the exit we didn't come from.
o 3 exits or 4 exits, appy AI.

And then, based one which ghost it was, we did this.

o Jimbo (red): Head in the one that goes toward the player.
o Cletus (green): Randomly either toward the player, or a random direction.
o Eileen (purple): Pick one at random.
o Steve (orange): Bahave like Jimbo if too far from bacman, otherwise run from bacman.

The steve element was fun, because you'd think he's going to kill you, and then he starts running. I even made his sprite look worried when this happens. Jimbo and Cletus work together well, and Eileen wasn't always seemed to be blocking right where you needed to go to get away from the others.

Of course, there are a few other things in the AI to note, such as the returning to the Ghosthole, and everyone returning to their favorite corner at the start of the board, or after every Powerpellet mode.