Due: Friday, March 17, 2017, 11:59 pm

Spatial Simulation: Follow the Mushroom-Brick Road

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

Problem Description

This week, you will be simulating four very different types of agents on a gridded landscape:

• Patches of Fertile Ground: a select few of the grid cells will contain a FertileGround object. Grid cells close to FertileGround objects will be more likely to grow Mushrooms.
• Mushrooms: each grid cell will contain a mushroom of size zero or greater. At each time step, the probability of mushroom increasing its size is proportional to its distance from the nearest patch of fertile ground.
• Path Vertices: some of the grid cells will contain path vertices. Each path vertex is part of a doubly-linked list that forms a path through the grid.
• Gatherer: there is one Gatherer in a simulation. The Gatherer's goal is to collect as many mushroom bits as possible while being confined to Path Vertices. At each time step, the Gatherer takes one step along the path, collects mushrooms within a neighborhood of its current vertex, then moves the vertex in hopes it is more profitable the next time she arrives on that vertex.

Together, the simulation results in mushroom growth (and consumption), a path with moving vertices, and a gatherer that traverses the path back and forth.

Above is a zoomed in image of the simulation, using open green squares to indicate fertile patches, brown circles to represent mushrooms (their size is proportional to the mushroom's size), open blue squares to indicate path vertices, and a solid red square to indicate the gatherer.

Tasks

1. Agent: copy Agent.java from last week. Change all references from x to col (int) and from y to row (int). I.e. The new methods should be
   • public Agent(int r, int c) a constructor that sets the position.
   • public int getRow() returns the index of the row of the grid containing the Agent.
   • public int getCol() returns the index of the column of the grid containing the Agent.
   • public void setRow( int newRow ) sets the row index.
   • public void setCol( int newCol ) sets the column index.
   • public String toString() returns a String containing the row and column indices, e.g. "(3, 4)".
   • public void updateState( Landscape scape ) does nothing.
   • public void draw(Graphics g) does nothing.

   Write a main method and test your class.

2. Mushroom: create a Mushroom class extending the Agent class. There is no need to override updateState because Mushrooms are passive. They will be created and grown by the Simulation class and shrunk by the Gatherer class. A Mushroom should store its size (int) and implement the following methods:
   • public Mushroom(int r, int c) constructor that sets the column and row positions. It should initialize the size to zero.
   • public int getSize() returns the size.
   • public void grow() increments the size by one.
   • public void shrink() decrements the size by one, but don't allow it to have size < 0 (i.e. if the size is 0 then shrink has no effect).
   • public void die() sets the size to zero.
   • Add a draw method that centers a circle in its grid space. Make the assumption that each grid cell is gridScale x gridScale pixels large. You are free to use the code below, or to make something more interesting:

     public void draw(Graphics g, int gridScale) {
       if (this.size == 0) {
           return;
       }
       int xpos = this.getCol()*gridScale; // upper left corner of grid square.
       int ypos = this.getRow()*gridScale; // upper left corner of grid square.
       g.setColor( new Color( 0.87f, 0.72f, 0.53f ) );
       g.fillOval( xpos-this.size/2+gridScale/2, ypos-this.size/2+gridScale/2, this.size, this.size );
     }
     

   • public String toString() returns a String specifying the size of the mushroom (e.g. "a Mushroom of size 3").

   Write a main method to test all of the methods in the class (except for the draw method, which you can test later). Test it and fix it until it works perfectly.

3. Landscape: create a Landscape class modeled after the Game of Life Landscape. It does not require an advance, reset, or clone method. It should have fields to store a random number generator, a 2D grid of Mushrooms, an array list of fertile patches, a linked list (your doubly-linked list) of path vertices, and a Gatherer:

       private Random gen;
       private Mushroom[][] grid;
       // Uncomment these lines as you write the FertileGround, PathVertex, and Gather classes.
       //private ArrayList<FertileGround> growthPatches;
       //private LinkedList<PathVertex> path;
       //private Gatherer gatherer;
   

   It should implement the following methods:

   • public Landscape( int rows, int cols, int numGrowthPatches, int numPathVertices) a constructor that constructs a landscape that can hold a grid of Mushrooms with the given number of rows and columns. Later in the project, it will need to make fertile patches, a path, and a gatherer. For now, leave that out and ignore the parameters controlling their number. For now, initialize the random generator field and the mushroom grid (filling it with new Mushrooms).
   • public int getRows() returns the number of rows in the landscape.
   • public int getCols() returns the number of columns in the landscape.
   • public Mushroom getMushroom( int row, int col ) returns a reference to the Mushroom located at position (row, col).
   • public String toString() returns a string providing useful information about the Landscape. This may be as simple as its dimensions.
   • public void draw( Graphics g, int gridScale ) draws all of the Mushrooms in the grid. Later, you will need to add code to draw the fertile patches, path vertices, and the gatherer.

   Write a main method to thoroughly test your other methods (except for draw). Test it. Fix it. Test it. Fix it...

4. LandscapeDisplay: create the LandscapeDisplay class. Copy it from an earlier project and make the necessary updates to run it. Then run it and debug any drawing issues with your Landscape or Mushroom classes.
5. FertileGround: create a FertileGround class that extends the Agent class. It requires no new fields and only two methods:
   • public FertileGround(int r, int c) a constructor.
   • public void draw(Graphics g, int gridScale) a draw method. One way to draw the fertile patch would be with an open rectangle that is gridScale x gridScale pixels.

   Write a main method to test the class. Test it.

6. Update the Landscape class to support the FertileGround patches.
   1. Uncomment the field storing the patches.
   2. Add code to the Landscape's constructors to create a line of patches across the grid:

          this.growthPatches = new ArrayList<FertileGround>(numGrowthPatches);
          int stride = cols/numGrowthPatches;
          for (int i = 0; i < numGrowthPatches; i++) {
              this.growthPatches.add( new FertileGround( rows/2-rows/6, 
                    i*stride+gen.nextInt( 3*stride/4 ) ) );
          }
      

   3. Add code to Landscape.draw to call the GrowthPatch's draw method.
   4. Test the new code using LandscapeDisplay.
   5. Write a method that finds the GrowthPatch closest to a given position and returns the distance to it:

      public double findDistanceToNearestGrowthPatch( int row, int col )

      The method should loop through the FertileGround list, determining the Euclidean distance of each patch of fertile ground and (row,col). Return the smallest value.

      Note: To compute the Euclidean distance, compute the square root of the sum of the squares of the distance in rows and in columns. I.e. to compute the distance between (row1,col1) and (row2,col2), then you could use the following code:

              double dist = Math.sqrt( (row1-row2)*(row1-row2) + (col1-col2)*(col1-col2) );
      

   6. Test findDistanceToNearestGrowthPatch. It is up to you to design this test code. One option is to add code to your Landscape that explicitly tests a few hard-coded positions.
   7. Write a method that will grow the mushrooms in (possibly) many randomly chosen grid cells, with a probability proportional to the distance of each grid cell to its closest growth patch.

   public void growMushrooms(int numTries)

   The function should randomly generate numTries grid positions. For each position, it should compute its distance d to the nearestGrowthPatch. Then it should increase the size of the mushroom in that grid cell with probability 1/d.

   Hint: for a randomly generated position (r,c), this code will randomly grow a mushroom with the correct probability:

       double d = this.findDistanceToNearestGrowthPatch( r, c );
       double probability = 1/d; 
       if ( this.gen.nextDouble() < probability ) {
           this.grid[r][c].grow();
       }
   

7. Simulation: create a simulation class modeled after Simulation classes from earlier projects. Write a method to test simulation of mushroom growth. You will probably want to call it testGrowthPatches so that later, you can write a more general run method without erasing test code. In your method, generate a Landcsape with 4 rows, 5 columns 1 growth patch, and no vertices. Then create a LandscapeDisplay for the Landscape. Finally, end with a loop (iterate 10 times) that calls the Landscape's grow method (with 10 as the input), the LandscapeDisplay's repaint method, then Thread.sleep(100).
8. PathVertex: create a PathVertex class extending the Agent class. Since path vertices are passive, they do not need to overload the updateState method. The only methods you need to implement for the PathVertex are the constructor (taking in row and column values) and the draw method. Please write those methods.
9. Make it possible to draw the path.
   1. Uncomment the field storing the path.
   2. Add code to the Landscape's constructors to create a path of vertices across the grid:

        this.path = new LinkedList<PathVertex>();
        stride = cols/numPathVertices;
        // same number of path vertices as growth patches.
        for (int i = 0; i < numPathVertices; i++) {
            this.path.addFirst( new PathVertex( rows/2-rows/6, i*stride+stride/2 ) );
        }
      

   3. The Landscape needs to provide iterators for the path - both forward and backward iterators:

       public Iterator<PathVertex> getPathIterator() {
          return this.path.iterator();
      }
      
      public Iterator<PathVertex> getPathBackwardIterator() {
          return this.path.backward_iterator();
      }
      

   4. Add code to Landscape.draw to call the PathVertice's draw method.
   5. Test the new code using LandscapeDisplay or an updated Simulation test method.
10. Gatherer: create a Gatherer class extending the Agent class. The only methods you need to implement in this task are the constructor (taking in row and column values) and the draw method. Please write those methods. (We will overload the updateState method in a later task.)
    1. Uncomment the field storing the gatherer.
    2. Add code to the Landscape's constructors to create the gatherer, giving it a default position of (0,0):

          this.gatherer = new Gatherer( 0, 0 );
       

    3. Add an accessor method to the Landscape: public Gatherer getGatherer() returns a reference to the Gatherer.
    4. Add code to Landscape.draw to call the Gatherer's draw method.
    5. Test the new code using LandscapeDisplay or an updated Simulation test method.
11. The simulation will follow this outline:
    • Create a Landscape (which will make the growth patches, the size zero mushrooms, the path, and the gatherer) and a Landscape display. (Suggested values: 40 rows, 50 columns, 10 growth patches, 10 path vertices, and a grid scale of 16).
    • Grow mushrooms (so the Landscape begins with something for the gatherer to gather). (Suggested numTries=10,000)
    • Traverse the path (back and forth) in a loop (suggest number of iterations is 10). The body of the loop does this:
      • Traverse the path forward. This is a loop using the forward iterator. The body does this:
        • Grow mushrooms (Suggested numTries=100).
        • Update the Gatherer's state - the Gatherer will update its state by placing itself on the vertex, consuming mushrooms near that vertex, then moving the vertex to a more profitable location.
        • Repaint the Landscape.
        • Pause for a few milliseconds Thread.sleep( 100 );
      • Traverse the path backward. This is a loop using the backward iterator. The body does this:
        • Grow mushrooms (Suggested numTries=100).
        • Update the Gatherer's state - the Gatherer will update its state by placing itself on the vertex, consuming mushrooms near that vertex, then moving the vertex to a more profitable location.
        • Repaint the Landscape.
        • Pause for a few milliseconds Thread.sleep( 100 );

    Implement the above simulation method. You cannot test it until you write Gatherer.updateState, so begin with a very simple updateState that accomplishes only the first step - i.e. that places the Gatherer on the vertex:

    public void updateState( PathVertex v, Landscape scape ) {
        int row = v.getRow();
        int col = v.getCol();
        this.setRow( row );
        this.setCol( col );
    }
    

    Now you are in a position to test your simulation. Do so. Spend time debugging. You are almost there!

12. Improve Gatherer.updateState so that the Gatherer will eat the mushrooms, keeping track of the biggest spot. Then move the Vertex to the most fruitful spot and make sure the Gatherer moves with it. Here is a more detailed outline:
    • Initialize variables that will keep track of the location and size of the largest mushroom so far

          int biggest_mushroom = 0;
          int biggest_ridx = row;
          int biggest_cidx = col;
      

    • At each grid cell within 3 rows above and 3 rows below and 3 columns to the left and 3 columns to the right (i.e. in a 7x7 grid centered at the Gather's location),
      • Get the mushroom at that position. (i.e. call scape.getMushroom)
      • Shrink the mushroom (i.e. call its shrink method).
      • If it is bigger than the biggest seen so far, then update biggest_mushroom, biggest_cidx, and biggest_ridx.
    • Move the vertex and the Gatherer to (biggest_ridx, biggest_cidx).
13. Test the simulation. Then adjust parameters to see if you can run a simulation in which the path vertices end up on top of the growth patches. This is really challenging, so don't expect it to work out perfectly. You will need to save at least one simulation as an animated gif. More than one (if they are qualitatively different and you include text explaining what made them) will count as an extension.

Extensions

1. Adjust parameters to change the character of the simulation. Record the simulation as an animated gif. In your write-up, discuss what changes you made to the code to elicit the changes in the simulation.
2. Try additional initial configurations. In your write-up, include new animated gifs demonstrating them.
3. Implement alternate strategies for the Gatherer to move the path vertices. One option is to allow the Gatherer to see mushrooms beyond her neighborhood, then make a decision based on this more global information. Another option would be to have the Gatherer move fewer cells in each time step - maybe restrict its movement to just one grid cell in each direction, but use the most profitable direction.
4. Record the number of mushroom pieces gathered by the Gatherer during each simulation. For each simulation set-up (i.e. each set of parameters and each strategy), run the simulation 5 times, ignore the simulations with the smallest and largest numbers of mushroom pieces, and compute the mean of the middle 3. Report that mean. If you have mulitple sets of parameters, then you can discuss in your write-up how the change in parameters leads to a change in total mushroom consumption.
5. Draw the edges between the vertices. To do so, you will need to add parameters to PathVertex.draw.
6. For any assignment, a good extension will be to implement a Java class that you have't implemented in the past projects and demonstrate that it has the same functionality as the Java class.

Writeup

Your writeup should have a simple format.

• A brief description of the overall task, in your own words.
• An explanation of your solution, focusing on the interesting bits. In this assignment, for example, Gatherer.updateState and the overall simulation are the interesting bits. You can include code snippets in your writeup to help describe your solution. A code snippet is usually less than 10 lines of code.
• Printouts, pictures, or results to show what you did. For this assignment, you should include animated gifs of the simulations.
• Other results to demonstrate extensions you undertook. If you tried different neighborhood sizes, for example, show how those affected the overall simulation results.
• A brief conclusion and description of what you learned.
• A list of people you worked with, including TAs, and instructors. Include in that list anyone whose code you may have seen, such as those of friends who have taken the course in a previous semester.

Handin

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.

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

cs231s17project5

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.

© 2017 Ying Li. Page last modified: .