Analysing Pacman's Path Finding

Pacman has four ghosts which can be in three different states; chase, scatter, and frightened. Each mode behaves differently to create a more diversified game and increase the depth requiring more tactical thought from the player. Each mode in Pacman requires different path-finding techniques or alterations.

The chase mode is the default path-finding technique used for ghosts in the game. Similar to A* path-finding, all modes use the position of Pacman to ensure they are traveling towards the player. The ghost however does not calculate a path through the means of A* but uses heuristics similar to this. Since the mazed is fixed and never changes, the ghost will choose a direction until met at a decision path (i.e. when they have the option to make a turn or carry on in the same direction). When the decision path is met, the ghost will calculate the heuristics of the tile and decide whether or not that it is closer to Pacman. If the tile is closer the path should be taken. This effect can result in “odd” AI but is more forgiving to the player as it trades immediate vs long-term distance calculation. The AI is more likely to end up traveling useless paths thus making the game more forgiving to the player. They cannot reverse their direction when a decision is made either.

There is an exception to the direction traveling; when the ghosts’ mode changes from chase to any other mode. This is where the ghosts’ aim is to travel away from the player (as they are considered a threat). The direction of travel is forced to be reversed and when making a decision the best path away from the player is made.

Each ghost also inhibits their own behaviour type, when initially released from the cage the ghost is set to scatter mode and their target is set to a particular ‘home’ (their home being an area of the maze). The movement rules still apply in this mode, but will eventually reach their home with these rules. After a set time, their modes are forced to change and move into the chase to try to end the game.

There are only very few tactics employed to create co-operation between ghosts, one being the ghost known as ‘Pinky’. Rather than following the player’s current path, it takes the 4 possible paths in front of the player’s current position and chooses that as the target location. The intention of this is to create a ghost that tries to position itself in front whilst another ghost follows the player in order to trap Pacman. This inadvertently creates the tactic known as ‘chicken’. If the player is 3 tiles in front of Pinky, who has to decide to turn before they meet then Pinky will create a new path behind itself and divert away from the player. It is particularly interesting that this effect created more depth to the game. Inky, the blue ghost, takes into consideration the players’ position and orientation as well as the other ghost known as ‘Blinky’. Lastly, the orange ghost known as ‘Clyde’ switches his mode between chase and scatter based on how far away his position is from Pacman. This can result in odd behaviour, where he is just ‘doing his own thing’. Although it adds more strategy to the game, as it ensures that another route cannot be taken when close to Pacman.

The take from Pacman is immediate vs long-term benefit of path-finding. The techniques in Pacman’s path finding are almost entirely based on instant results rather than trying to find the shortest possible path. At the time, this was important as it reduced the number of resources used whilst also increasing the depth of the game. These techniques would likely create odd results in a random maze and are based on a fixed result enabling these techniques to be successful. Particular parts of this algorithm would have to be adapted in order to ensure that the AI is ‘always on track’. With a large maze, it is unlikely that the ghosts would get close to the player based on immediate effect decision making; resulting in a boring and stale game. The techniques however can be applied with A* path-finding in order to create more co-operation between the enemies to add depth - such as looking ahead of the player’s directional path and surrounding area.