CS 231: Data Structures and Algorithms (Lab Page)

Title image Project 4
Fall 2016

Spatial Simulation: Finding Friends

The main purpose of this project is to give you an opportunity to use your linked list within the context of an agent-based simulation.

In this week's simulation, we will have Agents that are on a 2D landscape. They will have positions in a continuous (floating point) 2D space, rather than the grid from the Game of Life. Like in the Game of Life, the agents are active and will implement an updateState method.

This week, we will be discarding the need for a scale parameter. Consider your units to be pixels, so, if your Landscape's size is 500 by 500, then the Agents' positions should be between 0 and 500. You also will want to update the LandscapeDisplay class to remove all uses of the scale.


  1. Agent - create an Agent class (it is up to you whether or not you want to make it abstract, but the instructions are written as if it is not). We will be making two forms of agents (agents with different updateState methods). This means we will be using inheritance and need to begin with a base class - the Agent class. It needs (double) fields to store the x and y positions and should implement the following methods:
    • public Agent(double x0, double y0) - a constructor that sets the position.
    • public double getX() - return the x position
    • public double getY() - return the y position
    • public void setX( double newX ) - set the x position
    • public void setY( double newY ) - set the y position
    • public String toString() - return a String containing the x and y positions, e.g. "(3.024, 4.245)"
    • public void updateState( Landscape scape ) - does nothing
    • public void draw(Graphics g) - does nothing

    Also, remember to import java.awt.Graphics so the compiler knows about the Graphics type.

    Write a simple main method to test your class and its methods. Compile and run it. Make sure it works perfectly.

  2. Grouper - create a Grouper class. The first agent we will implement will ultimately move towards other agents, creating groups of agents. We will name the class Grouper and it will extend the Agent class.
    public class Grouper extends Agent

    The new class does not need any additional fields, but will need to override the constructor, updateState, and draw methods. We will save updateState for a later task. For now, implement these methods:

    • The constructor, which simply calls the super class constructor:
          public Grouper(double x0, double y0) {
              super( x0, y0 );
    • public void draw(Graphics g) - draws a circle of radius 2.5 (i.e. it fits in a 5x5 box) at the Agent's location.

    Write a simple test method. Compile and test your class so far (excluding draw). Get it working perfectly.

  3. Landscape - create a class called Landscape. It serves the same purpose as the Landscape in the Game of Life simulation, but is different enough that you probably don't want to copy the old one and edit it. Start afresh. The Landscape will need fields to store its width and height (as ints) and a LinkedList of Agents. (Note that you need to you your implementation of a linked list). It needs the following methods:
    • public Landscape(int w, int h) - a constructor that sets the width and height fields, and initializes the agent list.
    • public int getHeight() - return the height
    • public int getWidth() - return the width
    • public void addAgent( Agent a ) - adds an agent to its list of agents
    • public String toString() - return a String representing the Landscape. It can be as simple as indicating the number of Agents on the Landscape.
    • public ArrayList<Agent> getNeighbors(double x0, double y0, double radius) - return a list of the Agents within radius distance of the location x0, y0.
    • A method to draw all of the agents on the Landscape:
          void draw( Graphics g ) {    
              // draw all the agents
              for (Agent a: this.agents ) {
                  a.draw( g );

    Write a simple test method, compile, run, and debug.

  4. Make it possible to visualize your Landscape. Copy LandscapeDisplay.java from two weeks ago. Test your visualization by running LandscapeDisplay as your main program. You will need to update the main program to create new Groupers and add them to a Landscape.
  5. Add a method to your Grouper class.

    public void updateState(Landscape scape) - It should implement the following rules.

    	If the cell has more than 3 neighbors within a radius of 3, then 
    	    the cell should move +/- 5 with a 1% chance
    	    the cell should move +/- 5

    Note that the Cell's motion should be a continuous value between +5 and -5 in both X and Y. You can use the Random class's nextFloat or nextDouble method to get a random floating point value between 0 and 1.0.

  6. Add a method to your Landscape class

    public void updateAgents() - update the state of each agent, in a random order.

  7. GrouperSimulation - create a GrouperSimulation class. It should be modeled after the LifeSimulation class. It would be best to control the Landscape size and the number of agents from the command line, but it is acceptable to hard-code them. Generate and randomly place agents (and N of 200 is reasonable) on in the Landscape. Then loop over the time steps, calling updateAgents, repaint, and Thread.sleep as in LifeSimulation. Use saveDisplay to generate the images for an animated gif, once you have it working.
  8. CategorizedGrouper - create a CategorizedGrouper class that extends the Grouper class. This is our second agent (since CategorizedGrouper is a Grouper and Grouper is an Agent, CategorizedGrouper is also an agent). public class CategorizedGrouper extends Grouper

    The new class should have an integer field category and implement or override the following methods.

    • public CategorizedGrouper(double x0, double y0, int cat) - call the parent constructor and set the category.
    • public int getCategory() - return the category value.
    • public String toString() - return a single character string indicating the category.
    • public void updateState(Lanscape scape) - implement the following rule.

      Identify how many neighbors have the same category (as this.getCategory()) and how many have a different category.

          If there are more of the same category
             move +/- 5 with a 1% chance
             move +/- 5 
  9. CategorizedGrouperSimulation - create a CategorizedGrouperSimulation class. Model this class after GrouperSimulation, using CategorizedGroupers instead of Groupers. Test it using 3 categories.
  10. Create one other type of agent that extends the Grouper class and has a different update rule. Show simulations for it. Explain what individual behavior you are trying to model with your new agent type. (Example: the original Grouper class is modeling a preference for clumping, while the second Grouper class is modeling the impact on group behavior of subtle individual preferences.)


Each assignment will have a set of suggested extensions. The required tasks constitute about 85% of the assignment, and if you do only the required tasks and do them well you will earn a B+. To earn a higher grade, you need to undertake at least one extension. The difficulty and quality of the extension or extensions will determine your final grade for the assignment. One significant extension, or 2-3 smaller ones, done well, is typical.

  1. Instead of making separate main classes for each type of simulation, write just one Simulation class and make it possible for the user to control the type of Groupers from the command line.
  2. See if you can mix and match different agent types and write about what happens.
  3. Try out additional Grouper subclasses with different update rules.
  4. Experiment with the effects of modifying some of the update rules. These should be compare and contrast. Try to avoid comparing simulations where more than one thing has been changed.
  5. For any assignment, a good extension will be to implement a Java class yourself and demonstrate that it has the same functionality as the Java class. For example, you could implement your own ArrayList class for this assignment.
  6. For any assignment, a good extension will be to annotate your code to indicate all places where memory is "lost" (in other words, each place where the last remaining reference to an object is either destroyed or is given a new value). If you do this extension, please indicate so in your write-up.


Make your writeup for the project a wiki page in your personal space. If you have questions about making a wiki page, stop by my office or ask in lab.

Your writeup should have a simple format.

Once you have written up your assignment, give the page the label:


You can give any wiki page a label using the label field at the bottom of the page. The label is different from the title.

Do not put code on your writeup page or anywhere it can be publicly accessed. To hand in code, put it in your folder on the Courses fileserver. Create a directory for each project inside the private folder inside your username folder.