Pac-Man Implementation

References

The Pac-Man Dossier

Architecture Overview

By utilizing service discovery and ad-hoc networking, all of the robots operate independently and autonomously. There is no centralized controller controlling the game, each robot makes its own decisions and sends its own commands. Pac-Man is the only robot that takes human input, and this is simply in an "augmented control capacity" where user input is limited to valid directions of travel (no passing through boundaries). The laptop and GUI provided for the operator provide no computational support for the game, its simply a node that allows the operator to issue commands. A good example of the level of autonomy in the robots is when a ghost kills Pac-Man. Upon determining that it has killed Pac-Man, it issues a command to Pac-Man to let it know it was killed, and then informs all of the other ghosts that Pac-Man was killed. Pac-Man performs his death, and then informs all of the other robots that they need to reset for another round.

More information can be found in the ad-hoc networking, application layer networking, and service discovery sections.

Board Simplification

The first step in building Roomba Pac-Man was to simplify the board. This was done mainly due to limited space and the desire to keep the programming simple. The board was gridded up into an 10x11 square grid and boundaries were defined using a KML file to be fed into the GUI. The figures below show the actual board, and the simplified board.

Pac-Man Control

Joystick

The first two axes of the joystick are used for movement, and two of the buttons are used for game control (one for reset, the other to signify the start of the game). After attaching the joystick to any computer running a GUI, the user may designate which Roomba is to receive control using its node window (see "user interface"). Only Roombas running the code to behave as Pac-Man will accept joystick commands. Once control is enabled, the joystick commands are sent over the network to the desired Roomba. The Roomba then quantizes the commands into four directions (UP,DOWN,LEFT,RIGHT) and allows the movement controller to handle the user input.

Pac-Man Movement

Movement is tricky given issues with implementing the game in the real world. The most prominent problem is simply specifying "drive" and "turn" commands will not ensure the Roombas stay within the boundaries (small deviations in heading direction will cause the Roomba to drive off course). It is for this reason that a guidance algorithm is used as a low level control.

The guidance algorithm ensures that the Roomba travels only in the forward direction, and keeps it within the center of the map cells. Movement performed by either the automatic movement controller (such as with the ghosts) or from the quantized joystick inputs is limited to specifying a "target" and "desired" cell on the grid. Once a target cell is specified, the low level movement controller takes over. It first performs a turn until the Roomba is within +/- pi/18 of the heading to the target cell. Following the turn, the Roomba then drives forward until it is within an error bound of the center of target cell. Small heading corrections are made along the way to keep the Roomba heading toward the center of the target cell.

The desired cell is used to specify the next motion to be performed. This is usually determined by looking at the joystick input for a displacement from the target cell, or by the automatic controller on a ghost.

As an example, consider a Roomba that has just been initialized to its starting point on the grid. To make this interesting we'll consider this to be a Pac-Man roomba, and the user is sending inputs through the joystick. Both the desired and target cell are initialized to the current location of the Roomba. This case is shown below.



The user now pushes the joystick to the left. After checks are performed to determine if this is a valid direction of travel, the desired cell is set to the cell to the left of the Roomba. Since the Roomba is currently in the target cell, the target cell is set to the desired cell. The robot then rotates to within the error bounds of the desired heading and starts to head forward. These steps are shown below.



Now the user changes his input to the down direction. After ensuring this is a valid direction to travel, the desired cell is set to one cell below the target cell. While the Roomba is transiting to the target cell, the desired cell is free to change. When the Roomba is within the error margin of the center of the target cell, the desired cell is now set to the target cell and the Movement controller begins to turn the Robot towards the correct direction.



Power Pellets

The Roomba acting as Pac-Man maintains the pellets as "targets" and relays these targets to any subscriber on the system, allowing for visualization using the GUI. Once Pac-Man enters a cell with a pill, he sends a message to all ghosts indicating that he is "powered-up." Following a delay, the power-up wears off, and Pac-Man then sends a message to all ghosts indicating the power-up is over. This allows for a change in ghost behavior along with a visual representation presented to operators using the GUI.

Ghost Behavior

The link posted at the top of this page covers the ghost behavior pretty extensively from the original game if you are interested in learning how it was originally done. The implementation here had to be changed for various reasons, and was slightly simplified to reduce development time.

Ghost Movement

Ghost movement is performed by constraining the directions of travel and then picking one of the remaining allowable directions at random. There are four main constraints on the movement of a ghost: location of boundaries, collision avoidance, state dependent movement, and the inability to reverse directions. Only the location of boundaries and collision avoidance may limit the number of allowable directions of movement to zero. The other constraints are ignored if they will make the Roomba stop moving.

State based movement constraints are only enforced randomly, with the likelihood fo enforcement changing between different ghosts. Each gost may be either SEARCHING for Pac-Man, TRACKING Pac-Man, or RUNNING from Pac-Man. In each of these states the "probable" ghost movement is simplified by allowing for a controller to specify the desired angle of movement. This angle is quantized into 8 different directions. If the angle is within a margin of an allowed direction of travel, that particular direction is set to be an "allowed" direction. An example of this is shown below.



If the desired angle of movement is not within a margin of an allowed direction, both the nearest allowed directions are set to be an "allowed" direction. An example of this is shown below.



Collision Avoidance

Collision avoidance is strictly followed and can constrain the ghost to no allowable directions. Collision avoidance performed only when another ghost comes within two squares. Two cases are considered: head on collisions and collisions from the side. For the first case, two squares are examined up, down, left, and right. If any of the cells contain a ghost, and there are no walls between the other ghost and this ghost, the direction of travel is not allowed. If there is a wall in between the two ghosts, the direction remains an allowed direction. In the diagram below, Blinky is behind a wall and does not cause a constraint. Clyde, however, is not behind a wall and therefore constrains the allowed directions of motion.



For sideways collisions, the diagonal squares are examined. If they contain a ghost then the walls around the diagonal square are considered to determine allowed directions of travel. The best way to explain this case is through an example. In the figure below, Pinky is in a diagonal square, and the square permits movement up and right. Since Pinky's square is to the lower-left, movements to the left and down are constrained (although down was already constrained by the presence of a wall). Clyde in this case is also in a diagonal square. This square permits movement down, but not left. The wall keeps up as an allowable direction, but movement to the right is constrained.



Search

The desired angle for search is determined such that each ghost typically searches its "home" location. These locations are shown the graphic below.



Tracking

Once Pac-Man is within 3 squares, the ghost switches to tracking Pac-Man. Turns are made so that travel is probabilistically toward Pac-Man. This probability is dependent upon the "aggressiveness" of each ghost. Once Pac-Man leaves the tracking range of the ghost, it returns to searching. In the figure below, the track radius is shown. Here, Blinky is very aggressive and will always follow Pac-Man. On the other hand, Clyde is not very aggressive, and actually chooses a path away from Pac-Man.



Running

Running is quite simple, each ghost probabilistically choses a path directly away from Pac-Man.

Getting Eaten

Once Pac-Man in within range of touching the Ghost, and the Ghost has been informed that Pac-Man has a power-up, the ghost is informed by Pac-Man that it has been "killed," and is sent back to its reset point. Following return to the reset point, the ghost then returns to a search state.

Killing Pac-Man

If Pac-Man does not have a power up, the former case results in Pac-Man being killed. A command to stop the game is sent by the ghost that "killed" Pac-Man to all game participants, causing the ghosts to stop and Pac-Man to spin in place. Following a delay, Pac-Man will send a reset to all participants, and the game will be reset.