Archived

This topic is now archived and is closed to further replies.

Inmate2993

Pacman's (not ghost) AI

Recommended Posts

The Ghost AI question probably comes up too much, but I''m not here to ask about that. I want to ask if anyone has any ideas on what Pacman himself would do under AI, or rather what should an AI do to make an almost believable pacman? My thinking is that since the player can look around the map, Pacman should be chasing the pretend player''s focus, but then thats trying to code an AI that would imitate what a good player of pacman would be looking at.

Share this post


Link to post
Share on other sites
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!"

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites