Archived

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

Simple PacMan AI

This topic is 6933 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

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

Share on other sites
I might me wrong but i read a text about the PacMan AI a while ago...

It sed that the 4 monsters had different tasks, one was to "corner" the player one to hunt him down and so on...

Share on other sites
PacMan actually had very good AI, especially for the time.

One of the ghosts randomly wandered around, but the others all had plans.

One went agressively towards you with the shortest path. Another played the interceptor and tried to go towards the next point you were moving towards, and the third ghost tried to intercept in the middle of the map and catch you moving between the tunnels.

-Geoff

Share on other sites
Hello. It looks as if I'm posting this message in a kind of dead forum but what the hell.

I'm working on a PacMan clone and everything is workin just fine. I've got two different AI's (not happy with either one).
The first one just wonders around aimlessly. The second one goes strait for the target without checking for obsticles wish makes it reaaly easy to get away from.

What I need is somesort of more intelligent "ghost" that Calculate paths and maybe works together with another "ghost".

Greatful for any input.

//m_grinder

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

1. 1
2. 2
Rutin
19
3. 3
4. 4
5. 5

• 9
• 9
• 9
• 14
• 12
• Forum Statistics

• Total Topics
633302
• Total Posts
3011272
• Who's Online (See full list)

There are no registered users currently online

×