Pacman

Early Handin: Sunday, December 8th, 11:59 pm EST
Regular Handin: Tuesday, December 10th, 11:59 pm EST
Late Handin: Thursday, December 12th, 5:00 pm EST

Watch the demo here!
Check out the code checkpoint here, due by Sunday, November 24th at 8:00pm!

Note: You cannot use late days on this assignment; turning in after the on-time handin will result in an automatic 8% deduction on your grade

Assignment Roadmap

Introduction

Congratulations on choosing the best project! We are super excited to have you on our team, and you should be pumped to join the league of legendary Pacman-ers! You’re going to work hard, you may have to sweat a little, but when you’re done you’ll have made PACMAN. While many of you have probably played a version of Pacman before, our requirements differ slightly from the official rules so make sure to read the specifications carefully.

Collaboration Policy Reminder

If you ever have questions about the collaboration policy, refer to the collaboration policy or ask a TA!

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

Note: The usage of any artificial intelligence technologies, except those explicitly endorsed by CS15, is strictly prohibited. Because of TAs reading your code and a software package we use called MOSS (Measure of Software Similarity), illegal collaboration is easily detected in CS15.

Helpful Resources

This handout!
Pacman Demo
Help Slides
CS15 Style Guide, CS15 GitHub Guide, and CS15 README Guide
CS15 JavaFX Guide and JavaFX Javadocs
CS15 Debugging Cheat Sheet and CS15 Debugging Cheat Sheet

Installing Stencil Code

Click here to get the stencil from GitHub - refer to the CS15 GitHub Guide for help with GitHub and GitHub Classroom.

Once you’ve cloned your personal repository from GitHub, you’ll need to rename the folder from pacman-<yourGitHubLogin> to just pacman. You will have issues running your code until you make the change.

Grading

The grade for this assignment will be determined by functionality (50%), design (35%), and style (15%). See each of those sections for more details of this grading breakdown. An ‘A’ project would meet mostly all full functionality requirements with good design and style.

Functionality

Overview

Pacman is played on a 23 x 23 grid organized into a maze. The user controls Pacman’s direction of movement with the keyboard (see Controlling Pacman for more details). The goal is to eat all of the white dots while avoiding the four ghosts (Blinky, Pinky, Inky, and Clyde) who chase after Pacman.

Initial Setup

Your board should be initially set up as shown in the image below with: Pacman in his starting square, one ghost outside of the ghost pen, and the rest of the ghosts inside the ghost pen. There are also dots and energizers on the board. Each wall, dot, energizer, ghost, and Pacman himself are initially positioned in a single square in the 23x23 grid.

You must also keep track of Pacman’s score and remaining lives. This information should be clearly visible on the screen at all times. Pacman will start with 3 lives and 0 points. The game should also have a quit button. Please note that the countdown in the demo until the game starts is extra-credit and is not mandatory.

Initial State of the Board

Gameplay

If Pacman collides with any of the ghosts, he should lose one life. Additionally, the ghosts should be returned to the pen, and Pacman’s location should be reset to the original starting location. If Pacman collides with a dot or energizer, the dot or energizer should disappear from the board, and the game score should be updated accordingly. Finally, every time an energizer is eaten, the ghosts should be set to frightened mode (read about this below) for a short time.

Ghosts

When in Scatter or Chase Mode, the ghosts move according to a breadth-first-search algorithm, which is outlined in the Ghost Behavior section. In these modes, when Pacman collides with a ghost, the game resets and he loses a life.

In Frightened Mode, the ghosts’ behavior changes and Pacman is able to eat them. The ghosts should all simultaneously change their color to blue when frightened mode begins and revert to their original colors when frightened mode ends. They don’t need to blink like they do in the demo, but they must change color to blue. When a ghost is eaten, it disappears and reappears in the ghost pen. The ghost pen periodically releases ghosts to the free square just above the pen.

Scoring

Whenever Pacman eats a dot, energizer, or ghost, the game score should be updated as follows:

Dot: +10 points
Energizer: +100 points
Ghost: +200 points

Winning and Losing

The game ends either when all of the dots and energizers are eaten or when Pacman loses all of his lives. When the game ends, the ghosts and Pacman should all stop moving, and keyboard input should be disabled.

Coding Incrementally

After you’ve watched the demo, thoroughly read this handout (especially the Design Details) to make sure you understand the project design. Take some time to come up with a plan for incremental coding – feel free to run through your plan with a friend and/or a TA in conceptual hours!

Code Checkpoint

This project will have a checkpoint with TAs to ensure you’re on track to complete the project in time! The checkpoint is less than a third of the way through the project and is there to make sure that you get started. The later parts of this project can be more time consuming than the first parts so please make sure you keep working on it after you meet the checkpoint!

You must come to Conceptual Hours to get checked off for the code checkpoint by Sunday, November 24th at 8:00pm (the time of the last pacman conceptual hours on that day), with the following requirements:

Get the board to show up with walls, dots, energizers, and ghosts in the correct positions.
Fully implement Pacman movement. This includes response to keyboard input, timeline movement, wrapping, and only making valid moves (navigating the maze properly).

Minimum Functionality Requirements

MF Policy Summary:

In order to pass CS15, you will have to meet minimum functionality requirements for all projects. If you don’t meet them the first time around, you may hand the project in again until you succeed, but you will keep your original grade. MF requirements are not the same as the requirements for full credit on the project. You should attempt the full requirements on every project to keep pace with the course material. An ‘A’ project would meet all of the requirements on the handout and have good design and code style.

Your Pacman will have to do the following things in order for you to meet minimum functionality (REMINDER: you have to achieve minimum functionality on all projects to pass the course, and since this is the final project, you cannot hand in again!)

To meet MF for Pacman:

Pacman can move around the entire board using both the timeline and key input (including wrapping)
- Timeline: Pacman moves continuously on the timeline in whatever direction he is currently moving in
- Key Input: Pacman changes direction based on key input if it is possible for it to move in the direction of key input. If it is not possible for Pacman to move in the direction of key input, he should continue moving in whatever direction he already was
- Wrapping: When Pacman reaches one of the tunnels on either side of the board, he wraps (think DoodleJump!) i.e. Pacman enters the tunnel on one side of the board and exits on the other side
Pacman collides with (‘eats’) dots and energizers
- Dots and energizers should disappear from the board after they’ve been eaten
- The score should be updated appropriately after a dot/energizer is eaten (see the Scoring section above for more information on this)
4 Ghosts should properly behave in Chase and Frightened Mode
- Pacman should be able to properly collide with ghosts in these modes – this means that either Pacman or the ghost should be reset to its original positions upon collision, depending on the ghost’s mode (see the Ghost Behavior section for more information on Pacman-Ghost collisions in different modes)
Ghosts chase Pacman using a working BFS algorithm

Full Functionality Requirements

Beyond the minimum functionality requirements, the rest of the functionality grade will depend on the following criteria:

Ghosts properly behave in Scatter, Chase, and Frightened Mode, including tunnel wrapping
Ghosts enter and exit the ghost pen in a first-in, first-out order
The game displays how many remaining lives Pacman has, starting with 3 and updated accordingly each time Pacman collides with a Ghost
When the game ends:
- Both Pacman and the ghosts should no longer be able to move and Pacman should not be able to be manipulated with the keyboard
- If you win the game (i.e. you eat all of dots and energizers)
  - A “Winner!” label appears
- If you lose the game (i.e. you lose all 3 lives):
  - A “Game Over” label appears
Quit button quits the app
No minor bugs

Bells and Whistles

The following are some ideas for extra credit bells and whistles. Only attempt to implement these after you have a fully functional Pacman game. It is a good idea to hand in a working version of your game before you tackle any extra credit.

Better turning (If the user presses a directional key and Pacman is NOT able to immediately move in that direction, he will keep going and turn in the new direction as soon as he can).
Authentic ghost target locations (see info on this here)
Authentic Pacman and Ghost appearance and animations (composite shapes!)
Ghosts turn 180 degrees when changing between modes
Pacman moves faster than the ghosts
Game continues after winning (new levels)
Ghosts return to the Ghost Pen using BFS after being eaten
Fruit
Snazzy graphics

Keep in mind that things get very difficult very quickly and time is limited! If you have any questions about how hard something would be to implement, come talk to one of the Pacman TAs. As usual, make sure that you document any extra credit that you implement in your README.

Remember that you should make sure that you have a fully functional program before working on extra credit. Remember, from the Course Missive:

“Extra credit is only to be done after the original assignment has been fully completed - if you have not met the requirements, you will not receive extra credit. Extra credit may not redefine the original assignment…
Remember: “you may not use late days on the Final Projects. If you submit your Final Project by the late deadline, the late deduction will apply.”

Implementation

Support Code

The Map

Hard-coding every piece of the initial board to their initial locations is hard work and very tedious, so we have provided you with a support class,
cs15.fnl.pacmanSupport.CS15SupportMap, to tell you where to put things on the board. This class has a static method getSupportMap() that returns a 2D array cs15.fnl.pacmanSupport.CS15SquareType[][] representing the map. Each element in this array is a value of the cs15.fnl.pacmanSupport.CS15SquareType enum as defined below, where each of the six possible values represent different types of locations on the board.

It may help to think of enums in this context the same way you might think of this array if it was made of integers, where 0 represented a wall, 1 represented a free spot, etc. – enums are functionally doing the same thing, but are more descriptive, so that SquareType.WALL represents a wall instead of a 0, for instance, representing a wall.

Name	Item holding at start
`WALL`	-
*`FREE`**	-
`DOT`	Dot
`ENERGIZER`	Energizer
`PACMAN_START_LOCATION`	Pacman
`GHOST_START_LOCATION`	Ghost

Note: FREE represents squares that initially have nothing in them, but that a Ghost/Pacman can still move into. If the square has something in it at the start, such as a dot, it is not represented by the FREE enum (but rather it would be represented by the DOT enum, for example).

Again, after the game begins, the ghosts and Pacman are free to occupy any spaces except those containing the WALL enum (and, of course, any spaces that are unreachable).

To get the map, use the method:
cs15.fnl.pacmanSupport.CS15SupportMap.getSupportMap();
The map returned can be indexed into just like a regular 2D array: map[i][j], i.e. in row, column order. As such, your entire program should be indexed in row, column order for consistency and to reduce the possibility of bugs. You must make your own 2D array and use the SupportMap to set the initial layout of the map.

You must use this array of CS15SquareType enums *only* as a means of generating an object-oriented maze, and NOT use it as your Game’s maze model. You should scan over all spots in the array once and extract the necessary information for constructing your own object-oriented maze made up of something other than CS15SquareType enums, such as maze square instances (see below). Thus, you should never refer back to the maze of CS15SquareType enums once your own maze has been created. Given that, should the CS15SquareType maze be a local or an instance variable?

As suggested above, we propose that you create your own array of maze square instances. Each maze square should know about the elements inside of it.

What kind of data structure should store these elements? How can you use polymorphism to decide what type it will hold? Can you hold all of these common types in a list?

Map generation can be tricky, so we’ve provided (very) high level pseudocode below!

High Level Pseudocode - Map Generation

Retrieve 2D array typeMap from CS15SupportMap
Initialize map: MAZE_DIMENSION * MAZE_DIMENSION array of type MazeSquares

loop through map and populate with MazeSquares and set their locations

for each row in map
    for each col in map
	Based on CS15SquareType at corresponding index of typeMap, place 
        game object (i.e. DOT, ENERGIZER, PACMAN, etc.) in appropriate
        location based on map index and add graphically to pane

Wrapping

You will notice that there are two FREE squares in the maze where Pacman and the ghosts can move out of the frame. When they move out, they should wrap around to the other side. See the demo for a demonstration of how this should work.

The BoardCoordinate class

We’ve added the BoardCoordinate class to the stencil code for you. The purpose of the class is to conveniently store board coordinate pairs – (row, col) – together in one object so that you can reference them together.

Using this class will help you avoid indexing bugs in your BFS (like going out of bounds) and other parts of the project by throwing an error when you create an invalid coordinate object. When an error is thrown, a descriptive error message will be printed to help you know what went wrong.

However, there is one time that you may want to create an out of bounds coordinate object: when creating target squares during Chase mode for ghosts. Occasionally, the target for a Ghost will be an out of bounds coordinate, since the target is based on an offset from Pacman (See Ghost Behavior) rather than Pacman’s actual location. In this case, you would want to set the boolean parameter isTarget in the BoardCoordinate constructor to be true, so that the class can allow an out of bounds coordinate object to be created for this case only.

You don’t have to change the BoardCoordinate class at all (you also don’t have to use it if you don’t want to – it is purely an object for convenience’s sake), but make sure to read through the code and the comments and have a firm understanding of what the purpose of the class is, as well as how to use it, before incorporating it into your code.

Ghost Behavior

The ghosts navigate the board in three different modes

Chase: the ghosts chase Pacman
Scatter: the ghosts move toward the corners of the map
Frightened: the ghosts move randomly

During normal gameplay, the ghosts alternate between Chase mode and Scatter mode. The length of each mode is up to you, but we suggest alternating between 20 seconds of Chase mode and 7 seconds of Scatter mode. These two modes use a breadth-first-search algorithm in order for the ghosts to reach their targets as quickly as possible.

The most important aspect of ghost behavior is that a ghost should never do a 180-degree turn in any mode. (Note: In the real Pacman game, the ghosts turn around every time they switch between modes. You’ll get extra credit points if your ghosts do this, but we aren’t requiring it.)

Chase Mode

In Chase Mode, the Ghosts chase Pacman (crazy, right?). Each ghost should have a target that is relative to Pacman’s location – these targets should be unique for each ghost. Here are some suggestions for target locations (see the Bells and Whistles section if you’re interested in implementing the targeting system from the original Pacman game):

Pacman’s location (Blinky, the red ghost that starts outside of the pen)
2 spaces to the right of Pacman’s location
4 spaces above Pacman’s location
3 spaces to the left and 1 space down from Pacman’s location

If Pacman collides with a Ghost while in Chase Mode, he should lose a life and the game should be reset (all the ghosts and Pacman are reset to their original starting locations).

Scatter Mode

In Scatter mode, each Ghost’s target should be a different corner of the board.

If Pacman collides with a Ghost while in Scatter mode, he should lose a life and the game should be reset, just like in Chase Mode.

Frightened Mode

When Pacman eats an Energizer, Frightened Mode is activated. The Ghosts should all turn light blue and move in a random direction at every timestep.

If Pacman collides with a Ghost in Frightened Mode, Pacman eats the Ghost and the Ghost returns to the ghost pen.

Again, the length of this mode is up to you, but we suggest 7 seconds.

BFS

When a Ghost needs to make a decision about where to turn, it must choose the direction that will bring it to its target the fastest. You will be implementing a modified, beefed-up Breadth-First Search (BFS) algorithm to determine this optimal direction. You'll learn a lot more about breadth-first searches and other shortest-path algorithms if you take CS200.

The general idea behind BFS is to first search all the squares neighboring you, then expand and search the squares neighboring your neighbors, then expand again, and so on, until the entire maze has been searched. A BFS guarantees that a target will be reached first by the shortest path. Note that we need to somehow mark which squares have already been visited, so we don’t loop around the maze forever.

Example of BFS path starting at the ghost’s location and searching for Pacman’s location, examining all possible neighbors at each step.

Hand Simulation

In our implementation of BFS, we will mark each square as “visited” with the initial direction the search took to reach that square. That way, when we finally reach our target, it will be conveniently marked with the optimal direction the ghost should take!

Here is a simplified simulation of our BFS, with Pacman as our target. The ghost starts out moving right.

First, we find all the directions in which the ghost can move. Remember that ghosts cannot make a 180 degree turn, nor can they turn into walls. In this case, the ghost can either move up or right. We launch our search in each of these valid directions, marking those squares neighboring the ghost with their respective directions.

Next, we check the neighbors of the neighbors. The square that was marked as “up” checks all its unmarked neighbors (in this case there is only one) for the target, marking them all with “up.” Likewise the square that was marked “right” checks all of its unmarked neighbors and marks them with “right” to indicate that they have been visited.

Note that each square has four neighbors, but we only check those to which the ghost can move. That means we don’t check squares that are walls. What about making sure the ghosts never turn 180 degrees? Fortunately, we have already accounted for this rule by never checking a square that has already been visited. This makes it impossible for any trail to double back on itself. Please take time to think about this and understand how this works.

We continue expanding our search, looking for the target. *Note that even though the path taken by the initial “up” direction turns to the right, all the squares along the path are still marked “up”.*

Here, our search has located the target! We’ve reached the square containing Pacman and marked it with “up”, because that’s the direction with which its preceding square was marked. Now we know that moving up will take the ghost to Pacman fastest. If our target was always Pacman, we could be done with this algorithm now...

*However, what if the target is not reachable?* With our targeting scheme, it may be that the target square (e.g. two squares in front of Pacman) is actually a wall as shown to the right, which our current BFS would never reach. Oh no! What then?! How will we know when to end our BFS? There is a solution, but before you continue reading, make sure you have a concrete grasp of how the current BFS simulation works.

Okay, ready?

Because we need to account for unreachable targets, we can no longer end the BFS when the target has been found. Rather, we are going to make a breadth first traversal of the entire map, looking for the open square closest to the target. The process of visiting our neighbors first, then our neighbors’ neighbors, etc. remains exactly the same. We will also use the same technique of marking squares as “visited” with directions.

Here’s where the search changes: Every time we visit a square, we will compute the distance between that square and the target square. Throughout the entire traversal, we will keep track of the current minimum distance between a square and the target. At the end of the traversal, we will return the direction with which the absolute minimum-distance square is marked, which will be the correct direction to take!

Here is a simulation of our final algorithm, with implementation specifics. Now our target is off of the board, marked by an X.

We make a new 2D array of Directions that is the same size as our maze. We will use this array to mark squares as “visited” and allow the neighbors to know what direction was “taken” to reach it. The value of a cell should be null when it is unvisited.

We will refer to the squares by their Pacman.BoardCoordinates, a class in the stencil representing valid coordinates in the board.

Finally, to maintain the order of squares to visit, we will use a queue! (We recommend using Java’s built-in LinkedList to implement a queue!) Since Java only has a Queue Interface, and LinkedList implements Queue, this would look something like:

Queue<Type> myQueue = new LinkedList<>();

Before we begin the traversal, we start by marking the ghost’s neighboring squares as visited (in the 2D array) and enqueuing them (as Pacman.BoardCoordinates).

During the traversal, each time we dequeue a square to check its distance to the target, we will mark its neighbors as visited and add them to the end of the queue to be checked later. This ensures that we always visit our neighbors before we visit our neighbors’ neighbors, and so on. This approach puts the “breadth-first” in BFS, so make sure you understand how it works!

Now let’s start. After visiting the first two squares, we update the minimum distance to be the length of the line in yellow. The current minimum-distance square is likewise shown in yellow.

Note that all the squares in the queue have already been marked with a direction. This means that when you dequeue a square, it can tell you the direction with which to mark its unvisited neighbors and update the direction we are keeping track of!

Remember, to get the next square to examine, we simply dequeue from the queue. Each time we dequeue a square, we do the following:

Calculate the distance to the target square.
Update the minimum distance if necessary.
Find the square’s unvisited neighbors, mark them with the current square’s direction, and stick them at the end of the queue.

Eventually, the entire maze will have been traversed. All squares in the 2D array will be fully marked with directions (except for the wall squares) at the end of the BFS search. This will allow us to know the minimum distance to get to that square, along with the direction the ghost would need to move in to make it to this square...This is the direction we need! In this example, we find that the ghost should move down to get to the target.

So your 2D array of directions might look something like this (logically) once the entire maze is traversed:

Note: In this example, the red ghost is initially moving to the right, so moving left would not be an option since ghosts should never make a 180-degree turn!

High Level Pseudocode

for each of the ghost’s valid neighboring squares:
    add the square’s location (the square’s position in the 2D array) to 
    the queue and store the square’s direction in the 2D array, indexed 
    by its location
while the queue isn't empty:
    dequeue the next square location
    update the shortest distance and board coordinate
    for each valid neighbor of the current square:
        if the neighbor has not been visited, add its location to the 
            queue and store the current square’s direction in the 2D array at
            the neighbor’s row-col coordinates
return the direction of the closest square

Final note: Even though each ghost has a different target, their breadth first search algorithms are the same. You should not have to repeat the code for breadth first search in more than one place. Think about how to accomplish this.

Collision Detection

Collisions in Pacman are simple: A collision occurs if Pacman’s location on the grid is the same as another object’s location on the grid. However, the result of a collision differs greatly depending on what object Pacman collides with. There are many ways to handle collisions, so make sure to be generic and extensible in your implementation.

Here are some questions to consider:

How often will you check for collisions?
How will you handle multiple collisions? (What if Pacman collides with a dot and a ghost at the same time? A dot and two ghosts?) Hint: It shouldn’t matter how many objects Pacman collides with at once. Your design should be able to handle any number of simultaneous collisions and your score should update appropriately.
- Note: at some point while coding, you may stumble upon the idea to use a Java keyword, instanceof, to determine the actual type of an object stored in a list polymorphically. Resist this temptation! Using instanceof in this manner defeats the benefits of polymorphism and is poor object-oriented design.
What if you want to add fruit to the game later? Your design should make it as easy as possible to add new objects or change collision rules.

When detecting collisions, there is a common bug that occurs when Pacman and a ghost are moving toward each other. If the timing is right, it is possible for the two to switch cells at the same time. Since they were never in the same cell, the collision isn’t detected and Pacman runs right through the ghost!

There is a simple solution to this bug:

Move Pacman
Check for collisions
Move the ghosts
Check for collisions

These four steps should happen one after another in this order.
Note: This is not the only solution. Feel free to come up with your own.

Design

Controlling Pacman

As mentioned in the Gameplay section, you will use the keyboard to control Pacman’s movement. (Refer back to the Tetris handout if you forget how to do this.) Similar to checking movement validity in Tetris, your Pacman needs to check if the direction it's headed towards is valid before it moves. The direction that Pacman heads towards is determined when a directional key is pressed (i.e the key input that corresponds to a direction), and then Pacman begins moving in that direction only if he is free to move in that direction. He continues moving in that direction until he either runs into a wall or is told to turn in a new, valid direction. When Pacman runs into a wall, he stops moving.

You may notice that in the demo, if a directional key is pressed when Pacman cannot move in that direction, he will move in that direction at the next possible intersection; this feature is extra-credit and is NOT required. For minimum and full functionality, if a directional key is pressed and Pacman cannot move in that direction, he should continue moving in whichever direction he was already moving until he runs into a wall and stops.

You can use any keys you like for your directional keys, but make sure to document your choice in your README and game play instructions.

Pacman/Ghost Movement

Pacman and the ghosts both have unique features to their movement. Specifically,

Ghosts should never be able to turn 180 degrees
Pacman should move continuously on a timeline, changing direction only when an arrow key is pressed. Note: if a directional key is pressed and Pacman cannot move in that direction, it should continue moving in whichever direction he was already moving.

It might be helpful to have a special data type to represent the various directions (up, down, right, left) that these characters can move in. Hint: what other data type have we created that aren’t classes or interfaces?

Ghost Pen

When Pacman eats a ghost, it is sent back to the ghost pen. The ghost pen should release a ghost into the maze at periodic intervals. You might want to think about using a counter…see how you might be able to tie this into some of the Ghost Behavior below! The ghosts should be released in the same order that they enter the pen.

Style

Refer to the CS15 Style Guide for the specific style guidelines along which your code will be graded.

Handing In

README

In CS15, you’re required to hand in a README file (must be named README) that documents any notable design choices or known bugs in your program. Remember that clear, detailed, and concise READMEs make your TAs happier when it counts (right before grading your project).

You are expected to create your own README file. Please refer to the CS15 README Guide for information on how to create a README, what information your README should contain, and how you must format it.

At the bottom of your README, add the approximate number of hours you spent on this project. This will be used only to average how long the projects are taking students this semester, and it is completely anonymous.

Handin

To hand in your assignment, follow these steps:

In a terminal, move into the pacman folder
Add, commit, and push your code to GitHub
Type the command rm *.class (Mac) or del *.class (Windows)
This will remove the .class files that are created when compiling so that your submission only includes .java code files.
Submit your Pacman GitHub repository to the Gradescope

If you do not submit all the proper files, we will allow you to resubmit with a 5 point penalty, only if you’ve pushed your code to GitHub prior to the deadline. If your code wasn’t pushed to GitHub by the deadline and you submit incorrectly to, we will grade whatever was submitted.

You can submit as many times as you want prior to the deadline, and only your most recent handin will be graded. If you handin before the deadline and again after the deadline, the submission will be counted as late.

Do not include any identifying information on your handin, including file names (name, login, Banner ID) as we grade anonymously. Including identifying information will result in a deduction from your assignment.