Level 7  Ghosts Movement Basics
Adding the ghosts will turn this more into a game. We'll start by figuring out how to add one ghost in by creating a Ghost class. Once we do that it should be trivial to add as many ghosts as we want. One thing that should be apparent is that the ghosts will need to be able to navigate the maze like Pacman can. So they're going to need all of the methods in the PacMan class that Pacman uses to move around the maze. Instead of rewriting it for our Ghost class, we can take all of that code and put it in a generic abstract class that both Pacman and the Ghosts inherit from. Lets call that class DynamicEntity in a file called entities.py since Pacman and the Ghosts are entities that move around and change position during the course of the game as opposed to static entities like the pellets or fruit that stay in the same spot until eaten, at which point they just disappear. We'll move all of the code that isn't specific to Pacman into this class, and then have our PacMan class inherit from it. As it turns out, at this point every method that we've written for the PacMan class can be transported to the DynamicEntity class except for the update and move methods. The reason for that is because those methods look for key presses from the player in order to tell Pacman where to go. We don't want the ghosts to respond to key presses, so Pacman and the Ghosts will have their unique methods for update and move. So our Pacman class will look like the following:
Don't forget to import the DynamicEntity class from the file its saved in. I took out the tWidth and tHeight. We don't need those anymore. Notice that I also added a color variable and set it to the RGB values for yellow. The render method in the DynamicEntity class will have this self.color variable instead of having it hardcoded in. The DynamicEntity class will also have a default value for color. We'll set the default to white. I'm not going to show you all of that code, I'm sure it'll be easy to add. If you're not sure, then just download the code at the bottom of this page and check.

class PacMan(DynamicEntity):
def __init__(self, node): DynamicEntity.__init__(self, node) self.color = (255,255,0) def update(self, dt): ... def move(self): ... 
The Ghost class looks similar to the PacMan class right now. If we create a Ghost object in the run.py file and render it to the screen, then we'll just get a blue circle sitting on a node doing nothing. That's pretty boring. Let's make it do something interesting. First lets learn a bit about the key differences of how the ghosts move around the maze as compared to how Pacman moves around.

class Ghost(DynamicEntity):
def __init__(self, node): DynamicEntity.__init__(self, node, tWidth, tHeight) self.color = (0,0,255) def update(self, dt): self.position += self.direction*self.speed*dt def move(self): pass 
Understanding the Ghosts
Since we have Pacman's movement fresh in our minds, lets figure out how the ghosts are going to move around the maze. Everything I learned about how the ghosts move around came from the Pacman Dossier. That's a really good resource.
Basic Movement
Like Pacman the ghosts move around the maze from node to node. But there are several differences to how Pacman does it.
 When the ghosts are between nodes, i.e. traveling from one node to another, they cannot reverse direction.
 When the ghosts get to a node, they can go in any valid direction except for the direction they just came from. So if a ghost enters a node with 3 valid directions to choose from, there will only be two valid directions for them.
 The ghosts choose a direction when they enter a node depending on the target position they are trying to reach. They choose the direction that will bring them closer to their target position.
Step 1  Basic Ghost
Before we create the uniqueness of each of the four ghosts, let's create a generic ghost that chooses random directions to move. Whenever it overshoots a node we'll set it on top of that node and then choose a new random direction from a list of possible directions for that node.
So, basically if the ghost overshoots a node, we position the ghost onto the node, checking if it's a portal node as well. We then get the valid directions for that node and then choosing a direction randomly. We then set our direction and target node.

def update(self, dt):
self.position += self.direction*self.speed*dt overshot = self.overshotTarget() if overshot: self.node = self.target if self.node.portalNode: self.node = self.node.portalNode self.position = self.node.position validDirections = [] for key in self.node.neighbors.keys(): if self.node.neighbors[key] is not None: validDirections.append(key) index = randint(0, len(validDirections)1) self.direction = validDirections[index] self.target = self.node.neighbors[self.direction] 
We also need to give the ghost an initial direction and target node. We're assuming that the initial node the ghost is on has a neighbor to its right. We shouldn't assume that, but we will for now because we're positioning it on a node that has a neighbor to its right.

def __init__(self, node):
DynamicEntity.__init__(self, node) self.color = (0,0,255) self.direction = RIGHT self.target = self.node.neighbors[self.direction] 
This works fine, but it's not how the ghosts are implemented in Pacman. This would be a really stupid ghost. Just moving around aimlessly without any purpose. But now that we have this working we can implement the 3 bullet points above. We got the first one taken care of since we only change direction when overshooting a node rather than in between a node. Let's implement the second bullet point now.


Step 2  No Backtracking
Ghosts don't backtrack. When they enter a node, they can't leave the same way they entered. So every node will have from 1 to 3 possible direction choices.
This is easy to implement, all we need to do is not add the direction that would cause the ghost to backtrack into the validDirection list. That's all there is to it. A small change, but as you can see in the video it already makes it look a lot better.

def update(self, dt):
self.position += self.direction*self.speed*dt overshot = self.overshotTarget() if overshot: self.node = self.target if self.node.portalNode: self.node = self.node.portalNode self.position = self.node.position validDirections = [] for key in self.node.neighbors.keys(): if self.node.neighbors[key] is not None: if not key == self.direction * 1: validDirections.append(key) index = randint(0, len(validDirections)1) self.direction = validDirections[index] self.target = self.node.neighbors[self.direction] 
Looking good so far. In fact it looks a lot better than the previous version above. Almost looks like we can replace the dots with ghosts and we'd have a Pacman game. The final step is to give the ghosts some AI so that it seems like they're aware of Pacman's presence.


Step 3  AI Complete
The ghosts seem to be moving better than before, but they're still moving in a random direction every time they come to a node. As mentioned above in the third bullet point, the ghosts have a target position or 'goal' that they are always trying to reach. Their goals are all calculated differently and for different situations. This is what gives them their unique behavior. First, let's update the code to allow them to move towards some random goal, then we'll talk about how to calculate the specific goals for all of the ghosts.
Below I'll show you how we get the yellow circle to move towards the blue circle. Le'ts say the circle is initially at rest. We get it's neighbors and we compare the distances from the neighbors to the point of interest (light blue circle). We see that the LEFT neighbor has the shortest distance (blue) to the point of interest. So we move to that node by setting it as the target node and so forth. When we reach that node we check the distances of its neighbors. Notice we're not including the RIGHT neighbor since ghosts can't double back. We see that the LEFT neighbor is the closest so we move there. Now in the third image we only have two choices and its easy to see that we should move UP which will get us to the node. So all we're doing is comparing the distances between the valid neighbor nodes and the point of interest, choosing the node with the shortest distance, and moving there. We keep doing that until we reach the node. Note that there may be situations where multiple nodes will be equidistant from the point of interest. In that case we can just randomly choose between the nodes with the shortest distance. We can also have an order of precedence of something like UP, RIGHT, DOWN, LEFT. In which case if the UP and RIGHT nodes are the same distance, then we choose the UP node since that takes precedence. If RIGHT and LEFT nodes are equidistant, then we choose the RIGHT node since it has a higher precedence than the LEFT node. You can try both ways and see which one works better. I personally like the order of precedence, so I'll use that.
What I didn't show you above is what happens when the yellow circle reaches the point of interest node. One of the rules of ghost movement is that a ghost can never be stationary. Once the ghost reaches the point of interest he still has to move somewhere and can't stay on the node. In the first image below we see that the yellow circle has reached he point of interest node, but still has to move somewhere. He only has one choice since he can't double back, so he moves to the RIGHT node. Now in the second image below he only has two choices, so he moves DOWN. In the third image we see that the LEFT node is where he'll move next. At which point we're back to where we were in the third image above. As long as the point of interest is in that corner, the yellow circle will just continue to make these loops around and around.
This is the basic idea behind the ghosts movement. In order to get the ghosts to move somewhere we give them a point of interest. The point of interest doesn't have to be a node. It can be any (x, y) position, it doesn't matter if the point of interest is reachable or not. Let's update the code so that instead of choosing random directions, we give the ghost a point of interest and have him move towards it.
First thing we need to do is add a point of interest which holds a vector position. We'll set the default to position (0, 0) which is the top left corner of the screen.

def __init__(self, node):
DynamicEntity.__init__(self, node) self.color = (0,0,255) self.direction = RIGHT self.target = self.node.neighbors[self.direction] self.poi = Vector2D() 
I'm also going to put the previous code where we get the valid directions into its own method.

def getValidDirections(self):
validDirections = [] for key in self.node.neighbors.keys(): if self.node.neighbors[key] is not None: if not key == self.direction * 1: validDirections.append(key) return validDirections 
This is where we take the valid directions and return the index to the node with the shortest distance. Notice that I'm getting the squared magnitude and not the magnitude. Getting a magnitude requires you to do a square root calculation. We want to try and minimize that since getting the square root of a number takes a lot of computing, even on our super fast future computers. If you're just comparing distances, then you don't need to take the square root since if x > y, then x^2 > y^2.

def getClosestNode(self, validDirections):
distances = [] for key in validDirections: diffVec = self.node.neighbors[key].position  self.poi distances.append(diffVec.magnitudeSquared()) return distances.index(min(distances)) 
Now in the update method instead of finding a random node to move towards we call these two methods and move towards the node closest to the point of interest.

def update(self, dt):
#print self.direction self.position += self.direction*self.speed*dt overshot = self.overshotTarget() if overshot: self.node = self.target if self.node.portalNode: self.node = self.node.portalNode self.position = self.node.position validDirections = self.getValidDirections() index = self.getClosestNode(validDirections) self.direction = validDirections[index] self.target = self.node.neighbors[self.direction] 
We see that our ghost moves towards the top left corner and just circles around that area. As long as its point of interest is the top left corner, that's what he'll do. Throughout the game of Pacman, however, the ghost's point of interest changes. Now let's learn the specifics about the ghosts and figure out what points of interests we need to give them.


level7.zip  
File Size:  23 kb 
File Type:  zip 