Sign in to follow this  

Pacman: Chase Algorithm

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello, This is my first post! Hope this is in the right category, if not, sorry in advance! I coding a PacMan game clone, currently the ghosts "chase" pacman character by moving towards with more or less random directions. I looking for an Algorithm to implement a REAL chase, what is the best algorithm to make it? Dijkstra, A*, etc? I found these Algorithms List in WikiPedia: http://en.wikipedia.org/wiki/Shortest_path_problem Thanks!

Share this post


Link to post
Share on other sites
'Best' is subjective. Especially for a game as simple as pac man, if you make the AI too 'good' then the player won't stand a chance and the game will not be fun to play. My opinion would be to choose a different strategy for each ghost in order to make them appear to have different personalities. You might not even need to use any search algorithms. Often the layout of pacman levels makes a heuristic based on distance from the player good enough. The general guideline for game AI is to use the simplest strategy that looks intellegent.

For example:

Only allow ghosts to change their direction at an intersection, and don't allow them to reverse direction.

Ghost 1 could prefer a direction that will always move toward the player. If the player is above and to the right, and the options are to go left or up, choose up. If both options are equally valid, choose randomly.

Ghost 2 could patrol the border.

Ghost 3 could choose directions randomly.

Ghost 4 could patrol the equator: the middle of the board, and the escape hatches through the sides.

If any ghost is close to the player (perhaps within a city-block distance of 5) switch to Ghost 1's strategy. If the player moves out of that distance then resume original strategy.

Just my $0.02

Share this post


Link to post
Share on other sites
As mentioned, the ghosts in PacMan generally don't actually use a particularly intelligent algorithm but rather rely on the combination of a number of simple rules to give the appearance of intelligent chasing; if you do it well they can even seem like they're working together.

Typical rules you might apply to any given ghost include:
  • Stick close to the centre, attack the player if (s)he comes close.
  • Patrol the outer edge of the board, attack the player if (s)he comes close.
  • Attempt to vertically align with the player, then move closer horizontally.
  • Attempt to horizontally align with the player, then move closer vertically.
  • Move randomly (a single random ghost often keeps things mixed up nicely).


Basically have the ghosts each follow one or two rules, but switch to heading straight for the player once they get within a certain distance.

Also already mentioned, a lot of implementations only allow the ghosts to change direction if they're at an intersection, which can help to give the player a chance.

Many implementations also give each ghost a "home quadrant" - you might notice in versions that include this that the ghosts will each initially head to a specific corner of the board before starting to follow thier other rules, and may even return to thier "home corner" if the player gets far enough away from them - this generally ensures that there will be a ghost in each corner of the grid unless the player intentionally leads them away.


A* or Dijkstra would both work perfectly fine if you want to practice using them though, so if you're interested then give it a try! You can always change things later if your chosen solution doesn't turn out fun to play or is too smart or stupid. Pretty much any pathfinding will work out for you, but you'll find that you don't need anything particularly complex for a good PacMan AI.

One other thing you may want to keep in mind is that you might not always want to calculate the shortest path to the player; you can often get good results by attempting to guess where the player is going and trying to cut them off, especially if another ghost is chasing them.

Share this post


Link to post
Share on other sites
Dijkstra's algorithm is probably your best bet if you want the game to be absolutely impossible. The graph is fairly small, so A* shouldn't be necessary. However, if you're looking for a more realistic clone, the AI is well documented.

The original Pacman had very specific AI. The each of four ghosts each had their own job:

Orange: 'Pokey' - Wanders around at random; is the slowest.
Pink: 'Speedy' - Also wanders at random, but is the fastest.
Cyan: 'Bashful' - Avoids Pacman at first, but retaliates if attacked.
Red: 'Shadow' - Chases the player at all times.

Also, when given two equal choices of where to go, Speedy and Pokey (also Bashful and Shadow) will turn in opposite directions to one-another, increasing the chance of boxing Pacman in.

Regards
Admiral

Edit: Take a look here for a discussion.

Share this post


Link to post
Share on other sites
What I did for my chaser was:
Only change direction at an intersection.
To decide which way to go, loop through each of the possible squares it can go to (1st square in each direction), then calculate the straight-line distance from that square to pac-man. Then go in the direction that produces the shortest distance.

Very simple and effective method.

Degra

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by TheAdmiral
The original Pacman had very specific AI. The each of four ghosts each had their own job:

Orange: 'Pokey' - Wanders around at random; is the slowest.
Pink: 'Speedy' - Also wanders at random, but is the fastest.
Cyan: 'Bashful' - Avoids Pacman at first, but retaliates if attacked.
Red: 'Shadow' - Chases the player at all times.

I find Wikipedia more trustworthy, and it disagrees:
Quote:
Blinky increases greatly in speed once a certain number of dots are eaten. The higher the level, the sooner this happens. ... (Apart from Blinky, the ghost speeds are equal and constant.)
Where blinky=shadow=red.

Also:
Quote:
The movements of the ghosts are strictly deterministic—there is no random or even pseudo-randomness in the algorithms choosing their paths.


http://en.wikipedia.org/wiki/Pac-Man

Share this post


Link to post
Share on other sites
I think you're taking TheAdmiral too literally. By 'random' he presumably means there is no obvious relation to Pacman's position and the directions chosen by the ghosts. If I recall correctly, they move in a pattern which you can learn, but which could appear effectively random.

Share this post


Link to post
Share on other sites
I believe the system used in the original arcade version was based on the game storing what the player last did at each junction in the maze and then the ghosts would check that and use it or not on a random value that was set according to the current level of the game.

Share this post


Link to post
Share on other sites
When I came to an interview at DTI soft in montreal, they told me about the algo (just for my general culture) and they said :

The pacman algo is A*

- One of the ghost takes the shortest way
- One of the ghost takes the longest
- The other is just random


Maybe they are wrong, but it sounds perfect to me.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by Daivuk
When I came to an interview at DTI soft in montreal, they told me about the algo (just for my general culture) and they said :

The pacman algo is A*

- One of the ghost takes the shortest way
- One of the ghost takes the longest
- The other is just random


Maybe they are wrong, but it sounds perfect to me.
They were wrong. There's no reason why A* or dijkstra would've been implemented in a game made in 1980. Computer resources were scarce, programming was hard (full asm most likely) and moreover, the game wouldn't be any better with A* ghosts (I can imagine it being worse). Plus, A* doesn't give you the longest way. What even is the longest way when you can just loop in a circle forever in some corner?

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this