Pacman's (not ghost) AI

One way of approaching it on the large scale would be to use a pair of influence maps (or combine them into one). One map would be where the bulk of remaining dots are, the other would be where the ghosts are. This gives you an overall "sense" of where you want to be combined with where you DON''T want to be.

Then, on a fine scale using a combination pathfinding/planning algorithm using the intersections as nodes. The question that the algorithm would answer is "can I make it to the next intersection before a ghost". If the answer is yes, then start thinking ahead to where you could go from that intersection. If the answer is no, then see if you even need to go down that path at all (dots there?).

Since the board is actually grid based (with each dot being a space) you could actually run a planning algorithm that incorporates the speed of the ghosts on a grid basis. Use your own speed as the frame rate... that is, every frame is based on how long it takes me to travel from one dot to the next. Then, you can project the ghosts positions forward based on their rates of travel. e.g. It will take me 4 frames to get to that intersection 4 dots away... where will they all be in 4 frames?

If you were to run a planning itteration for every frame into the future, you could get a good fix (100% certainty) on ghost positions that are on straight segments (no intersections). If a ghost encounters an intersection during a planning frame, do a descending value for certainty radiating out from the intersection. i.e. the first dots away are 100%, the next dots are 80%, the next 40%, etc. That means that you will be avoiding areas that are even NEAR the intersections a ghost is heading toward.

You would only really need to look at 2 intersections deep... that is, here to the next intersection and then the segement following that. Beyond that level, you don''t know where the ghosts are going to be anyway so it''s pointless to look further.

Using the influence map method for the dots, you can wander around in the safe areas and will tend to move towards large concentrations of dots. However, you will always be "looking ahead" to see if the ghosts are going to cut you off. If so, you will be choosing a path that gets you out of their way.

The other issue is the "clean-up" phase. That would likely need to be more fine-tuned than the influence map attracting you to the dots. You could have a new state that is based on a certain number of remaining dots. When the dots get below that level, go into a new mode that is more of a specific pathfinding mode. It wants to get to a goal, but it still has to avoid the ghosts using the formula above.

Dave Mark - President and Lead Designer
Intrinsic Algorithm - "Reducing the world to mathematical equations!"

Bump.

Well, thats certainly an interesting algorithm to consider, though it seems a bit complex. If I remember correctly, Pacman was slighty faster than the ghosts (at least until Red started to speed up), and could change direction mid-tunnel. Given that, pacman could risk a path even if ghosts would catch up to him.

So, anyone else have any ideas?