Pacman ghost algorithms

[jrcagle]

So this isn't a Python question exactly, but the code is in Python, so there it is. I have a mostly-working version of pacman -- currently, one monster v. pacman -- that includes the usual features: eat the power-up, chase the blue or flashing ghosts, get points.

When a ghost dies, his eyes zip back to the central monster box, where he is reborn and goes back to chasing pacman.

Here's the problem: my ghost algorithm is pretty simple, and it occasionally gets confused.

If he gets to a 'decision point' -- two or more options -- he asks the maze to give him paths to the next decision points by going up, down, right, or left. He then chooses the one that takes him closest to pacman (if chasing), farthest from pacman (if fleeing or flashing), or closest to the monster box (if recovering from having been eaten). He also has a random chance to go the wrong way.

However, if the ghost is recovering and happens to hit just the right spot directly over the monster box, he gets locked into an oscillation. The .bmp below shows the problem: if the ghost goes right, the end-point of that path is closer to the box than if he goes left. But once he's gone right, the path that ends closest to the box is to the left ... and so on.

The oscillation isn't permanent; eventually, the 'random chance' factor above causes him to get back to the monster box. Still, the oscillation point is annoying to the point of affecting game play.

So: anyone have suggestions for smarter algorithms? I would hate to kludge it by checking for that specific point...

Thanks,
Jeff

[jrcagle]

Problem solved: rather than directing the recovering ghost to the decision point nearest the box, I compute the entire path from his current position to the box, as follows. The path thus generated will usually but not always be the shortest path; hence, it is 'pseudo-shortest.'

def direct_path(self, start, end):
        """
Return pseudo-shortest path from start to end.  start and end are point objects.
"""
        current = start
        paths = []
        while current != end:
            possibles = self.find_paths(current) # returns paths to nearest decision points
            for p in possibles[:]:
                # delete paths already traversed
                if p in paths:
                    possibles.remove(p)
                # special case -- the end point may not be a decision point, so we need to make sure path doesn't go past end point
                elif end in p:
                    index = p.index(end)
                    p = p[:index+1]
                    possibles = [p]
                    break

            # find shortest path
            possibles.sort(key=lambda x:\
                           self.distance(x[-1].coords,end.coords))
            
            paths.append(possibles[0])
            current = possibles[0][-1]  # last point in the path

        # list of paths now needs to be joined, understanding that the last
        # point in path n is same as first point in path n+1
        if not paths:
            return []
        final_path = paths[0]
        for p in paths[1:]:
            final_path.extend(p[1:])
        return final_path

[vegaseat]

Good thinking on your part Jeff!

[G-Do]

Hi jrcagle,

I would have said to give the ghost a memory of his last choice, then exclude the opposite of that choice as a possibility when deciding which way to go in the present decision. In other words, if the ghost just decided to move east, don't let him move back west. But your solution is more elegant.