GridWorld
Objective #1: Explain the rationale for the Case Study.
- College Board includes questions on the AP Computer Science exam from a case study. Currently, the case study is known as the GridWorld Case Study. In order to do well on the AP exam, you must be familiar with the content of this Case Study.
- On part 1 of the exam, students will be asked questions that have to do with analysis of the Case Study source code, explanation of design decisions, understanding the results of the execution of code, & developing test cases. There will be at least 5 multiple choice questions out of 40 that have to do with the Case Study.
- On part 2 of the exam, students will have to modify the
source code or add additional code to existing methods. One of the four
free-response questions will have to do with the Case Study. This question
will probably ask you to derive another class from Fish and override some
of its methods or add new methods. When answering this free-response question,
try to find a similar code segment in the Case Study source code and adapt
that code rather than writing something from scratch. Be sure to use equals
rather than == when necessary. Be sure to correctly use ArrayLists vs arrays
when necessary. Don't forget to cast when using the ArrayList get method.
Don't call methods from objects of the wrong type. Don't use private properties when you're writing code in a different
class.
- The case study is an important part of this Java course for a number of reasons. It requires you to work with a real-world program that is significantly longer than those typically assigned by a programming teacher. It also makes you think about issues of good programming design. It is also beneficial to study code written by expert programmers. A number of principles of object-oriented programming (OOP) are intentionally worked into the Case Study.
Objective #2: Be able to download the Case Study code and execute the projects in Eclipse.
- Download & extract the code from College Board by clicking the "Code" link in the middle of the page at http://www.collegeboard.com/student/testing/ap/compsci_a/case.html. Or, you can find the code in a folder named GridWorld in my network Handout folder. Place the folder in your Eclipse Workspace folder. Create a new project in Eclipse named "GridWorld" and click the Finish button. In older versions of Eclipse, you must click the "Create Project from existing source" radio button on the New Project dialog window. This allows you to execute the "runner" programs that are mentioned in the Case Study Narrative. See http://www.sfusd.edu/schwww/sch697/depts/math/simon/website/GridWorld1.html for more details.
- To build a GridWorld-related project from scratch, follow these steps:
- Create a New Project
- Right-click on the new project in the Package Explorer window pane on the left and select the Properties command at the bottom of the shortcut menu
- Select "Java Build Path" on the left-side of the window and select the "Libraries" tab on the right side.
- Click the "Add External JARs" button and browse to the file named gridworld.jar that is in your GridWorld Code folder that was downloaded from the College Board website. Click OK to close the window.
- Right-click on the project listing in the Package Explorer window and select the Import command. Select "File system", click "Next" and then browse to the desired classes to import.
- You will have to add the necessary import statements to the top of any classes and you can use click the red x's to get Eclipse's help with this.
Objective #3: Be familiar with the core classes & utility classes of the Case Study and their implementations. That is, you must be able to trace all the code in these classes.
- The core classes of the Case Study are the Bug, BoxBug, Critter, ChameleonCritter, AbstractGrid, & BoundedGrid classes. The Grid interface is also important. The GridWorld
API at http://horstmann.com/gridworld/javadoc is very useful for reviewing the various classes and methods.
- The grid contains one or more actors. During a single step, every actor gets a chance to act. When an actor acts it does not necessarly make a move. Other acts including changing color, changing direction, removing another actor from the grid (i.e. eating another actor), or adding a new actor to the grid.
- Bug - A Bug moves forward to an empty location or onto a flower when possible. When it moves, it lets behind a flower in its former location. When it moves onto
a flower, the flower is removed from the grid. When a bug hits the edge of the grid or another Actor, it turns 45 degrees to the right. A bug inherits many method from the Actor class but it overrides the act method and includes a few additional methods
- void act() - overridden from Actor, a bug moves if it can. If it can't move then it turns.
- void turn() - turns a bug 45 degrees to the right but its directions stays the same.
- void move() - moves bug forward and drops flower in old location
- boolean canMove() - returns true if a Bug can legally move. A move is legal if the location in front of a bug is a valid location on the grid and if it is empty or only contains a flower.
- BoxBug - BoxBug is a child of Bug. A BoxBug moves like a bug but it traces out a square with a certain side length. The act method is overridden that if a BoxBug is blocked, it makes two right turns
and starts again. A BoxBug has property called sideLength. If a BoxBug has a sideLength of k, then you will see k+1 flowers on each side of its traced out diagram.
- Critter - A Critter eats actors that are adjacent to it except for rocks or other critter's. After eating, it moves to a
random adjacent location. If there are no empty, adjacent locations, a critter does not move. A critter has overridden and new methods
- void act() - gets list of neighbors, processes them, gets list of possible locations to move to, picks one of those locations, them moves to that new location
- ArrayList<Actor> getActors() - returns a list of adjacent neighbor actors
- void processActors(ArrayList<Actor> actors) - processes the actors in the parameter. It eats anything that is not a rock or another critter. Anything else is removed from the grid (i.e. "eaten").
- ArrayList<Location> getMoveLocations() - returns a list of valid, adjacent, empty locations which are possible locations for a next move.
- Location selectMoveLocations(ArrayList<Location> locs) - selects a location for a next move
- void makeMove(Location loc) - moves the Critter to the specified location
When working with or extending the Critter class, you are not allowed to override the act method. Also, you should only change a critter's state (i.e. modify its properties) in its processActors or makeMove methods. Furthermore, you should only change the state of other actors in the critter's processActors method. (These rules don't apply to bugs however.)
- ChameleonCritter - A chameleon critter gets a list of adjacent neighbors and then it randomly picks one. Then it changes its color to the color of the randomly selected adjacent neighbor. It moves like a Critter but first changes its direction
to face the new location before moving.
- Grid interface - Grid is an interface for a two-dimensional, grid-like environment containing arbitrary objects. In GridWorld it usually contains actors. The Grid interface specifies the following methods which are implemented in the black blox class BoundedGrid. Each location in the grid is in a row-col coordinate position. For example, the location in the top-left corner is considered to be in Row 0 and Column 0 (remember RC Cola with Row always listed before Column) and is referred to as location 0, 0. The location to the right of the location 0, 0 is in position 0, 1 since it is Row #0 and Column #1.
- int getNumRows() - returns the number of rows in the grid
- int getNumCols() - returns the number of columns in the grid
- boolean isValid(Location loc) - returns true if loc is in the grid
- E put(Location loc, E obj) - puts the object obj in loc
- E remove(Location loc) - removes and returns the object (i.e. actor) that is in loc
- E get(Location loc) - returns the object (i.e. actor) that is in loc
- ArrayList<Location> getOccupiedLocations() - returns an ArrayList of occupied locations in this grid
- ArrayList<Location> getValidAdjacentLocations(Location loc) - returns an ArrayList of neighboring locations to loc that are in the grid
- ArrayList<Location> getEmptyAdjacentLocations(Location loc) - returns an ArrayList of neighboring locations to loc that do not contain objects (i.e. actors)
- ArrayList<Location> getOccupiedAdjacentLocations(Location loc) - returns an ArrayList of neighboring locations to loc that actually contain objects (i.e. actors)
- ArrayList<E> getNeighbors(Location loc) - returns an ArrayList of objects (i.e. actors) that are in neighboring locations to loc.
Objective #4: Be familiar with the black blox & utility classes of the Case Study and their available methods and constants. That is you must know their API's.
- The classes Location, Actor, Rock, & Flower are black box classes. You do not have to know how the methods in these classes are implemented but
you must be familiar with their available methods and constants (i.e. their API).
- Actor - An Actor is something that can act. It has color and direction. Actor is the parent class of Flower, Rock, Bug, & Critter. It has location, direction & color.
Actors act in "row-major" order.
That is, all of the actors in the grid's top row 0 get a chance to act from left to right and then the actors in row 1 from left to right and so on. An actor has the methods
- Color getColor() -
- void setColor(Color newColor) -
- int getDirection() -
- void setDirection(int newDirection) -
- Grid<Actor> getGrid() - this is a very important method that is used a lot. It returns null if the actor isn't currently in a grid.
- Location getLocation() - returns the actor's location
- void putSelfInGrid(Grid<Actor) gr, Location loc) -
- void moveTo(Location newLocation) - if the new location is occupied then the actor that is already in the location is removed from the grid!
- void act() - reverses the direction of the actor though this method is overridden in its child classes.
- String toString() -
- Location - The Location class keeps track of row and column values for positions in the grid.
The top left corner location within a grid is the location (0, 0). This is similar to the notation of two-dimensional arrays. It has the methods
- int getRow() -
- int getCol() -
- Location getAdjacentLocation(int direction) - returns the adjacent location in the direction closest to the direction property.
- int getDirectionToward(Location target) - returns the direction, rounded to the nearest direction, from the current location toward the parameter location.
- boolean equals(Object other) -
- int compareTo(Object other) - when two location objects are compared (0, 1) is less than (0, 2) and (1,
3) is less than (3, 0).
- String toString() -
The Location class contains the constants
Location.NORTH = 0
Location.EAST = 90
Location.SOUTH = 180
Location.WEST = 270
Location.NORTHEAST = 45
Location.SOUTHEAST = 135
Location.SOUTHWEST = 225
Location.NORTHWEST = 315
Location.LEFT = -90
Location.RIGHT = 90
Location.HALF_LEFT = -45
Location.HALF_RIGHT = 45
Location.FULL_CIRCLE = 360
Location.HALF_CIRCLE = 180
Location.AHEAD = 0
Notice how North is 0 and as you move clockwise to NorthEast and then East, you are adding degrees until you reach 360 at which point you are back to North again.
- Rock - A rock does nothing. The default color of a Rock is black.
- Flower - A flower darkens its color when it acts. The default color of a flower is pink although a constructor allows you to create a flower of another color.
- ActorWorld - This is not tested on the AP exam.
- BugRunner, BoxBugRunner, ChameleonRunner, CrabRunner, CritterRunner - These classes are not tested on the AP exam but serve as
client programs for the Case Study.
- CrabCritter - This is not tested on the AP exam but it's useful to study how it extends Critter.
- AbstractGrid - Students should be familiar with this class but they won't be tested on it. AbstractGrid contains methods that are common to all grid
implementations (BoundedGrid & other hypothetical ones.)
- BoundedGrid - Students should be familiar with this class but they won't be tested on it. BoundedGrid is implemented as a two-dimensional array of
Object's named occupantArray. The generic type E can't be used since Java doesn't allow generic arrays.
The material below is not tested on the AP exam.
Objective #5: Explore further possibilities with GridWorld.