Passing through the ghosts in Pac-Man
This article is a fragment of my book “Bug Voyage: A Tour of Classic Game Glitches”. The book also contains information on generating pseudo-random numbers, performing low-level computations with binary and decimal numbers, as well as how to cause a crash in any Galaga machine gun, even without dropping a coin there.
If there is an arcade machine Pac-Man, Ms. near you. Pac-man or something like that, then you are lucky, today they are in short supply. Even the 20 Year Reunion automatons that were very common in the past, in which Ms are installed together. Pac-Man and Galaga, now there are not so often.
But to understand what will be discussed, it is enough to download a video from YouTube about one of these games and watch it in just one minute:
')
You noticed. How do Pac-Man and ghosts move smoothly through the maze? They slide so confidently and clearly.
This smoothness, as we shall see, is an illusion, and that’s not all. Here is another YouTube video:
It is uploaded by Jamey Pittman, the author of the Pac-Man Dossier article, which has become the source of much of the information about Pac-Man for my book. The video is slightly rewound to save you time. Watch it. In particular, keep an eye on Pac-Man and the red ghost (the manual says that his name is Blinky). Notice what happens around the fortieth second!
Have you seen? Pac-Man passed through the red ghost without any problems! How did this happen? Is it possible to ensure that this happens all the time?
Calm down, I'll explain everything now, and yes, this is constant behavior. If you accurately follow Pittman’s instructions on level one, it will always happen.
Pac-man
Part of the two-dimensional graphics equipment used in the games special graphics, which are called sprites. Perhaps you have heard this term in modern conversations about the pixel graphics characters.
But before, the meaning of the term was different: they were used to designate an independently moving graphic object, which could be placed anywhere on the screen, or on top of the rest of the graphic, called the background, or under it. Sprite are given X and Y coordinates, an image and its color. Often they were used for game characters, but also used as additions to the background and for other purposes.
Most systems supported multiple or (in the case of Galaga) multiple sprites. They had other names: Atari first called them "Player-Missile Graphics" (Player-Missile Graphics), and in early Commodore documentation they were referred to as "Movable Object Blocks" (MOB). However, gradually, almost everyone began to call them sprites.
Equipment arcade Pac-Man supports sprite graphics. It can display on the screen up to eight sprites at the same time, and that is without using tricks with sweep strings. One of the sprites is the image of Pac-Man himself, plus four more are used by ghosts. When Pac-Man eats the ghost, his eyes returning home use the ghost sprite.
Not everything that changes on the screen is a sprite. Another type of graphics used by the equipment of that time is tile background . It was just a grid of individual graphic elements stored in memory. When changing the contents of a section of memory, a small part of the screen corresponding to this part of the grid also changes immediately. Therefore, it is easy to work with these grids.
Dots in Pac-Man are background tiles (tiles) that are erased when Pac-Man eats them. The flickering of "Energizers" (Energizer), which give Pac-Man strength, is performed by staining these cells black and then white every few frames. But these objects do not move, they can only be removed or replaced.
The problem with characters' tile graphics is that it cannot move smoothly. It is located on the grid, so a moving background object will not be able to move around the screen smoothly, as Pac-Man and ghosts do. It can only move between grid cells. It is impossible to move a part of the grid space, it is either there or not.
Well, yes, it is interesting. But so what?
In my childhood I wrote small games on Microsoft BASIC for my Commodore 64. This implementation of BASIC had problems. The programs were executed slowly and almost did not use the computer’s sound and graphic resources that were amazing for their time. If you wanted to do something with graphics and sound, you had to learn the cryptic technical commands of direct memory access, called POKE, or learn to write in machine code.
One way out was to use character objects instead of the sprite graphics system, as I described above. Objects made jumps the size of a tile, but it was much easier to work with them. It was possible to start creating a game using character graphics, and then, when the project was already big and serious, and he wanted to show people to switch to using hardware sprites.
An object in memory could still jump in the same increment of eight pixels, but the player could not see it. All he saw was a shimmering sprite image that could have been larger than the character tile and hid what was actually happening. Approaching programming wisely, one could interpolate the position of the sprite, so that its movement seemed smoother. If you did well enough, the player never noticed the difference. The truth would know only you.
I guess you already guessed what I'm driving. Because that's exactly how the Pac-Man game was programmed .
In fact, both Pac-Man and ghosts had two positions each. This is the position of the sprite graphics, smoothly moving around the screen, which the player sees. Such information is given to the player when he plays the game, but this is just a shadow, an illusion. If you want to figure out how Pac-Man actually works, then you need to look deeper.
"Behind the scenes" of the game, Pac-Man also takes into account which character cells are occupied by Pac-Man and ghosts. There are no traces of these coordinates on the screen. I suspect that in the early stages of the development of Pac-Man, when experiments on the gameplay were conducted, the developers could draw the tiles directly on the screen. Jamie Pittman discovered that these coordinates are used for the artificial intelligence of all ghosts, and they are also used to recognize all collisions in the game.
To maintain this illusion, the game has to go to the tricks. It tracks how far Pac-Man and ghosts have moved from their current cell at a subscription level, and switches them to a new position when they have moved far enough away. A slightly faster object will have a speed that forces cells to change a little more often.
These elements - grid coordinates, tracking between cells and the position of the sprite on the screen - create the illusion of smooth movement. But from the point of view of the game, the movement is performed in the same way as in my case when I programmed the cell graphics of characters on the Commodore 64.
Now we have all the information necessary to understand how Pac-Man can pass through ghosts.
Pac-Man collisions are recognized by comparing its grid coordinates with ghost coordinates. If they are the same, then a collision occurs and one eats the other. If they are different, there is no collision. That's all, no more, no less.
You can see that the reason for this decision is the speed of collision recognition in processor cycles. Each frame he compares the X and Y numbers of Pac-Man to the numbers of each of the four ghosts. Because of this, he does not need to worry about distances and risky situations. Collisions are exact matches of coordinates in the grid system.
This grid (approximately) corresponds to the coordinate system of tiles, representing the true positions of the game characters. Collision detection uses this mesh. The game registers a collision only when the coordinates of the tiles of both characters coincide. This means that they must occupy a single grid cell.
The problem occurs when the positions of Pac-Man and the ghost moving towards each other are switched to the next cell in the same frame. Collision checking is performed after all objects have moved in the current frame. If Pac-Man moves to the Blinky cell, and Blinky moves to the previous Pac-Man cell in the same frame, then an error is detected during collision detection. They swapped places!
Since this is the only level of reality that really means something in the game, it’s not important what the player sees. Pac-Man and the ghost simply pass through, “the ships diverge like at sea”.
Artificial intelligence (AI) in the game has a deterministic nature, so you can identify a pattern for repeating behavior. Despite the fact that the time for the manifestation of an error with the passage through must be accurate to the frame, the player does not necessarily have to be accurate to the frame if he follows the rules for the execution of the Pac-Man movement patterns. This is how Jamie Pittman’s video was recorded.
I gave such a detailed description to emphasize an important fact. It is very easy to perceive the objects in the game as real. Pac-Man is such an object on the screen, ghosts are also objects, like a spaceship, Mario, Sonic, Solid Snake, a soldier from Call of Duty. They are all objects. But this is an illusion.
In fact, they all just give you a hint of an inner, deeper system. In this system, the computer has to do serious work simply to determine that the two objects touch each other . What you see on the screen is an illustration of an abstract world, and a part of the game transfers information from this world to the player through the screen in a manner appropriate to his sense of reality.
It is very easy to forget how thin this connection is. How do you know which object on the screen you control? He is different from others and responds to management. But what if the screen appears exactly the same? Or will your object sometimes move randomly, react to control signals with a delay, sometimes turn into an invisible one, divide into two, become like one of the enemies?
The task of the designer is to make the connection between the inner world of the game and what you see on the screen as simple and direct as possible (of course, if he does not try to achieve some special effect). This is what the word immersion means, or should mean.
Insert a coin into the “20 Year Reunion” arcade machine and enter the first player's joystick: up, up, up, down, down, down, left, right, left, right, left. If the ghost on the Game Select screen turns pink and you hear a sound, then everything is done correctly. Now, if you choose the game Ms. Pac-Man, then instead of it you will play the original Pac-Man.
On some graphics hardware, you can use trick strings with sweep lines to create strong magic. For example, in a system that can display only eight sprites, you can achieve a greater amount, although at the cost of CPU time and reduced flexibility.
In this respect, the Atari VCS / 2600 console is the most noteworthy, because most of the system graphics there was created using sweep strings. Read more about these techniques in the book Racing The Beam .
Sources:
Pac-Man dossier: http://www.gamasutra.com/view/feature/3938/the_pacman_dossier.php?print=1
Jamie Pittman YouTube channel: https://www.youtube.com/user/jameypittman/videos
If there is an arcade machine Pac-Man, Ms. near you. Pac-man or something like that, then you are lucky, today they are in short supply. Even the 20 Year Reunion automatons that were very common in the past, in which Ms are installed together. Pac-Man and Galaga, now there are not so often.
But to understand what will be discussed, it is enough to download a video from YouTube about one of these games and watch it in just one minute:
')
You noticed. How do Pac-Man and ghosts move smoothly through the maze? They slide so confidently and clearly.
This smoothness, as we shall see, is an illusion, and that’s not all. Here is another YouTube video:
It is uploaded by Jamey Pittman, the author of the Pac-Man Dossier article, which has become the source of much of the information about Pac-Man for my book. The video is slightly rewound to save you time. Watch it. In particular, keep an eye on Pac-Man and the red ghost (the manual says that his name is Blinky). Notice what happens around the fortieth second!
Have you seen? Pac-Man passed through the red ghost without any problems! How did this happen? Is it possible to ensure that this happens all the time?
Calm down, I'll explain everything now, and yes, this is constant behavior. If you accurately follow Pittman’s instructions on level one, it will always happen.
Pac-man
What is a sprite?
Part of the two-dimensional graphics equipment used in the games special graphics, which are called sprites. Perhaps you have heard this term in modern conversations about the pixel graphics characters.
But before, the meaning of the term was different: they were used to designate an independently moving graphic object, which could be placed anywhere on the screen, or on top of the rest of the graphic, called the background, or under it. Sprite are given X and Y coordinates, an image and its color. Often they were used for game characters, but also used as additions to the background and for other purposes.
Most systems supported multiple or (in the case of Galaga) multiple sprites. They had other names: Atari first called them "Player-Missile Graphics" (Player-Missile Graphics), and in early Commodore documentation they were referred to as "Movable Object Blocks" (MOB). However, gradually, almost everyone began to call them sprites.
Equipment arcade Pac-Man supports sprite graphics. It can display on the screen up to eight sprites at the same time, and that is without using tricks with sweep strings. One of the sprites is the image of Pac-Man himself, plus four more are used by ghosts. When Pac-Man eats the ghost, his eyes returning home use the ghost sprite.
Not everything that changes on the screen is a sprite. Another type of graphics used by the equipment of that time is tile background . It was just a grid of individual graphic elements stored in memory. When changing the contents of a section of memory, a small part of the screen corresponding to this part of the grid also changes immediately. Therefore, it is easy to work with these grids.
Dots in Pac-Man are background tiles (tiles) that are erased when Pac-Man eats them. The flickering of "Energizers" (Energizer), which give Pac-Man strength, is performed by staining these cells black and then white every few frames. But these objects do not move, they can only be removed or replaced.
The problem with characters' tile graphics is that it cannot move smoothly. It is located on the grid, so a moving background object will not be able to move around the screen smoothly, as Pac-Man and ghosts do. It can only move between grid cells. It is impossible to move a part of the grid space, it is either there or not.
Well, yes, it is interesting. But so what?
Basics of the world Pac-Man
In my childhood I wrote small games on Microsoft BASIC for my Commodore 64. This implementation of BASIC had problems. The programs were executed slowly and almost did not use the computer’s sound and graphic resources that were amazing for their time. If you wanted to do something with graphics and sound, you had to learn the cryptic technical commands of direct memory access, called POKE, or learn to write in machine code.
One way out was to use character objects instead of the sprite graphics system, as I described above. Objects made jumps the size of a tile, but it was much easier to work with them. It was possible to start creating a game using character graphics, and then, when the project was already big and serious, and he wanted to show people to switch to using hardware sprites.
An object in memory could still jump in the same increment of eight pixels, but the player could not see it. All he saw was a shimmering sprite image that could have been larger than the character tile and hid what was actually happening. Approaching programming wisely, one could interpolate the position of the sprite, so that its movement seemed smoother. If you did well enough, the player never noticed the difference. The truth would know only you.
I guess you already guessed what I'm driving. Because that's exactly how the Pac-Man game was programmed .
In fact, both Pac-Man and ghosts had two positions each. This is the position of the sprite graphics, smoothly moving around the screen, which the player sees. Such information is given to the player when he plays the game, but this is just a shadow, an illusion. If you want to figure out how Pac-Man actually works, then you need to look deeper.
"Behind the scenes" of the game, Pac-Man also takes into account which character cells are occupied by Pac-Man and ghosts. There are no traces of these coordinates on the screen. I suspect that in the early stages of the development of Pac-Man, when experiments on the gameplay were conducted, the developers could draw the tiles directly on the screen. Jamie Pittman discovered that these coordinates are used for the artificial intelligence of all ghosts, and they are also used to recognize all collisions in the game.
To maintain this illusion, the game has to go to the tricks. It tracks how far Pac-Man and ghosts have moved from their current cell at a subscription level, and switches them to a new position when they have moved far enough away. A slightly faster object will have a speed that forces cells to change a little more often.
These elements - grid coordinates, tracking between cells and the position of the sprite on the screen - create the illusion of smooth movement. But from the point of view of the game, the movement is performed in the same way as in my case when I programmed the cell graphics of characters on the Commodore 64.
Pay
Now we have all the information necessary to understand how Pac-Man can pass through ghosts.
Pac-Man collisions are recognized by comparing its grid coordinates with ghost coordinates. If they are the same, then a collision occurs and one eats the other. If they are different, there is no collision. That's all, no more, no less.
You can see that the reason for this decision is the speed of collision recognition in processor cycles. Each frame he compares the X and Y numbers of Pac-Man to the numbers of each of the four ghosts. Because of this, he does not need to worry about distances and risky situations. Collisions are exact matches of coordinates in the grid system.
This grid (approximately) corresponds to the coordinate system of tiles, representing the true positions of the game characters. Collision detection uses this mesh. The game registers a collision only when the coordinates of the tiles of both characters coincide. This means that they must occupy a single grid cell.
The problem occurs when the positions of Pac-Man and the ghost moving towards each other are switched to the next cell in the same frame. Collision checking is performed after all objects have moved in the current frame. If Pac-Man moves to the Blinky cell, and Blinky moves to the previous Pac-Man cell in the same frame, then an error is detected during collision detection. They swapped places!
Since this is the only level of reality that really means something in the game, it’s not important what the player sees. Pac-Man and the ghost simply pass through, “the ships diverge like at sea”.
Artificial intelligence (AI) in the game has a deterministic nature, so you can identify a pattern for repeating behavior. Despite the fact that the time for the manifestation of an error with the passage through must be accurate to the frame, the player does not necessarily have to be accurate to the frame if he follows the rules for the execution of the Pac-Man movement patterns. This is how Jamie Pittman’s video was recorded.
I gave such a detailed description to emphasize an important fact. It is very easy to perceive the objects in the game as real. Pac-Man is such an object on the screen, ghosts are also objects, like a spaceship, Mario, Sonic, Solid Snake, a soldier from Call of Duty. They are all objects. But this is an illusion.
In fact, they all just give you a hint of an inner, deeper system. In this system, the computer has to do serious work simply to determine that the two objects touch each other . What you see on the screen is an illustration of an abstract world, and a part of the game transfers information from this world to the player through the screen in a manner appropriate to his sense of reality.
It is very easy to forget how thin this connection is. How do you know which object on the screen you control? He is different from others and responds to management. But what if the screen appears exactly the same? Or will your object sometimes move randomly, react to control signals with a delay, sometimes turn into an invisible one, divide into two, become like one of the enemies?
The task of the designer is to make the connection between the inner world of the game and what you see on the screen as simple and direct as possible (of course, if he does not try to achieve some special effect). This is what the word immersion means, or should mean.
Additional Information
Insert a coin into the “20 Year Reunion” arcade machine and enter the first player's joystick: up, up, up, down, down, down, left, right, left, right, left. If the ghost on the Game Select screen turns pink and you hear a sound, then everything is done correctly. Now, if you choose the game Ms. Pac-Man, then instead of it you will play the original Pac-Man.
On some graphics hardware, you can use trick strings with sweep lines to create strong magic. For example, in a system that can display only eight sprites, you can achieve a greater amount, although at the cost of CPU time and reduced flexibility.
In this respect, the Atari VCS / 2600 console is the most noteworthy, because most of the system graphics there was created using sweep strings. Read more about these techniques in the book Racing The Beam .
Sources:
Pac-Man dossier: http://www.gamasutra.com/view/feature/3938/the_pacman_dossier.php?print=1
Jamie Pittman YouTube channel: https://www.youtube.com/user/jameypittman/videos
Source: https://habr.com/ru/post/403115/
All Articles