Pacman and maze AI

I made an ascii pacman program for school. For the ghost ai, we couldn't make them too fast since they could move quicker than the play could move via the key board. So we basically set up a random number generator with 2 options, if the number was a 0 the ghost would move toward the player location either one step in the x direction or one step in the y direction. Basically if the ghost was going to move towards the player the random number is used again to determine if the ghost moves sideways or up and down, of course if the number determined sideways and that was not a valid move (maze wall) then the ghost would default to the up/down movement. Of course to implement this the ghost class needs to know the player coordinates at all times. Then the other half of the time the ghost moves in a random direction. We found that this worked well for our program, the ghosts tracked the player quickly enough to make the game challenging but not so quickly that the player couldn't get away enough to be able to win the game.

For pacman in particular I would focus on a simple directional based movment algorithm.

Represent the ghosts and pacman as a structure and record X,Y coordinates. Now you need to take the coordinates of the ghost and pacman and compare this as you would a vector to any open space that the ghost may move in to. The closest match will be chosen and the piece will move.

This is more of a hack than AI, but other more complex algorithms are fairly difficult to comprehend in some cases and unless you want to spend alot of time on that particular subsystem, 'emulating' AI may be a good choice.

In case you do want to go deeper, this is a great resource.

http://ai-depot.com/

I am having one heck of a time figuring out what I need to store, how to store it all, and how to implement it into the code I already have... this is my code.
http://ontologyband.com/Pacman2.zip

I am absolutely stumped on what to do or how to implement ideas found online. I have read a few intros and tutorials on the A* and related algorithms, but taking those ideas and stripping them down to what I need is over my head without source code examples.
Please, I need help in the worst way.. =(

For the real Pacman, each ghost actually have a unique AI.
As I remember it, one used pure random movement, one always just tried to move straight towards the player, and one tried to cut you off... Can't remember the fourth, and I'm not sure about the details of the second and third... So probably not very helpful after all ;)

This article discusses pac-man AI (it's on the 3rd page):
http://www.gamedev.net/reference/design/features/makegames/default.asp

The AI is this (this is in order of when they should pop out of the box):
Ghost #1 goes directly for the player.
Ghost #2 finds the nearest place the player would go to avoid #1.
Ghost #3 stuck to the middle in case the player tried to hit one of the side
warp thingies
Ghost #4 went off after some random destination

This is actually pretty damn good AI for being way back in the day. Makes you appreciate those ghosts more. On top of that, I don't feel so bad for losing ;)

EDIT: I don't do AI but maybe I could suggest some ideas since since pac-man does seem a little less complicated then most. For starters, I read in a thread on this forum about making a road map of a level and I would suggest making one of those. Basicly what that does is create a way point of every junction in the level and that should help greatly with the path finding.
With that road map created, which you can just hard code, you should make functions that handle path finding. You will probably need a function like this:

SetPath(destinationx, destinationy) //Finds the shortest path from the current
position of the ghost to the destination postition. This should make use of
the way points. This function should store the path in an array of way points.
Example: 0 = waypoint #2, 1 = waypoint #3; This means that the path goes to
waypoint #2 and then to waypoint #3.

This will handle the broad picture of where a ghost wants to go but now you need to make a function that will help with the next step towards that goal:

NextMove() //Decide on the next move to make. It should access the array that
has the path and then find the waypoint the ghost needs to go to next. These
waypoints should be already hard coded to x and y positions. So, because the
maze has only straight lines, you would just check to see which is different,
the x position of the ghost or the y position, compared to the waypoint. If
its the x position then you discover whether the ghost needs to move left or
right and then move them a unit in that direction. And vice versa if it's the
y position.

With that done you need to make a function that checks to see if the ghost has made it to that waypoint:

CheckPosition() //Just check the current x and y position against the targeted
way point's. If the ghost has made it then skip to the next way point on the
list.

Now, with all this done we can move on to the individual AI. Each ghost has their own very unique goals, which I have already mentioned. I will attempt to discuss each AI individually but they tend to work together, especially Ghost #1 and Ghost #2. Another thing to mention before I get started is that there is a reason these ghosts pop out in a specific order. Ghost #2 wouldn't be effective if Ghost #1 isn't there and vice versa. So, if you include the ability to eat the ghosts in your game you should remember to take this into account when a ghost is sent back to jail. You would need to discern what ghost was sent back and then fill that gap by reassigning jobs to all existing ghosts.
But, anyways, here we go with the indiviual ghost AI's:

Ghost #1:
This ghost is by far the easiest. To make his AI work just send a call to the 'SetPath' function while passing the players current x and y position. Just update this because the player is actively moving and you got 'er done.

Ghost #2:
This ghost is a little bit more difficult then Ghost #1. With this one you need to find these things: Ghost #1's current path, the player's current direction, and you need both Ghost #1's position along with the player's. With this data you need to make an educated guess on where the player is going based on the pressure Ghost #1 will be giving them. I would suggest you take the player's current position and make a path to it. Now check to see if this path crosses with Ghost #1's. If it doesn't use that. If it does then that blows because we need to do some more work. You can't have Ghost #2 and Ghost #1 follow the same path because that would defeat the purpose of Ghost #2. So, if this does happen then you should find the waypoint that they would cross at and take a slower route from there. If Ghost #1 wants to go North from a waypoint then Ghost #2 should go West or East depending on where the player is. You could make a function to handle this (I would or even recode SetPath() to accomadate this).

Ghost #3:
We are getting a little easier. This ghost is pretty much random except that he is stuck inside of just the middle of the map. I mean the horizontal middle by the way. You should use SetPath to a random waypoint that is somewhere within the middle. Then continously check to see if the player crosses the middle. If so then set the shortest path to the player. If the player escapes the middle then Ghost #3 should start patroling again.

Ghost #4:
This one is as easy as Ghost #1. You just set a random waypoint and go there. You can decide to have this ghost pursue the player if they get too close but I wouldn't. I would just have the ghost there for pressure on the player. You might even want to make sure Ghost #4 is in a part of the map that isn't being occupied by ghost or player. This would cause it to stick around the corners and might help to corner the player, accidentally. Just consider this ghost pretty much passive though.

----------------------

Again, I don't know AI. This just seemed like simple logic. So, this might just be a load of bullshit. If it is then I apologize, but I don't believe it is.

EDIT: Grammar and spelling needed to be corrected. I'm positive I didn't get it though. Damn, it is way too late at night (2:30 AM here)!

[Edited by - Think128 on December 31, 2004 4:03:45 AM]

PacMan is a true classic of game dev - twenty-five years after the fact and we STILL don't know how PacMan "thinks". Even after it's been "perfectly" completed. (thanks Billy Mitchell)

Suggest you go play the original a LOT (via MAME, for example). You'll quickly find that there are tons of subtleties that greatly affect the game:

1) NONE of the ghosts are completely random
2) NONE of the ghosts are completely "smart" (in the sense of using an elaborate optimal path-finding algorithm like A*, Djykstra, etc).
3) each ghost has its "home" in one of the quadrants of the screen. You can tell which owns which quadrant by watching them just after they emerge - that's where they go first before their real AI kicks in.
4) at timed moments throughout the game each ghost will switch between it's AI mode and a "patrol home quadrant" mode - you'll note these moments by abrupt changes in ghost direction (including 180-degree turns)
5) each ghost has a *slightly* different base speed (which varies depending on level and number of dots left in a level)
6) speed is affected by whether you're crossing dots or empty space
7) cornering speed is variable, there are faster and slower ways of turning (a tiny fraction of a second, but it does matter)
8) player is faster through tunnel than ghosts
9) ghosts can be faked out by jiggling the joystick even if you can't turn that way at present (so at least some of them apparently track the joystick movement request rather than the actual player direction)
10) ghosts switch into a distinctive "follow" mode when within range and visibility of player, though they can be shaken by repeated cornering and breaking visibility
11) then, of course, each ghost has it's own distinctive personality, here are some basic (but far from complete) observations:

"shadow" is fastest, likes to line up with player's Y before lining up in X

"speedy" also fast, when chasing and following player's direction, will then turn l/r if possible before attempting to again follow player's direction - this simple "trick" gives the illusion of advanced "cut-off" type path planning, though it's really just the limitation of the subsequent direction changes possible in the maze that accomplish this illusion.

"bashful" is slower, tends to avoid lining up with player in either X or Y, will not track player unless you get close enough to switch him into "follow" mode.

"pokey" is slowest, tends to dislike head-on confrontations and will turn to the side if possible, also does not track player, but this is only "most of the time", he will track like shadow at times

So, each ghost has (at least) four distinct states: patrol home (when enter and timed), chase (after got home, and timed, and if not see player), follow (when see player), evade (when blue).

And all of these extremely subtle timing differences are why the known successful "patterns" of play don't work for everyone. If your timing is off by just a little bit it can break the pattern. Sometimes by as little as a single slow cornering or a single dot not eaten and slowing you down later when walking over it!

I'd love to see someone disassemble the original source and comment it - for purely curiousity reasons of course. It's amazingly complex behaviour from what must be only a few simple rules.

Simple rules yielding complex patterns. I heard that in an article once...