In Pacman do the ghosts choose paths independently for finding pacman?

Question

So I have been playing a lot of pacman on my cell lately and am wondering how do the ghosts seem to work independent of each other. I was thinking about how it would have been programmed.

One option that I thought of was threads. All 4 ghosts are running in their own threads and somehow find pacman's position. But it seems a bit to much to have four threads working and syncing would be hard. Also, google wrote pacman in Javascript which doesn't support threads, so it can be done without threads and there has to be an easier way.

My second thought was event handlers. I just wire the 'directionChanged' event that pacman will fire to 4 event handlers, one for each ghost. Each ghost then decides what path to take to get to pacman. This I think is more likely what is happening. But it can get slow if the event handlers are synchronously executed, because paths will have to be calculated sequentially and the 4th ghost will take time to change direction and this might create a visible lag (probably). Also, the ghosts would fire an event themselves when they hit a wall and their event handlers would change the ghosts direction. But given the frequency with which pacman changes directions and the four ghosts respond, event handlers also seem a bit too much.

I am saying the above ideas would be a bit too much because remember the game was written 30 years ago when cpu time and memory were scarce, so I think there has to be a much easier way.

Also, it seems that the ghosts are following different paths even when pacman is still. Do all the ghosts use completely different or differently optimized path finding algorithms?

I am more interested in finding out how all the ghosts seem to work for themselves simultaneously than the path finding algorithms they use. Thoughts?

Answer 1

There's a lot of great information about how pacman works here including some detailed write ups about the ghosts behavior.

**Note I found this information from http://stackoverflow.com/questions/2604022/pathfinding-algorithm-for-pacman a while ago.

Answer 2

Before rendering each frame, I would loop over the ghosts. No events, threads, or async issues that way. Each ghost probably has a very crude heuristic for scoring its moves and making up its mind (turning left or right, no action, whatev).

Here's an implementation you could check out. :)

Answer 3

You're drastically over-thinking this.

Threads and event-handlers are terribly slow by video game standards. Multi-threaded game engines are a relatively new invention, literally decades after Pacman was released. Pacman's meager logic will occur inside a single fairly tight loop, something like this:

while (!pacman_dead) {
  foreach ghost {
    if (ghost has hit a wall) {
      if (pacman to left) turn left
      if (pacman to right) turn right
    } else {
      go straight
      if (ghost touched pacman) {
        pacman_dead = true
      }
    }
  }

  handle_input();
  move_pacman();
  draw_screen();      
}

Answer 4

Anti objects are one technique: http://en.m.wikipedia.org/wiki/Antiobjects