views:

2233

answers:

17

I found a lot of references to the AI of the ghosts in Pacman, but none of them mentioned how the eyes find their way back to the central ghost hole after a ghost is eaten by Pacman.

In my implementation I implemented a simple but awful solution. I just hard coded on every corner which direction should be taken.

Are there any better/or the best solution? Maybe a generic one that works with different level designs?

+3  A: 

It's a pathfinding problem. For a popular algorithm, see http://wiki.gamedev.net/index.php/A*.

Marijn
+11  A: 

You should take a look a pathfindings algorithm, like Dijsktra's Algorithm or A* algorithm. This is what your problem is : a graph/path problem.

Clement Herreman
+14  A: 

Any simple solution that works is maintainable, reliable and performs well enough is a good solution. It sounds to me like you have already found a good solution ...

An path-finding solution is likely to be more complicated than your current solution, and hence more likely to require debugging. It will probably also be slower.

IMO, if it ain't broken, don't fix it.

EDIT

IMO, if the maze is fixed then your current solution is good / elegant code. Don't make the mistake of equating "good" or "elegant" with "clever". Simple code can also be "good" and "elegant".

If you have configurable maze levels, then maybe you should just do the pathfinding when you initially configure the mazes. Simplest would be to get the maze designer to do it by hand. I'd only bother automating this if you have a bazillion mazes ... or users can design them.

(Aside: if the routes are configured by hand, the maze designer could make a level more interesting by using suboptimal routes ... )

Stephen C
Yes it is working. However I would like to write good code and not only code. And additionally I added the last sentence in my question, so if possible the algorithm should be not only for one maze but for several.
Roflcoptr
mazes can also be generated (I have an algorithm that generates nice-looking pacman mazes), so a bit of automation is the way to go
ammoQ
"...or users can design them."In which case, you DO have a bazillion mazes.
phuzion
+48  A: 

Actually, I'd say your approach is a pretty awesome solution, with almost zero-run time cost compared to any sort of pathfinding.

If you need it to generalise to arbitrary maps, you could use any pathfinding algorithm - breadth-first search is simple to implement, for example - and use that to calculate which directions to encode at each of the corners, before the game is run.

EDIT (11th August 2010): I was just referred to a very detailed page on the Pacman system: The Pac-Man Dossier, and since I have the accepted answer here, I felt I should update it. The article doesn't seem to cover the act of returning to the monster house explicitly but it states that the direct pathfinding in Pac-Man is a case of the following:

  • continue moving towards the next intersection (although this is essentially a special case of 'when given a choice, choose the direction that doesn't involve reversing your direction, as seen in the next step);
  • at the intersection, look at the adjacent exit squares, except the one you just came from;
  • picking one which is nearest the goal. If more than one is equally near the goal, pick the first valid direction in this order: up, left, down, right.
Kylotan
Yep, really effective, but rather hard to maintain if the map grows up.
Clement Herreman
I think he means you could compute it at runtime (when the level is loaded but before you start playing it) but just *once.* That's not hard to maintain.
Mark Peters
Yeah, or if there's a tool for creating the maps, as part of that.
Kylotan
There is nothing wrong with precomputing the return paths. You're trading storage (paths) for runtime performance.
Steve Kuo
Thanks. I think Ill stick with this solution. Anybody knows how it was done in the original Pacman?
Roflcoptr
I bet it used the same algorithm the ghosts use to find you. (Because the code is already there!) Just a guess though.
trinithis
+31  A: 

For an alternative to more traditional pathfinding algorithms, you could take a look at the (appropriately-named!) Pac-Man Scent Antiobject pattern.

You could diffuse monster-hole-scent around the maze at startup and have the eyes follow it home.

Once the smell is set up, runtime cost is very low.

Dan Vinton
+1 for coolness.
womp
this was going to be my answer. It's the same as ammoQ's essentially, but I always remember about the pacman smell :)
Luke Schafer
+1  A: 

I think your solution is right for the problem, simpler than that, is to make a new version more "realistic" where ghost eyes can go through walls =)

Hernán Eche
To add even more realism, allow the ghosts themselves to be able to move through walls :D
trinithis
Those are ghost's opaque walls, but the second order ghosts, (ghost of a ghost) are more transparent. (you could find many user manuals with bugs transformed in features)
Hernán Eche
+1  A: 

Knowing that pacman paths are non-random (ie, each specific level 0-255, inky, blinky, pinky, and clyde will work the exact same path for that level).

I would take this and then guess there are a few master paths that wraps around the entire maze as a "return path" that an eyeball object takes pending where it is when pac man ate the ghost.

+38  A: 

I've solved this problem for generic levels that way: Before the level starts, I do some kind of "flood fill" from the monster hole; every tile of the maze that isn't a wall gets a number that says how far it is away from the hole. So when the eyes are on a tile with a distance of 68, they look which of the neighbouring tiles has a distance of 67; that's the way to go then.

ammoQ
Yes. Floodfill is very good for pathfinding in any situation where the world isn't too big to make it viable. I would think it could be used even in large worlds by imposing a coarser grid whose connectivity was precalculated. It would make things go slightly out of the way but that would be better than the traffic jams I've seen in such games.
Loren Pechtel
+1  A: 

The ghosts in pacman follow more or less predictable patterns in terms of trying to match on X or Y first until the goal was met. I always assumed that this was exactly the same for eyes finding their way back.

plinth
+2  A: 

Here's an analog and pseudocode to ammoQ's flood fill idea.

queue q
enqueue q, ghost_origin
set visited

while q has squares
   p <= dequeue q
   for each square s adjacent to p
      if ( s not in visited ) then
         add s to visited
         s.returndirection <= direction from s to p
         enqueue q, s
      end if
   next
 next

The idea is that it's a breadth-first search, so each time you encounter a new adjacent square s, the best path is through p. It's O(N) I do believe.

Mark Peters
+1  A: 

I don't know much on how you implemented your game but, you could do the following:

  1. Determine the eyes location relative position to the gate. i.e. Is it left above? Right below?
  2. Then move the eyes opposite one of the two directions (such as make it move left if it is right of the gate, and below the gate) and check if there are and walls preventing you from doing so.
  3. If there are walls preventing you from doing so then make it move opposite the other direction (for example, if the coordinates of the eyes relative to the pin is right north and it was currently moving left but there is a wall in the way make it move south.
  4. Remember to keep checking each time to move to keep checking where the eyes are in relative to the gate and check to see when there is no latitudinal coordinate. i.e. it is only above the gate.
  5. In the case it is only above the gate move down if there is a wall, move either left or right and keep doing this number 1 - 4 until the eyes are in the den.
  6. I've never seen a dead end in Pacman this code will not account for dead ends.
  7. Also, I have included a solution to when the eyes would "wobble" between a wall that spans across the origin in my pseudocode.

Some pseudocode:

   x = getRelativeOppositeLatitudinalCoord()
   y
   origX = x
    while(eyesNotInPen())
       x = getRelativeOppositeLatitudinalCoordofGate()
       y = getRelativeOppositeLongitudinalCoordofGate()
       if (getRelativeOppositeLatitudinalCoordofGate() == 0 && move(y) == false/*assume zero is neither left or right of the the gate and false means wall is in the way */)
            while (move(y) == false)
                 move(origX)
                 x = getRelativeOppositeLatitudinalCoordofGate()
        else if (move(x) == false) {
            move(y)
    endWhile
thyrgle
+5  A: 

Assuming you already have the logic required for chasing pacman why not reuse that? Just change the target. Seems like it would be a lot less work than trying to create a whole new routine using the exact same logic.

John Gardeniers
yes i have the logic to chase pacman already implemented, but im also not happy with it ;)
Roflcoptr
In my experience (I love writing pacman versions just for fun), doing that can lead to eyes getting stuck outside the hole for a long time. That's because the chasing algorithm generally goes along the lines of "if pacman is in the north, go north" but the maze could contain "traps" where the the eyes would have to go south first. Since pacman moves, the ghost will escape sooner or later, but the hole is a fixed target. (Note: I'm talking about generated mazes)
ammoQ
+6  A: 

In the original Pacman the Ghost found the yellow pill eater by his "smell" he would leave a trace on the map, the ghost would wander around randomly until they found the smell, then they would simply follow the smell path which lead them directly to the player. Each time Pacman moved, the "smell values" would get decreased by 1.

Now, a simple way to reverse the whole process would be to have a "pyramid of ghost smell", which has its highest point at the center of the map, then the ghost just move in the direction of this smell.

Ivo Wetzel
I really like this approach and I'll also try this one
Roflcoptr
+1 for a really interesting solution
CheesePls
+2  A: 

How about each square having a value of distance to the center? This way for each given square you can get values of immediate neighbor squares in all possible directions. You pick the square with the lowest value and move to that square.

Values would be pre-calculated using any available algorithm.

SODA
A: 

You could just use a random direction at every corner. Sooner or later they will be in the hole.

This is a very bad solution. And you can't actually be sure it works.
the_drow
+2  A: 

I would propose that the ghosts stores the path he has taken from the whole to the Pacman. So as soon as the ghosts dies, he can follow this stored path in the inversed direction.

+1  A: 

dtb23's suggestion of just picking a random direction at each corner, and eventually you'll find the monster-hole sounds horribly ineficient.

However you could make use of its inefficient return-to-home algorithm to make the game more fun by introducing more variation in the game difficulty. You'd do this by applying one of the above approaches such as your waypoints or the flood fill, but doing so non-deterministically. So at every corner, you could generate a random number to decide whether to take the optimal way, or a random direction.

As the player progresses levels, you reduce the likelihood that a random direction is taken. This would add another lever on the overall difficulty level in addition to the level speed, ghost speed, pill-eating pause (etc). You've got more time to relax while the ghosts are just harmless eyes, but that time becomes shorter and shorter as you progress.

imoatama