Jump to content

  • Log In with Google      Sign In   
  • Create Account

Simple PacMan AI


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
3 replies to this topic

#1 grinder   Members   -  Reputation: 122

Like
Likes
Like

Posted 21 November 1999 - 01:35 PM

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

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


Sponsor:

#2 MikeD   Members   -  Reputation: 158

Like
Likes
Like

Posted 02 November 1999 - 11:43 PM

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


#3 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

Likes

Posted 21 November 1999 - 07:24 AM

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...


#4 ghowland   Members   -  Reputation: 134

Like
Likes
Like

Posted 21 November 1999 - 01:35 PM

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





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS