CS231

Agent-Based Simulations

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.

For this simulation, we won't have the concept of a scale factor, or you can think of the scale factor as being 1 so that coordinates map to pixels. If your Landscape's size is 500 by 500, then the Agents' positions should be between 0 and 500.

The Agent-based simulations were inspired by Growing Artificial Societies by Epstein and Axtell, two of the first researchers to make use computational modeling to examine social science questions about self-organizing societies.

Project Checklist: Before submitting your project, make sure you have completed all of the following!

All of the coding work listed under tasks
Your report describing the work you did in the project
Your reflection questions with any writing in the reflection section of the report, and code included in your code files Expect to allocate a decent chunk of time to these! They're worth 1/4 of your project grade
Your extensions should you choose to do any

Tasks

Testing

Remember to make use of the supplied test file LLTest file as you add methods to your linked list. You can test only a subset of methods by modifying the test script to run only the tests for methods you've implemented.

Wrapping up LinkedLists

Implement the Iterable interface

To enable another program to loop through the list, implement the Iterable interface, which allows a programmer to use a foreach loop structure on our LinkedLists. First, change the class definition for LinkedList to specify that it implements the Iterable interface.

    public class LinkedList<T> implements Iterable<T>

Then create an Iterator subclass that handles traversing the list. Create a new private class inside the LinkedList class with the following definition.

    private class LLIterator implements Iterator<T>

Give the class one field, which is of type Node, and which will hold the next node to be provided during a traversal. Then implement the following methods in the class.

public LLIterator(Node head) the constructor for the LLIterator given the head of a list.
public boolean hasNext() returns true if there are still values to traverse (if the current node reference is not null).
public T next() returns the next item in the list, which is the item contained in the current node. The method also needs to move the traversal along to the next node in the list.
public void remove() does nothing. Implementing this function is optional for an Iterator.

Finally, add the function iterator public Iterator iterator() to the LinkedList class. It should return a new LLIterator with head passed to the constructor, shown as the following code:

    // Return a new LLIterator pointing to the head of the list
    public Iterator<T> iterator() {
    return new LLIterator( this.head );
    }

The iterator method makes the class actually implement Iterable.

Final test of the LinkedList class

Run the full LLTest file that you downloaded at the start of the lab to test the standard LinkedList functions. Debug your code until it works! (But we hope you've already been doing this along the way).

Agent Class

Create an abstract class called Agent. The simulations will require making two forms of agents with different updateState() methods. This is an ideal situation for using inheritance, which means starting with a base class: the Agent class.

The Agent class needs fields to store its x and y position. Use type double for the agent's position. It also needs an int field named radius that stores the radius within which the agent considers another agent a neighbor, and a boolean field named moved to store whether it changed position at the last call of updateState. The radius and moved fields should have a protected access modifier, not private! Feel free to try both options and see what happens when you try to access the radius/moved field in the SocialAgent class.

The Agent class should implement the following methods:

public Agent(double x0, double y0) a constructor that sets the position.
public double getX() returns the x position.
public double getY() returns the y position.
public int getRadius() returns the radius.
public boolean getMoved() returns the moved field.
public void setX( double newX ) sets the x position.
public void setY( double newY ) sets the y position.
public void setRadius( int newRadius ) sets the radius.
public String toString() returns a String containing the x and y positions, e.g. "(3.024, 4.245)".
public abstract void updateState( Landscape scape ) does nothing, for now.
public abstract void draw(Graphics g) does nothing, for now.

SocialAgent

Create a (non abstract) SocialAgent class. The first agent we will implement will ultimately move towards other agents, creating groups of agents. SocialAgent will extend the Agent class. More information about inheritance.

The new class will need to override the constructor, and draw methods:

public SocialAgent(double x0, double y0, int radius)The constructor, which calls the super class constructor and sets the radius field. Remember to set all your class fields to some value by the end of the constructor!
```
public SocialAgent(double x0, double y0, int radius) {
    super( x0, y0 , radius );
    // remainder of constructor code
}
```
public void draw(Graphics g) draws a circle of radius 5 (i.e. it fits in a 10x10 box) at the Agent's location. If the agent moved during the last updateState, it is drawn with a lighter shade of blue, otherwise a darker shade of blue.
```
public void draw(Graphics g){
    if(!moved) g.setColor(new Color(0, 0, 255));
    else g.setColor(new Color(125, 125, 255));

    g.fillOval((int) getX(), (int) getY(), 5, 5);
}
```
public void updateState(Landscape scape) for now, leave this blank.

AntiSocialAgent

Create an AntiSocialAgent class. As opposed to SocialAgents, AntiSocialAgents try to move away from groups of Agents. AntiSocialAgent will also extend the Agent class.

The new class will need to override the constructor, and draw methods:

public AntiSocialAgent(double x0, double y0, int radius)The constructor, which calls the super class constructor and sets the radius field. Remember to set all your class fields to some value by the end of the constructor!
```
public AntiSocialAgent(double x0, double y0, int radius) {
    super( x0, y0 , radius );
    // remainder of constructor code
}
```
public void draw(Graphics g) draws a circle of radius 5 (i.e. it fits in a 10x10 box) at the Agent's location. If the agent moved during the last updateState, it is drawn with a lighter shade of red, otherwise a darker shade of red.
```
public void draw(Graphics g){
    if(!moved) g.setColor(new Color(255, 0, 0));
    else g.setColor(new Color(255, 125, 125));

    g.fillOval((int) getX(), (int) getY(), 5, 5);
}
```
public void updateState(Landscape scape) for now, leave this blank.

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 with a new file. The Landscape will need fields to store its width and height (as ints) and a LinkedList of Agents. Use your implementation of a linked list. The Landscape 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() returns the height.
public int getWidth() returns the width.
public void addAgent( Agent a ) inserts an agent at the beginning of its list of agents.
public String toString() returns a String representing the Landscape. It can be as simple as indicating the number of Agents on the Landscape.
public LinkedList<Agent> getNeighbors(double x0, double y0, double radius) returns a list of the Agents within radius distance of the location x0, y0.
public void draw(Graphics g) Calls the draw method of all the agents on the Landscape.

Visualization

Make it possible to visualize your Landscape. Download the LandscapeDisplay.java file. It is almost identical to last week.

Test your visualization by running LandscapeDisplay as your main program. The main program adds 200 agents to the Landscape and then displays them.

updateState( )

Add a method to your SocialAgent class, public void updateState(Landscape scape). If there are less than 4 agents within its own radius from itself, it changes both its x and y coordinates by a random value between -10 and 10. Make sure that it stays within the boundary of the window!

To your AntiSocialAgent class, add an analagous method that would move the Agent if there is more than 1 neighbor within its radius.

As you code this function, if the (Anti/)SocialAgent moves, set the moved field to true, otherwise set it to false.

updateAgents( )

Add a method to your Landscape class, public int updateAgents(). The method should do the following 3 things, then return the number of agents that moved during the update.

Randomly select an agent from the list and store its x and y coordinates and its radius. Then delete the agent from the linked list of agents.
Make a new AntiSocialAgent and give it the x and y coordinates and the radius of the deleted agent. Add it to the linked list of agents.
Update the state of each agent in the linked list, in whatever order you'd like. Track how many of the agents moved.

SocialAgentSimulation

Create an AgentSimulation class. It should be modeled after the LifeSimulation class. It should control the number of agents with a command line parameter N. Generate and randomly place N SocialAgents with radius 25 on a Landscape of size 500 by 500.

Create a loop that runs while the number of agents who have moved in the last time step is greater than zero and it has been running for less than 5000 iterations. You should create a variable to track the number of agents moved in the last step and set it to a non-zero value for the first iteration. You'll also need to track to number of iterations of the loop.

Inside the loop, call updateAgents and store the number of agents moved during the update (note: your method returnts this), repaint, and Thread.sleep as in LifeSimulation.

Exploration

Required Element 1:

Run experiments with the number of agents set to 50, 100, 150, 200 and 250. Record the number of iterations it takes for your simulation to stop (if it takes 5000 iterations, you can assume it timed out and put that as your result). Make a table of the number of iterations it takes the agents to stop moving by the number of agents in the simulation. Discuss the trends you see.

Required Element 2:

Make a second table, graph or video based on a set of experiments of your choice. Include it in your report and clearly describe what the experiment was (e.g. how many agents, what was the radius size, what was the grid size). Discuss the trends you see.

Reflection Questions

Please answer the following 2 questions. Put any written responses numbered in the Reflection section of your report, and include any code with your other code files. This section is worth a substantial portion of your project grade, and generally includes the type of more conceptual exercise you can expect to see on exams, so it's good preparation for that!

Question 1: The Big 6

Consider the 6 methods that we keep looking at in the worksheets:

public E getFirst(): returns the first item in the list
public E getLast(): returns the first item in the list
public void addFirst(E item): adds the given item to the start of the list
public void addLast(E item): adds the given item to the end of the list
public E removeFirst(): removes and returns the first item in the list
public E removeLast(): removes and returns the last item in the list

First, in your report detail the runtime of each of the above methods for your LinkedList. For any non-constant runtimes, explain why it is unavoidable without adding more fields to the class.

Many of your answers to the above should be linear time. Let's fix that. As we've seen in class, we can make almost all of them constant time by simply maintaining a reference to the final node. But even that is not enough to get constant time for one of the methods. As a result, we'll create what's called a Doubly Linked List: in this structure, each Node will maintain not just the next Node in the list, but also the previous.

To help you out, we've started this file for you. Your task is to fill in every method with a //TODO tag in it (the 6 methods listed above). When you think you've got it, you can use this tester to confirm.

In your report, explain which method needed a DoublyLinkedList in order to achieve a constant runtime, and why it now has a constant runtime.

Question 2: Mo Fields Mo Problems.

So far this class we've primarily focused on efficiency with respect to time. In this question, we'll look at our efficiency with respect to space. In order to do this, we'll need to talk a little bit about how Java manages its memory.

As a fun exercise, read and run this file. The behavior might be a little surprising to you! The int's value doesn't change when you increase it, but the ArrayList's contents do change. This is because primitives and Objects behave differently in Java: a primitive variable will always only refer to its value, while an Object's variable will generally refer to its memory location. As a result, the amount of memory space a primitive field holds and an Object field holds can be different.

Typically, an int in Java takes up 4 bytes of memory. Typically, a reference to an Object of any kind takes up 8 bytes of memory. As an example, let's consider ArrayLists: the fields of an ArrayList are just the underlying array and the size. The size, as an int, takes 4 bytes of memory, while the array takes 8 bytes per index. Since the array is at most twice the number of items (which we'll denote n), this means that the memory occupancy of an ArrayList is at most 4 + 16n bytes.

In your report, compute the memory size of a LinkedList of n items you built for your project, and the memory size of a DoublyLinkedList of n under the code you wrote for the first Reflection question.

Finally, in your report, describe the tradeoffs between LinkedList and ArrayLists. What are the pros and cons of each, relative to each other?

Extensions

Please submit your extensions in a separate folder from your main project! We recommend that, once you finish the project, you copy all of your files into a separate extensions subfolder and work on your extensions there. As last week, these are only recommendations and you can choose from these ideas or develop your own. Any extension you take must be adequately detailed in your report.

Try creating other agent types that implement different rule sets. Be intentional about your agent design.
Instead of moving randomly, have your agent move towards other agents, or possibly towards some and away from others.
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.

Congrats, you're done with everything except for your project report where you will communicate your findings from all that code! Make sure to write up your report in the project report file in the Google Classrooms assignment. The project report is an important part of the work in this project, so don't forget to do it!