FA+
Shop
Mathematical Personalities
10 years ago
General
A lot of code has been written to make computers behave like humans; to give them a personality and make them seem like they're really thinking. Heck, there are contests to see if people can tell the difference between a computer AI and an actual human being, getting into extremely complex programs with huge databases and parsers and decision trees. But sometimes, all you need to make a personality is some simple math and logic.
I'm talking about the ghosts in Pac Man. Contrary to what it may appear, the ghosts do not randomly move around the maze. In fact, Pac Man didn't even have a random number generator (the best it could do was use the lower four bits of consecutive memory locations to get pseudo-random numbers). Anyone who has played enough Pac Man may already be aware that Blinky (the red ghost) always seems to be on the heels of Pac Man. That's no coincidence.
First, we have to know that the screen in Pac Man is divided in to 8-by-8 pixel "tiles", each one holding part of the playfield: maze walls, curved walls, dots, power pellets... each one is an 8-by-8 tile. And an actor (Pac Man or one of the ghosts) is said to occupy a tile when the center of the actor is within that tile. The actor may be almost halfway overlapping an adjoining tile, but the official location of the character is the tile that has the center of the actor. In fact, there is no collision detection or hit-boxes in the game. When Pac Man and a ghost both occupy the same tile, they're deemed to have collided with each other. This is why you could be running for your life with a ghost overlapping Pac Man... and still be running for your life.
Second, all ghosts have a target, and they seek that target using a basic distance-measuring routine. A ghost will check the next tile ahead of it and look for the directions it can move from that tile. In a straight hallway, there is only one way to go: forward. This is because ghosts are not allowed to reverse direction except under one or two specific circumstances that arise in the game. If there is more than one direction to go, the routine checks one tile in each valid direction and compares the distance from it to the target tile. The direction with the shortest distance to the target is the direction the ghost will travel. In the case of a tie, the order of preference is up, left, down and right.
Each ghost uses a different set of rules to compute its target tile, and that's where the personalities arise.
Blinky (the red ghost) always seeks Pac Man's location. This is the simplest rule-set, but it makes Blinky aggressive and tenacious. He is always after Pac Man, chasing him down.
Pinky (the... uh... pink ghost) targets the location four tiles ahead of Pac Man. Pinky is crafty, trying to get out ahead of Pac Man and cut him off. When you combine Pinky with Blinky, the two of them become diabolical! Blinky will chase Pac Man from behind while Pinky is trying to get out in front. I'm sure the two of them have boxed in and killed many a Pac Man player.
Inky (the blue ghost) is perhaps the most interesting of the four. His target is computed by starting at Pinky's location and drawing a vector to two tiles ahead of Pac Man, then doubling the distance of that vector. The upshot of this is that when Blinky is far away from Pac Man, Inky tends to stay far away too. But as Blinky closes in on Pac Man, Inky closes the distance and joins the chase. It's almost as if he refuses to go in without help. In fact with Blinky behind Pac Man in a straight corridor, Inky is targeting the area ahead of Pac Man, just like Pinky.
Clyde (the orange ghost)... Clyde doesn't want to get too close to Pac Man. Normally his target is Pac Man's tile, like Blinky. But once Clyde gets inside a certain radius from Pac Man, his tile shifts to a point outside the maze at the bottom-left. So Clyde will keep his distance from Pac Man... except when Pac Man is in the bottom-left of the maze. If both Pac Man and Clyde are in the bottom-left of the maze, Clyde's target is the bottom-left but he's already there... so he wanders around that area, getting in Pac Man's way. This is almost worse than the other ghosts, because he's not targeting Pac Man, which makes him unpredictable.
And there you have it. How four different bits of math and logic can give distinct personalities to AI characters in an arcade game. Sometimes it's the simplest things that work out the best.
Players very familiar with Pac Man may know it's possible to play chicken with Pinky and make him "blink" and veer off course. It's a byproduct of his target algorithm. Say Pac Man and Pinky are moving toward each other with an intersection between them. Pinky arrives at the tile just before the intersection with Pac Man three tiles away. It's time for Pinky to chose the direction to go at the intersection.
Pinky's target square is four tiles ahead of Pac Man, and because Pac Man is three tiles away, this puts Pinky's target one tile behind him. Remember that ghosts can't reverse direction, so Pinky can only turn or move forward. And in comparison to the tiles on either side of the intersection, the one in the forward direction of travel is further away from the target than either of the turns. So Pinky takes the turn, getting out of Pac Man's way.
If you happen to have absolute sub-second-accurate timing (or more likely get extremely lucky) it's possible to pass through a ghost without being killed. This happens because the actors occupy the tile that the center of their sprite is in, and collisions are detected when two actors occupy the same tile.
Pac Man and Blinky approach each other and through a miracle of timing, the center of both actors is at the edge of their respective adjoining tiles at the same time. In the next 1/60th of a second update, Blinky moves forward into Pac Man's tile... and Pac Man moves forward into the tile that was occupied by Blinky. As far as the game logic is concerned, the two actors were never occupying the same tile at the same time, and Pac Man gets a free pass.
Of course if this happens when you're trying to chase down a frightened ghost, you pass through them without eating them...
I'm talking about the ghosts in Pac Man. Contrary to what it may appear, the ghosts do not randomly move around the maze. In fact, Pac Man didn't even have a random number generator (the best it could do was use the lower four bits of consecutive memory locations to get pseudo-random numbers). Anyone who has played enough Pac Man may already be aware that Blinky (the red ghost) always seems to be on the heels of Pac Man. That's no coincidence.
First, we have to know that the screen in Pac Man is divided in to 8-by-8 pixel "tiles", each one holding part of the playfield: maze walls, curved walls, dots, power pellets... each one is an 8-by-8 tile. And an actor (Pac Man or one of the ghosts) is said to occupy a tile when the center of the actor is within that tile. The actor may be almost halfway overlapping an adjoining tile, but the official location of the character is the tile that has the center of the actor. In fact, there is no collision detection or hit-boxes in the game. When Pac Man and a ghost both occupy the same tile, they're deemed to have collided with each other. This is why you could be running for your life with a ghost overlapping Pac Man... and still be running for your life.
Second, all ghosts have a target, and they seek that target using a basic distance-measuring routine. A ghost will check the next tile ahead of it and look for the directions it can move from that tile. In a straight hallway, there is only one way to go: forward. This is because ghosts are not allowed to reverse direction except under one or two specific circumstances that arise in the game. If there is more than one direction to go, the routine checks one tile in each valid direction and compares the distance from it to the target tile. The direction with the shortest distance to the target is the direction the ghost will travel. In the case of a tie, the order of preference is up, left, down and right.
Each ghost uses a different set of rules to compute its target tile, and that's where the personalities arise.
Blinky (the red ghost) always seeks Pac Man's location. This is the simplest rule-set, but it makes Blinky aggressive and tenacious. He is always after Pac Man, chasing him down.
Pinky (the... uh... pink ghost) targets the location four tiles ahead of Pac Man. Pinky is crafty, trying to get out ahead of Pac Man and cut him off. When you combine Pinky with Blinky, the two of them become diabolical! Blinky will chase Pac Man from behind while Pinky is trying to get out in front. I'm sure the two of them have boxed in and killed many a Pac Man player.
Inky (the blue ghost) is perhaps the most interesting of the four. His target is computed by starting at Pinky's location and drawing a vector to two tiles ahead of Pac Man, then doubling the distance of that vector. The upshot of this is that when Blinky is far away from Pac Man, Inky tends to stay far away too. But as Blinky closes in on Pac Man, Inky closes the distance and joins the chase. It's almost as if he refuses to go in without help. In fact with Blinky behind Pac Man in a straight corridor, Inky is targeting the area ahead of Pac Man, just like Pinky.
Clyde (the orange ghost)... Clyde doesn't want to get too close to Pac Man. Normally his target is Pac Man's tile, like Blinky. But once Clyde gets inside a certain radius from Pac Man, his tile shifts to a point outside the maze at the bottom-left. So Clyde will keep his distance from Pac Man... except when Pac Man is in the bottom-left of the maze. If both Pac Man and Clyde are in the bottom-left of the maze, Clyde's target is the bottom-left but he's already there... so he wanders around that area, getting in Pac Man's way. This is almost worse than the other ghosts, because he's not targeting Pac Man, which makes him unpredictable.
And there you have it. How four different bits of math and logic can give distinct personalities to AI characters in an arcade game. Sometimes it's the simplest things that work out the best.
Players very familiar with Pac Man may know it's possible to play chicken with Pinky and make him "blink" and veer off course. It's a byproduct of his target algorithm. Say Pac Man and Pinky are moving toward each other with an intersection between them. Pinky arrives at the tile just before the intersection with Pac Man three tiles away. It's time for Pinky to chose the direction to go at the intersection.
Pinky's target square is four tiles ahead of Pac Man, and because Pac Man is three tiles away, this puts Pinky's target one tile behind him. Remember that ghosts can't reverse direction, so Pinky can only turn or move forward. And in comparison to the tiles on either side of the intersection, the one in the forward direction of travel is further away from the target than either of the turns. So Pinky takes the turn, getting out of Pac Man's way.
If you happen to have absolute sub-second-accurate timing (or more likely get extremely lucky) it's possible to pass through a ghost without being killed. This happens because the actors occupy the tile that the center of their sprite is in, and collisions are detected when two actors occupy the same tile.
Pac Man and Blinky approach each other and through a miracle of timing, the center of both actors is at the edge of their respective adjoining tiles at the same time. In the next 1/60th of a second update, Blinky moves forward into Pac Man's tile... and Pac Man moves forward into the tile that was occupied by Blinky. As far as the game logic is concerned, the two actors were never occupying the same tile at the same time, and Pac Man gets a free pass.
Of course if this happens when you're trying to chase down a frightened ghost, you pass through them without eating them...
Xander_Opal
~xanderopal
That's pretty neat, and makes me want to read Ready Player One again.
