Algorithm of ghost behavior in the game Pac-Man
I tried to make a translation of yesterday's topic-links to Habré. I apologize in advance if the wording may seem crooked to you, I will gladly accept constructive criticism. Go…
It seems to me right to start this blog with a topic that inspired me in the first place. Not so long ago, I came across an article by Jamey Pittman " Pac-Man Dossier ", which contained a very detailed description of the mechanics of the game Pac-Man. It seemed to me very interesting, so this site is an attempt to collect the same detailed information about the other games. But in tribute, I still start with Pac-Man, and in particular, with a description of the algorithm of ghost behavior. This is a very interesting topic and, I hope, my explanation will be a little more understandable and accessible than Jamie’s, because I will focus only on behavior.
About the game:
')
Pac-Man is one of the iconic video games of all time, most people (not even gamers) are at least familiar with it. The goal of the game is very simple - the player is in a maze filled with “food” (depicted as dots), and he needs to eat them all to pass to the next level. The task is complicated by four ghosts haunting Pacmene. If he meets with one of the ghosts, he loses his life and returns to the beginning, as well as the points he ate. In addition to simply escaping from ghosts, the only protection for Paekmen is the four granules-energizers located in the corners of the maze. If you eat one, ghosts begin to fear and retreat for a short time, and at early levels Packmen can eat one of them to get bonus points. The eaten ghost does not remove it completely, but returns to its initial position in order to restart the pursuit. In addition to eating points and ghosts, there is another opportunity to get bonus points - fruits, which appear at each level closer to the middle of the maze. The first fruit appears when Packman ate 70 points in the maze, the second when 170.
Each Pac-Man level uses the same labyrinth with 240 points (food) and 4 energyizers. Tunnels leading from the left and right edges of the screen can be used by pacmen and ghosts as transitions to the opposite side of the screen, although the speed of ghosts during the passage of the tunnel is significantly reduced. Although the labyrinth is the same all the time, the levels are getting harder because of the changing speed of Packman himself and the acceleration of the ghosts. After 21 levels no changes are made to the game, therefore all other levels are identical in complexity.
Each of the ghosts is individual, each uses its own algorithm to determine the route. Understanding the behavior of each ghost is very important in order to effectively avoid them. However, before proceeding to the description of the individual characteristics, first we will look at aspects of behavior that they have in common.
When the game begins, Packman is not immediately attacked by all four ghosts. As shown in the initial position diagram of the game, only one ghost begins to pursue him while the others sit in a small room in the center of the maze, often called the "ghost house." At a difficulty level other than “beginner”, ghosts will return to it after being eaten by pacmen (after adopting an energizer), so they will be there if pacmen dies. In all other cases, the ghost house is inaccessible to both the player and the ghosts themselves. Ghosts, leaving the house, always begin to move to the left, except for the cases that will be separately described below.
The conditions that determine when the three remaining ghosts leave their home are actually quite complex. Therefore, I will leave their description outside of this article, the more they are no longer relevant after the first few levels. If you are still interested, then Pac-Man Dossier, mentioned at the beginning of the article, covers them .
Most of the mechanics of Pac-Man is based on the fact that the labyrinth is divided into cells. The “cell” in this context is a square of 8x8 pixels on the screen. The screen resolution of the original game was 224x288, which gives us a total size of 28x36 cells, although most of them are not available for ghosts and pekmen. As an example: it is believed that the ghost devoured Pacmene when he occupied the same cell as he. In addition, each point in the labyrinth is located in the center of its own cell. It should be noted that the sprites of ghosts and pakmena more than one cell, so they are never only on one. Because of this, in a game, a character is considered to occupy a given cell if his sprite occupies its center. This is important for effectively escaping ghosts, because Packman will only be caught if the ghost manages to transfer his center point to the same cell as Packman.
The key to understanding the ghost algorithm is the concept of a “target cell”. The vast majority of the time each ghost has a cell that he is trying to reach, and his behavior is precisely to get from his position to the target cell. Each ghost uses the same algorithm to move to the target cell, but their individuality is that the target cells of each of them are different. Please note that there are no restrictions, that the target cell should be available for moving there (even more often it is just not available), many aspects of ghost behavior are a direct result of this feature. The cells will still be affected further, but for now just keep in mind that ghosts are almost always motivated trying to reach their target cell.
Ghosts are always in one of three possible modes: Chase, Scatter, or Frightened. The pursuit mode is considered “normal”; it is in this mode that the ghosts of most of the game are in trying to catch Packman, using his position as a factor in the choice of his target cell. In the scatter mode, each ghost has its fixed target cell, located in close proximity to the corners of the maze. This leads to the fact that in this mode the ghosts scatter to the corners. The mode of fright is unique in that ghosts do not have a target cell during movement. Instead, they pseudo-randomly decide where to go at each intersection. In the fright mode, the ghost becomes dark blue, moves much slower and can be eaten by pacmene. However, the duration of this mode gradually decreases with increasing level and disappears completely at level 19.
Changes from the pursuit mode to the run mode occur at a fixed timer, which causes the “waves” described by Iwatani. This timer is reset at the beginning of each level or after the death of Pacman. It also pauses when the ghosts are in the startle mode, what happens when a packman eats an energy gun. After that, the ghosts again return to their previous mode and the timer resumes. The ghosts begin in the scatter mode and there are four waves of chasing / scattering, after which the ghosts will remain in the pursuit mode indefinitely (until the timer is reset). For the first level, the duration of these waves:
1. Run for 7 seconds, chase 20 seconds.
2. Run for 7 seconds, chase 20 seconds.
3. Run for 5 seconds, chase 20 seconds.
4. Disperse for 5 seconds, then a constant chase.
The duration of these phases varies somewhat when the player moves to the second level, and then again at the fifth. Starting from the second level, the third wave of pursuit increases significantly to 1033 seconds (17 minutes 13 seconds), and in the next mode, the runaway lasts only 1/60 second, after which the ghosts go into a permanent pursuit mode. After the fifth level, the changes are based on an additional reduction of the first two “runs” to 5 seconds and the addition of an extra 4 seconds to the third wave of prosecution, which lengthens it to 1037 seconds. As for the 1/60-second scatter mode at each level, except the first, it seems that such a small time can not affect the gameplay, but the reason for this will be further justified.
The next step is to understand exactly how ghosts are trying to reach their target cell. AI ghosts are very simple and short-sighted, which makes it even more impressive. Ghosts think only one step into the future when they move in a maze. Whenever a ghost steps on a cage, he looks forward to the next one and looks where he turns when he reaches it. These decisions have one very important limitation: ghosts can never change the direction of motion to the opposite. That is, the ghost cannot enter the cage on the left side, and then decide to start moving in the circumferential direction and exit on the left. The meaning of this restriction is that when a ghost enters a cell with only two exits, he cannot choose the one from where he came from, and will always go in the same direction.
However, there is one exception to this rule: when ghosts change the mode from stalking or scattering to any other, they are obliged to change their direction as soon as they switch to the next cell. This obligation cancels any decision on the previous direction of movement. This acts as an effective notification to the player that the ghosts have changed their mode, since this is the only time that this behavior is possible. Notice that when they leave the startle mode, they do not change direction. So, the 1/60-second mode at each level after the first forces all ghosts to reconsider their direction of movement, even if their goal remains there. By the way, the same behavior is specially prescribed for ghosts in the "house", so a ghost that did not leave the house during the first mode switch will come out of it in the opposite direction. This makes them move to the left as usual, and then immediately change direction and go to the right.
The diagram above shows a simplified version of the maze. Cells that require a decision are marked in green.
When it is necessary to make a decision, the ghost chooses an adjacent cage, which will put it closer in a straight line to the target. The distance from the possible cell of the movement to the target is measured and chooses the one that is closer. In the diagram below, the ghost will turn up at the intersection, if two cells are at the same distance from the target, then it is selected by priorities: upper> left> lower. With this method of choice, the decision to go to the right can never be made, since any other option will definitely be better.
Since the distance is chosen in a straight line to the target, it is possible that the ghost will choose the wrong turn when the distance in a straight line is less, but the distance through the maze may be greater. An example is shown below, where measuring in a straight line gives an exit to the left, however this is not the best choice. This will give us 28 cells to reach the goal, but the path to the right would take only 8.
The last particular case is the cells marked yellow in the diagram. Specifically, these intersections have additional limitations: ghosts cannot choose an upward path from these cells. Having entered them on the right or on the left, the ghost can only go further (except in cases of forced rotation when changing modes). But this restriction does not work in the mode of fright, because in it the ghosts behave randomly at every turn. Also, if the ghost came in from above when switching modes, it can go up. So this restriction only works with “normal” movement, with no exceptions. So if Packman runs away from the ghosts near these cells, he can win his head start by running up, because the ghosts will be forced to take a longer way around.
As mentioned earlier, the only differences between ghosts are their method of selecting target cells in pursuit and scatter mode. First, let's see how the ghosts behave in the scatter mode, as this is very simple, and then we will look at their approach to movement in the pursuit mode.
In this mode, each ghost has a predetermined target cell, located beyond the boundaries of the maze near the corners. When this mode begins, each ghost turns its head toward the target angle and starts moving according to the usual pathfinding algorithm. However, since their goals are inaccessible, and ghosts cannot stop or turn around, they begin to try to reach their goal, turning and returning to it again. As a result, the path of each ghost eventually turns into a loop near its corner. If you remain in scatter mode, they will spin on it endlessly. In practice, the scatter mode is so short that the ghosts do not even have time to reach their corners or make a full turn around their loop. The diagram below shows the target cells of each character and the loops they would describe.
The red ghost begins outside the house of ghosts and, as a rule, its first one should be regarded as a threat, as it paves the shortest path to peckman almost instantly. His name is Blinky and the game describes his personality as a “shadow”. In Japanese, it is described as oikake, which translates as "pursuer" or "hunter." The description in both languages is accurate, as the Blinky target cell in the pursuit mode is determined by the current packman cell. This means that Blinky almost always directly pursues Pacman, until, because of short-sighted decision-making, he chooses an inefficient path.
Although the Blinky target selection method is very simple, it has one feature that other ghosts do not have — in two specific coordinates at each level (depending on the remaining points), its speed increases by 5% and the behavior in the scatter mode changes. The duration of the speed change varies with the level and occurs earlier and earlier with an increase in player progress.
Changes in the scatter mode are probably more significant than the speed change, since they cause the target Blinky cell to always be Packman's position, even in scatter mode, instead of a fixed cell in the upper right corner. This actually keeps the Blinky in pursuit mode all the time, although he will have to turn around when the regime changes. In this extended state, Blinky is generally referred to as “Cruise Elroy,” although the origin of this term seems to be unknown. Even the great omnipotent guide "Pac-Man Dossier" does not give us the answer. If Pacman dies when Blinky is in Cruise Elroy mode, he temporarily returns to normal behavior until other ghosts have left the ghost house.
The pink ghost begins at the ghost house, but always leaves it immediately, even on the first level. The ego is the name Pinky and his personality is described as speedy. This is a significant difference from the Japanese description of the individual - machibuse, which translates as "lying in wait." The Japanese version is more true, since Pinky does not move faster than other ghosts (even slower than Blinky in Cruise Elroy mode), and the target search system tries to move him to where he goes, not where he is now. The Pinky target cell is determined according to the current position and direction of the peckman and selects the position four cells in front of it. At least it was a design and it worked when peckman was heading left, down or right. But when Pakman was heading up, due to an overflow error in the code, Pinky’s target cell was mounted on four cells in front of Pakman and four to the left of it. I don’t want to frighten people who are not familiar with programming, but if you are interested in the technical details of this bug, Don Hodges wrote a wonderful explanation ( Link to Google’s cache , as the server is sometimes loaded), containing the original code to search for Pinky’s goal and corrected version.
One of the important consequences of the method of choosing the goal of Pinky is that packman could often win him in the " chicken " game (on Wikipedia an example from Hollywood is given when two drivers go to the ram and one of them turns at the last moment. - approx. Transl.) .
Since the target cell is placed four cells in front of the peckman, if the peckman goes to it and they are located behind it in less than 4 cells from each other, Pinki’s target cell. This leads Pinky to go around to get to her goal. Therefore, it was an overall strategy for instantly confusing Pinky if he was getting too close. This often sent him in a completely different direction. (the picture below is clear. - approx. transl.)
A ghost named Inca stays in the house for a short time on the first level and does not give chase until Packmen has eaten at least 30 points. In English, it is described as “shy”, “timid” (bashful), in Japanese “kimagure” - whimsical, whimsical. It is difficult to predict the behavior of the Inca, because it is the only ghost that uses in his pursuit not only the position of Pekmen. The Inca uses the position and direction of both Pacman and Blinky (the red ghost). The Inca's targeting method is like this: he chooses a cell two squares in front of a peckmen (almost like Pinky), then imagine a vector from Blinky to this point and double it. The end of the vector will be the target Inca cell.
Thus, the Inca goal can be anywhere, until the Blinky is not close to Packman, but if Blinky has managed to get close, the Inca will do the same. Notice that his calculation of “two cells before Packman” suffers with exactly the same overflow error as Pinky, so that if Packman moves up, the end of the vector from Blinky (before doubling) will actually be two tiles to the left of Packmen.
The orange ghost, "Clyde", is the last ghost remaining in the house the longest, and not going out until at least one third of the points have been eaten. In English, his personality is described as “jailer” (o_O - commentary transl.) (Pokey), while from Japanese it is otoboke - “to pretend that you are ignoring.” As usual, the Japanese version is more accurate, the Clyde targeting method gives the impression that it is simply “doing its job” that is not related to Packman at all. The unique Clyde targeting feature is two modes that switch based on its distance from the packman. Every time Clyde needs to calculate his target cell, he first calculates the distance to Pacman. If it is more than 8 cells, then it acts as a Blinky, that is, its goal is Pacman himself. However, as soon as its distance to pacmen becomes less than eight cells, its target cell is installed in the same place where it would be in a running mode, not far from the lower left corner of the maze.
The combination of these two methods gives the fact that Clyde constantly changes direction, either towards Packman, or in another direction. In the diagram above, the crosses mark the places where mode switching occurs. So if Packman somehow manages to stay in his place, Clyde will be spinning endlessly on this loop. As long as the player is not in the lower left corner of the maze, there is a guarantee that Clyde can be avoided if you do not block the path of his retreat into his own corner. As long as Pacman is eight squares from the bottom left corner, the Clyde loop will have the same shape that it would have had in scatter mode.
If you have read to here, you should now have a fairly complete idea of the logic of the movement of ghosts in Pac-Man. Understanding their behavior is probably the most important step in becoming a good Pac-Man player. I have never been good at Pac-Man, but while I was researching this article and testing some things, I found that I was able to avoid ghosts much easier than before. Even a little knowledge helps a lot in the game, for example, understanding that in the scatter mode you have a couple of seconds when the ghosts are not trying to kill you consciously.
Pac-Man is an amazing example of seemingly complex behavior, resulting from several cleverly designed rules that make a very interesting gameplay, forcing players to play it even 30 years after the release.
The Pac-Man Dossier, Jamey Pittman - almost the only source that is useful to you for your own research. Honestly, most of this article is a rehash of The Pac-Man Dossier. I strongly recommend reading it if you liked this article.
Pac-Man's Ghost Behavior Analyzed and Fixed, Don Hodges - an explanation of the bug in the behavior of Pinky and Inca.
Pac-Man Museum
It seems to me right to start this blog with a topic that inspired me in the first place. Not so long ago, I came across an article by Jamey Pittman " Pac-Man Dossier ", which contained a very detailed description of the mechanics of the game Pac-Man. It seemed to me very interesting, so this site is an attempt to collect the same detailed information about the other games. But in tribute, I still start with Pac-Man, and in particular, with a description of the algorithm of ghost behavior. This is a very interesting topic and, I hope, my explanation will be a little more understandable and accessible than Jamie’s, because I will focus only on behavior.
About the game:
“At that time, all available games were very violent - games about war and space invaders. There was not a single game for everyone at once, and especially, which the girls would have liked. I wanted to come up with a “comic” game that even girls could enjoy. ”
- Toru Iwatani, creator of Pac-Man
')
Pac-Man is one of the iconic video games of all time, most people (not even gamers) are at least familiar with it. The goal of the game is very simple - the player is in a maze filled with “food” (depicted as dots), and he needs to eat them all to pass to the next level. The task is complicated by four ghosts haunting Pacmene. If he meets with one of the ghosts, he loses his life and returns to the beginning, as well as the points he ate. In addition to simply escaping from ghosts, the only protection for Paekmen is the four granules-energizers located in the corners of the maze. If you eat one, ghosts begin to fear and retreat for a short time, and at early levels Packmen can eat one of them to get bonus points. The eaten ghost does not remove it completely, but returns to its initial position in order to restart the pursuit. In addition to eating points and ghosts, there is another opportunity to get bonus points - fruits, which appear at each level closer to the middle of the maze. The first fruit appears when Packman ate 70 points in the maze, the second when 170.
Each Pac-Man level uses the same labyrinth with 240 points (food) and 4 energyizers. Tunnels leading from the left and right edges of the screen can be used by pacmen and ghosts as transitions to the opposite side of the screen, although the speed of ghosts during the passage of the tunnel is significantly reduced. Although the labyrinth is the same all the time, the levels are getting harder because of the changing speed of Packman himself and the acceleration of the ghosts. After 21 levels no changes are made to the game, therefore all other levels are identical in complexity.
Common elements of the behavior of all ghosts
“Well, the game about food is not such a great entertainment, so we decided to breathe in a bit of excitement and tension and added enemies. The player had to fight with them in order to get food. Each of the enemies has its own character. Enemies are four small monsters in the shape of resembling ghosts, each with its own color — blue, orange, pink, and red. I used four different colors mainly to attract girls to the game, I thought they would like different colors. ”
- Toru Iwatani, creator of Pac-Man
Each of the ghosts is individual, each uses its own algorithm to determine the route. Understanding the behavior of each ghost is very important in order to effectively avoid them. However, before proceeding to the description of the individual characteristics, first we will look at aspects of behavior that they have in common.
Ghost House
When the game begins, Packman is not immediately attacked by all four ghosts. As shown in the initial position diagram of the game, only one ghost begins to pursue him while the others sit in a small room in the center of the maze, often called the "ghost house." At a difficulty level other than “beginner”, ghosts will return to it after being eaten by pacmen (after adopting an energizer), so they will be there if pacmen dies. In all other cases, the ghost house is inaccessible to both the player and the ghosts themselves. Ghosts, leaving the house, always begin to move to the left, except for the cases that will be separately described below.
The conditions that determine when the three remaining ghosts leave their home are actually quite complex. Therefore, I will leave their description outside of this article, the more they are no longer relevant after the first few levels. If you are still interested, then Pac-Man Dossier, mentioned at the beginning of the article, covers them .
Target cells
Most of the mechanics of Pac-Man is based on the fact that the labyrinth is divided into cells. The “cell” in this context is a square of 8x8 pixels on the screen. The screen resolution of the original game was 224x288, which gives us a total size of 28x36 cells, although most of them are not available for ghosts and pekmen. As an example: it is believed that the ghost devoured Pacmene when he occupied the same cell as he. In addition, each point in the labyrinth is located in the center of its own cell. It should be noted that the sprites of ghosts and pakmena more than one cell, so they are never only on one. Because of this, in a game, a character is considered to occupy a given cell if his sprite occupies its center. This is important for effectively escaping ghosts, because Packman will only be caught if the ghost manages to transfer his center point to the same cell as Packman.
The key to understanding the ghost algorithm is the concept of a “target cell”. The vast majority of the time each ghost has a cell that he is trying to reach, and his behavior is precisely to get from his position to the target cell. Each ghost uses the same algorithm to move to the target cell, but their individuality is that the target cells of each of them are different. Please note that there are no restrictions, that the target cell should be available for moving there (even more often it is just not available), many aspects of ghost behavior are a direct result of this feature. The cells will still be affected further, but for now just keep in mind that ghosts are almost always motivated trying to reach their target cell.
Ghost Movement Modes
Ghosts are always in one of three possible modes: Chase, Scatter, or Frightened. The pursuit mode is considered “normal”; it is in this mode that the ghosts of most of the game are in trying to catch Packman, using his position as a factor in the choice of his target cell. In the scatter mode, each ghost has its fixed target cell, located in close proximity to the corners of the maze. This leads to the fact that in this mode the ghosts scatter to the corners. The mode of fright is unique in that ghosts do not have a target cell during movement. Instead, they pseudo-randomly decide where to go at each intersection. In the fright mode, the ghost becomes dark blue, moves much slower and can be eaten by pacmene. However, the duration of this mode gradually decreases with increasing level and disappears completely at level 19.
“To bring some tension into the game, I wanted the monsters to surround Pac-Man at a certain stage of the game. But I felt that it would create stress for the player if he were constantly surrounded by ghosts. Therefore, I had the monsters surround him in waves: first attack, then retreat. When they regrouped, the attack began again. It seemed to me more natural than a constant attack. ”
- Toru Iwatani, creator of Pac-Man
Changes from the pursuit mode to the run mode occur at a fixed timer, which causes the “waves” described by Iwatani. This timer is reset at the beginning of each level or after the death of Pacman. It also pauses when the ghosts are in the startle mode, what happens when a packman eats an energy gun. After that, the ghosts again return to their previous mode and the timer resumes. The ghosts begin in the scatter mode and there are four waves of chasing / scattering, after which the ghosts will remain in the pursuit mode indefinitely (until the timer is reset). For the first level, the duration of these waves:
1. Run for 7 seconds, chase 20 seconds.
2. Run for 7 seconds, chase 20 seconds.
3. Run for 5 seconds, chase 20 seconds.
4. Disperse for 5 seconds, then a constant chase.
The duration of these phases varies somewhat when the player moves to the second level, and then again at the fifth. Starting from the second level, the third wave of pursuit increases significantly to 1033 seconds (17 minutes 13 seconds), and in the next mode, the runaway lasts only 1/60 second, after which the ghosts go into a permanent pursuit mode. After the fifth level, the changes are based on an additional reduction of the first two “runs” to 5 seconds and the addition of an extra 4 seconds to the third wave of prosecution, which lengthens it to 1037 seconds. As for the 1/60-second scatter mode at each level, except the first, it seems that such a small time can not affect the gameplay, but the reason for this will be further justified.
Basic rules for ghost behavior
The next step is to understand exactly how ghosts are trying to reach their target cell. AI ghosts are very simple and short-sighted, which makes it even more impressive. Ghosts think only one step into the future when they move in a maze. Whenever a ghost steps on a cage, he looks forward to the next one and looks where he turns when he reaches it. These decisions have one very important limitation: ghosts can never change the direction of motion to the opposite. That is, the ghost cannot enter the cage on the left side, and then decide to start moving in the circumferential direction and exit on the left. The meaning of this restriction is that when a ghost enters a cell with only two exits, he cannot choose the one from where he came from, and will always go in the same direction.
However, there is one exception to this rule: when ghosts change the mode from stalking or scattering to any other, they are obliged to change their direction as soon as they switch to the next cell. This obligation cancels any decision on the previous direction of movement. This acts as an effective notification to the player that the ghosts have changed their mode, since this is the only time that this behavior is possible. Notice that when they leave the startle mode, they do not change direction. So, the 1/60-second mode at each level after the first forces all ghosts to reconsider their direction of movement, even if their goal remains there. By the way, the same behavior is specially prescribed for ghosts in the "house", so a ghost that did not leave the house during the first mode switch will come out of it in the opposite direction. This makes them move to the left as usual, and then immediately change direction and go to the right.
The diagram above shows a simplified version of the maze. Cells that require a decision are marked in green.
When it is necessary to make a decision, the ghost chooses an adjacent cage, which will put it closer in a straight line to the target. The distance from the possible cell of the movement to the target is measured and chooses the one that is closer. In the diagram below, the ghost will turn up at the intersection, if two cells are at the same distance from the target, then it is selected by priorities: upper> left> lower. With this method of choice, the decision to go to the right can never be made, since any other option will definitely be better.
Since the distance is chosen in a straight line to the target, it is possible that the ghost will choose the wrong turn when the distance in a straight line is less, but the distance through the maze may be greater. An example is shown below, where measuring in a straight line gives an exit to the left, however this is not the best choice. This will give us 28 cells to reach the goal, but the path to the right would take only 8.
The last particular case is the cells marked yellow in the diagram. Specifically, these intersections have additional limitations: ghosts cannot choose an upward path from these cells. Having entered them on the right or on the left, the ghost can only go further (except in cases of forced rotation when changing modes). But this restriction does not work in the mode of fright, because in it the ghosts behave randomly at every turn. Also, if the ghost came in from above when switching modes, it can go up. So this restriction only works with “normal” movement, with no exceptions. So if Packman runs away from the ghosts near these cells, he can win his head start by running up, because the ghosts will be forced to take a longer way around.
Individual aspects of behavior
“This is the heart of the game. I wanted every enemy to have its own specific character of his own movements, so they do not pursue Pekmen on the same path, it would be tiring and not interesting. ”
- Toru Iwatani, creator of Pac-Man
As mentioned earlier, the only differences between ghosts are their method of selecting target cells in pursuit and scatter mode. First, let's see how the ghosts behave in the scatter mode, as this is very simple, and then we will look at their approach to movement in the pursuit mode.
Scatter mode
In this mode, each ghost has a predetermined target cell, located beyond the boundaries of the maze near the corners. When this mode begins, each ghost turns its head toward the target angle and starts moving according to the usual pathfinding algorithm. However, since their goals are inaccessible, and ghosts cannot stop or turn around, they begin to try to reach their goal, turning and returning to it again. As a result, the path of each ghost eventually turns into a loop near its corner. If you remain in scatter mode, they will spin on it endlessly. In practice, the scatter mode is so short that the ghosts do not even have time to reach their corners or make a full turn around their loop. The diagram below shows the target cells of each character and the loops they would describe.
Red ghost
The red ghost begins outside the house of ghosts and, as a rule, its first one should be regarded as a threat, as it paves the shortest path to peckman almost instantly. His name is Blinky and the game describes his personality as a “shadow”. In Japanese, it is described as oikake, which translates as "pursuer" or "hunter." The description in both languages is accurate, as the Blinky target cell in the pursuit mode is determined by the current packman cell. This means that Blinky almost always directly pursues Pacman, until, because of short-sighted decision-making, he chooses an inefficient path.
Although the Blinky target selection method is very simple, it has one feature that other ghosts do not have — in two specific coordinates at each level (depending on the remaining points), its speed increases by 5% and the behavior in the scatter mode changes. The duration of the speed change varies with the level and occurs earlier and earlier with an increase in player progress.
Changes in the scatter mode are probably more significant than the speed change, since they cause the target Blinky cell to always be Packman's position, even in scatter mode, instead of a fixed cell in the upper right corner. This actually keeps the Blinky in pursuit mode all the time, although he will have to turn around when the regime changes. In this extended state, Blinky is generally referred to as “Cruise Elroy,” although the origin of this term seems to be unknown. Even the great omnipotent guide "Pac-Man Dossier" does not give us the answer. If Pacman dies when Blinky is in Cruise Elroy mode, he temporarily returns to normal behavior until other ghosts have left the ghost house.
Pink ghost
The pink ghost begins at the ghost house, but always leaves it immediately, even on the first level. The ego is the name Pinky and his personality is described as speedy. This is a significant difference from the Japanese description of the individual - machibuse, which translates as "lying in wait." The Japanese version is more true, since Pinky does not move faster than other ghosts (even slower than Blinky in Cruise Elroy mode), and the target search system tries to move him to where he goes, not where he is now. The Pinky target cell is determined according to the current position and direction of the peckman and selects the position four cells in front of it. At least it was a design and it worked when peckman was heading left, down or right. But when Pakman was heading up, due to an overflow error in the code, Pinky’s target cell was mounted on four cells in front of Pakman and four to the left of it. I don’t want to frighten people who are not familiar with programming, but if you are interested in the technical details of this bug, Don Hodges wrote a wonderful explanation ( Link to Google’s cache , as the server is sometimes loaded), containing the original code to search for Pinky’s goal and corrected version.
One of the important consequences of the method of choosing the goal of Pinky is that packman could often win him in the " chicken " game (on Wikipedia an example from Hollywood is given when two drivers go to the ram and one of them turns at the last moment. - approx. Transl.) .
Since the target cell is placed four cells in front of the peckman, if the peckman goes to it and they are located behind it in less than 4 cells from each other, Pinki’s target cell. This leads Pinky to go around to get to her goal. Therefore, it was an overall strategy for instantly confusing Pinky if he was getting too close. This often sent him in a completely different direction. (the picture below is clear. - approx. transl.)
Blue ghost
A ghost named Inca stays in the house for a short time on the first level and does not give chase until Packmen has eaten at least 30 points. In English, it is described as “shy”, “timid” (bashful), in Japanese “kimagure” - whimsical, whimsical. It is difficult to predict the behavior of the Inca, because it is the only ghost that uses in his pursuit not only the position of Pekmen. The Inca uses the position and direction of both Pacman and Blinky (the red ghost). The Inca's targeting method is like this: he chooses a cell two squares in front of a peckmen (almost like Pinky), then imagine a vector from Blinky to this point and double it. The end of the vector will be the target Inca cell.
Thus, the Inca goal can be anywhere, until the Blinky is not close to Packman, but if Blinky has managed to get close, the Inca will do the same. Notice that his calculation of “two cells before Packman” suffers with exactly the same overflow error as Pinky, so that if Packman moves up, the end of the vector from Blinky (before doubling) will actually be two tiles to the left of Packmen.
Orange ghost
The orange ghost, "Clyde", is the last ghost remaining in the house the longest, and not going out until at least one third of the points have been eaten. In English, his personality is described as “jailer” (o_O - commentary transl.) (Pokey), while from Japanese it is otoboke - “to pretend that you are ignoring.” As usual, the Japanese version is more accurate, the Clyde targeting method gives the impression that it is simply “doing its job” that is not related to Packman at all. The unique Clyde targeting feature is two modes that switch based on its distance from the packman. Every time Clyde needs to calculate his target cell, he first calculates the distance to Pacman. If it is more than 8 cells, then it acts as a Blinky, that is, its goal is Pacman himself. However, as soon as its distance to pacmen becomes less than eight cells, its target cell is installed in the same place where it would be in a running mode, not far from the lower left corner of the maze.
The combination of these two methods gives the fact that Clyde constantly changes direction, either towards Packman, or in another direction. In the diagram above, the crosses mark the places where mode switching occurs. So if Packman somehow manages to stay in his place, Clyde will be spinning endlessly on this loop. As long as the player is not in the lower left corner of the maze, there is a guarantee that Clyde can be avoided if you do not block the path of his retreat into his own corner. As long as Pacman is eight squares from the bottom left corner, the Clyde loop will have the same shape that it would have had in scatter mode.
Conclusion
If you have read to here, you should now have a fairly complete idea of the logic of the movement of ghosts in Pac-Man. Understanding their behavior is probably the most important step in becoming a good Pac-Man player. I have never been good at Pac-Man, but while I was researching this article and testing some things, I found that I was able to avoid ghosts much easier than before. Even a little knowledge helps a lot in the game, for example, understanding that in the scatter mode you have a couple of seconds when the ghosts are not trying to kill you consciously.
Pac-Man is an amazing example of seemingly complex behavior, resulting from several cleverly designed rules that make a very interesting gameplay, forcing players to play it even 30 years after the release.
Sources
The Pac-Man Dossier, Jamey Pittman - almost the only source that is useful to you for your own research. Honestly, most of this article is a rehash of The Pac-Man Dossier. I strongly recommend reading it if you liked this article.
Pac-Man's Ghost Behavior Analyzed and Fixed, Don Hodges - an explanation of the bug in the behavior of Pinky and Inca.
Pac-Man Museum
Source: https://habr.com/ru/post/109406/
All Articles