How Pac Man's ghosts decide what to do: elegant complexity

How Pac Man's ghosts decide what to do: elegant complexity: "Game Internals's description of the way that the Pac Man ghosts use incredibly simple rules to emerge complex, difficult-to-defeat anti-Pac Mac strategies is a great reminder of the power of recursion and iteration to produce complexity out of the simplest starting points.

The next step is understanding exactly how the ghosts attempt to reach their target tiles. The ghosts' AI is very simple and short-sighted, which makes the complex behavior of the ghosts even more impressive. Ghosts only ever plan one step into the future as they move about the maze. Whenever a ghost enters a new tile, it looks ahead to the next tile that it will reach, and makes a decision about which direction it will turn when it gets there. These decisions have one very important restriction, which is that ghosts may never choose to reverse their direction of travel. That is, a ghost cannot enter a tile from the left side and then decide to reverse direction and move back to the left. The implication of this restriction is that whenever a ghost enters a tile with only two exits, it will always continue in the same direction.

However, there is one exception to this rule, which is that whenever ghosts change from Chase or Scatter to any other mode, they are forced to reverse direction as soon as they enter the next tile. This forced instruction will overwrite whatever decision the ghosts had previously made about the direction to move when they reach that tile. This effectively acts as a notifier to the player that the ghosts have changed modes, since it is the only time a ghost can possibly reverse direction. Note that when the ghosts leave Frightened mode they do not change direction, but this particular switch is already obvious due to the ghosts reverting to their regular colors from the dark blue of Frightened. So then, the 1/60-of-a-second Scatter mode on every level after the first will cause all the ghosts to reverse their direction of travel, even though their target effectively remains the same. This forced direction-reversal instruction is also applied to any ghosts still inside the ghost house, so a ghost that hasn't yet entered the maze by the time the first mode switch occurs will exit the ghost house with a 'reverse direction as soon as you can' instruction already pending. This causes them to move left as usual for a very short time, but they will almost immediately reverse direction and go to the right instead.

Understanding Pac-Man Ghost Behavior

(via JWZ)

 

• AI learns to play Ms Pac Man - Boing Boing


• Game uses fun as incentive to solve hard chip-design problems ...


• Left 4 Dead 2: zombie game is scarier than the original, which is ...

"