If I recall pacman correctly one of the AI's it used was a random wander, making decisions at corners and aimlessly moving about. This should not be too hard

For the Ghost AI what you'll need is called an A* search.

Basically this involves having a starting point, a target point and a map.

Every square on the map has a value saying how difficult it is to use that square and the value of a path is merely the value of every square on that path up to the current point.

You then start at the first square and look around you at every possible other square you can step on, a decision tree is then formed of each of these squares.

Say there are three squares you can step on from the start node. You then have a decision tree of three paths from this node, you pick the square with the lowest value and follow it until the total value of that path exceeds the total value of any other non-completed path.

When another path becomes cheaper you then switch to that path and expand it instead.

Whenever a path takes you to a node with more than one option from it (not including the path back) you build a new decision tree of all the paths from that node each with the starting value of the path up until that point.

Eventually one path will lead to the target and, as you are expanding that path, it will be the lowest cost path.

This will give you the shortest distance from starting point to target.

To make the path finding quicker, although not necessarily finding the best answer, you can weight which path you will expand by it's Manhatten distance.

The Manhatten distance is quite simple, it is the value of the easiest square to cross multiplied by the physical distance between the current point and the target point.

So if the minimum value is 10 then it would be

10 * sqrt(sqr(x2 - x1) * sqr(y2 - y1))

So if you add the Manhatten distance to any given path and then take the path with the least travelled value + Manhatten distance and expand that, then it should speed up your search significantly.

For a URL try http://www-cs-students.stanford.edu/~amitp/gameprog.html

which I found in the resources of www.gameai.com

Both good sites.

Mike