# Pacman: Chase Algorithm

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

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

Edit: Take a look here for a discussion.

##### 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 on other sites
Quote:
 Original post by TheAdmiralThe 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.)

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 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 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 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 on other sites
Thanks for the replies guys!

I found this forum as a great resource for Game beginner Developers :)

1. 1
2. 2
3. 3
Rutin
22
4. 4
JoeJ
17
5. 5

• 14
• 30
• 13
• 11
• 11
• ### Forum Statistics

• Total Topics
631774
• Total Posts
3002297
×