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?

score 13 · Answer 1 · edited May 23 '17 at 11:53

13

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 Pathfinding Algorithm For Pacman a while ago.

EDIT:

This blog post has even more information about the ghosts.

edited May 23 '17 at 11:53

Community

1
1

answered Aug 21 '10 at 02:40

GWW

43,129
11
115
108

1

holy $*^! that's an awesome page : D – Robert Karl Aug 21 '10 at 02:43
2

That is a truly great page. But that guy must not have left his apartment for weeks!! – David Hoerster Aug 21 '10 at 02:56
1

http://gameinternals.com/post/2072558330/understanding-pac-man-ghost-behavior has another great explanation of their behavior – GWW Dec 04 '10 at 02:50

user229044 · Accepted Answer · 2018-06-21T23:57:47.180

6

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 very simplified pseudocode:

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();      
}

This is a fairly common pattern in gaming, and it gives the appearance of concurrence. Typically a game will run in a single loop, which advances the game state by some tiny increment in the space between screen redraws. This is why performance is still very important in game development: Your game must iterate over every in-game object which needs to do something or make some decision (AI-controlled opponents, moving platforms, simple animations, etc) and update their state at least 30 times per second.

edited Jun 21 '18 at 23:57

answered Aug 21 '10 at 02:41

user229044

232,980
40
330
338

Though there must be a lot more logic internally, I think this should basically be the idea that must have been implemented. thanks. – Punit Vora Aug 25 '10 at 15:43
Except in the case where ghosts seek/run from you, in which case they use your location to determine the best avenue choice (or randomly chose one of the two). And for the record they need ONE thread so that they move independently of the user events (if you don't move they will get you) – Rudu Sep 01 '10 at 20:16
You need some randomness in the ghost's movements, otherwise, sooner or later all ghosts will move together in a bulk, which makes the game relatively easy. And of course a ghost doesn't have to hit a wall to change direction, he can do that on any intersection. In the original Pacman game, Ghosts can even reverse without warning. – Erich Kitzmueller Sep 02 '10 at 07:19
If my memory serves, the ghosts' movement was more random the farther away they were. Or, stated the other way, their pursuit became more heated when nearby. If you ran past a ghost while fleeing another, they did tend to pile up. Once you managed to get some separation, they would drift apart again. – Simon Oct 06 '10 at 16:15
@ErichKitzmueller: The original game uses a different algorithm for each monster; there isn't any randomness, nor is there any effort to have the ghosts avoid each other, but the use of different algorithms means that they'll often group together but won't permanently stay that way. – supercat Jun 21 '18 at 20:27

score 1 · Answer 3 · answered Aug 21 '10 at 02:40

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. :)

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

3 Answers3