Overview · Design · Rules · Files · Tasks · Simulation · Exploration · Testing · Report Format · Checklist

Overview

In Project 3 you will build an agent-based simulation. Agents live on a 2D Landscape, but unlike the Cells of the Game of Life they are not locked to a grid: each agent has a floating-point position and can move anywhere. On every step, each agent looks at the other agents near it and decides whether to move. Simple local rules like these can produce surprising large-scale patterns, an idea explored by Epstein and Axtell in Growing Artificial Societies, one of the first uses of computational modeling to study self-organizing societies.

From Lab 3 to Project 3: In Lab 3 you built a generic LinkedList<T> with an iterator. In this project, your LinkedList<Agent> holds every agent on the Landscape. Every neighbor search, every removal, and every simulation step runs through the list you wrote. You will also add two new list methods, and you will think about what each list operation costs.

The project also introduces three object-oriented ideas: inheritance, abstract classes, and the protected access modifier.

LinkedList<Agent>  (yours, from Lab 3)
  ↓
Landscape: addAgent, getNeighbors, removeAgent, counting
  ↓
Agent  →  SocialAgent / AntiSocialAgent   (each decides when to move)
  ↓
updateAgents(): one simulation step
  ↓
AgentSimulation: run until nobody moves
  ↓
LandscapeDisplay

Design: Inheritance and Abstract Classes

The simulation has two kinds of agents. They have a lot in common: both have a position, a radius within which other agents count as neighbors, and a record of whether they moved. They even move the same way. They differ in only two things: when they decide to move, and what color they are drawn. That is exactly the situation inheritance is designed for.

                         Agent   (abstract)
     ------------------------------------------------------------
     private     double x, y
     protected   int radius
     protected   boolean moved

     public      getX(), getY(), getRadius(), getMoved()
     public      setX(), setY(), setRadius(), toString()
     protected   moveRandomly(Landscape scape)       <-- HOW to move (shared)
     abstract    updateState(Landscape scape)        <-- WHEN to move (each subclass decides)
     abstract    draw(Graphics g)
     ------------------------------------------------------------
                   /                            \
                  /  extends                      \  extends
       SocialAgent                            AntiSocialAgent
       updateState: move if it has            updateState: move if anyone
       company of fewer than 4                else is within its radius
       draw: blue                             draw: red

Abstract classes

Agent is declared abstract. You can never write new Agent(...), because an Agent with no rule for updateState makes no sense. An abstract class can still have fields, constructors, and finished methods that all subclasses inherit. It may also declare abstract methods — a signature followed by a semicolon and no body:

public abstract void updateState(Landscape scape);

Any non-abstract class that extends Agent must write that method, or it will not compile. That is why a LinkedList<Agent> can safely call a.updateState(this) on every element: Java guarantees every real agent has one, and it runs the version that belongs to that agent's actual class. This is polymorphism.

private versus protected

ModifierVisible in the class itselfVisible in subclassesVisible everywhere
privateyesnono
protectedyesyesno*
publicyesyesyes

The position fields x and y are private: subclasses go through getX() and setX(). The fields radius and moved are protected, because every subclass reads and sets them directly in updateState() and draw().

Try it: once your project compiles, change moved to private in Agent, recompile, and read the error message. Then change it back.
* Java also lets classes in the same package see protected members.

The Rules

Each agent asks the Landscape for its neighbors: all agents within the agent's own radius of its position. That list includes the agent itself, because it is at distance 0 from its own position.

On every simulation step, one randomly chosen agent is replaced by an AntiSocialAgent at the same position. Over time, the population changes from sociable to antisocial. Your experiments will measure how long it takes the agents to settle down.

Walk the list the efficient way

Every simulation step asks each of n agents for its neighbors, and each neighbor search looks at all n agents. Consider two ways to look at every agent:

for (int i = 0; i < agents.size(); i++) {        for (Agent a : agents) {
    Agent a = agents.get(i);   // walks from head        // the iterator remembers its place
    ...                                                  ...
}                                                    }
        ~ n2/2 node visits                           ~ n node visits

In a linked list, get(i) must walk from the head every time. Inside getNeighbors, the left-hand loop makes a 250-agent simulation run for minutes instead of seconds. Use for-each loops (your iterator) to visit agents.

Files Provided

You should already have a Project3 folder in the Projects folder of your personal Google Drive from Lab 3, containing your completed LinkedList.java. Download the Project 3 files below into that same Project3 folder.

Agent.java SocialAgent.java AntiSocialAgent.java Landscape.java AgentSimulation.java LandscapeDisplay.java Project3Tester.java

Every file compiles as soon as you download it; each method you need to write is marked TODO with the task number.

Work in order. The later tasks depend on the earlier ones. Experiment with each class and method yourself, then run Project3Tester before building the next layer.

Tasks

Task 1 — Grow Your LinkedList: addLast() and indexOf()

The Landscape needs two operations your list does not have yet. Their stubs are already at the bottom of LinkedList.java.

addLast(C):

head --> [A] --> [B] --> null          walk until current.getNext() == null,
                  ^                     then attach the new Node there
                  current

Think about the empty list for addLast: there is no last Node to attach to. And think about cost: how many Nodes does addLast visit compared with add? You will answer that question in your report.

Task 2 — The Abstract Agent Class

Open Agent.java. The class header and the two abstract methods are already written. Declare the four fields with the access modifiers from the design, then complete:

You cannot create an Agent to test it. Instead, experiment in a main() with new SocialAgent(...): its constructor already calls super(...), which runs the Agent constructor you just wrote. The tester does the same.

Task 3 — SocialAgent and AntiSocialAgent

Both classes extend Agent. Each constructor's first statement calls the parent constructor with super(x0, y0, radius). SocialAgent's constructor is written for you; AntiSocialAgent contains a placeholder super(0, 0, 0) that you must fix.

Do not redeclare inherited fields. If SocialAgent declares its own moved, it gets a second variable that hides the inherited one. Agent's methods would read one and your subclass would set the other. The tester checks for this.

Write each draw(Graphics g) method. A SocialAgent is dark blue if it did not move during its last update and light blue if it did:

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);
}

Notice that draw reads moved directly (it is protected) but must call getX() (because x is private). AntiSocialAgent uses dark red (255, 0, 0) and light red (255, 125, 125). Leave both updateState methods for Task 6.

Task 4 — Landscape Basics

A Landscape has a width, a height, a Random object, and a LinkedList<Agent> — your LinkedList. Complete:

The list is declared LinkedList<Agent>, so it can hold SocialAgents and AntiSocialAgents side by side.

Task 5 — Searching and Changing the Agent List

Landscape list:   a5 (10,15)   a4 (50,50)   a3 (10,20)   a2 (13,14)   a1 (10,10)

getNeighbors(10, 10, 5)   →   [a5, a2, a1]      a5 and a2 are exactly 5 away; a1 is 0 away
Check the display: Once Task 5 passes, run java LandscapeDisplay. Its main() places 100 SocialAgents and 100 AntiSocialAgents at random. Confirm that the window shows blue and red agents scattered across a 500 × 500 area.

Task 6 — Moving: moveRandomly() and updateState()

First write the shared movement in Agent: protected void moveRandomly(Landscape scape) changes x and y each by a random amount between −10 and 10 and then keeps the agent inside the Landscape: 0 ≤ x ≤ width and 0 ≤ y ≤ height. It is protected so that subclasses can call it but outside classes cannot.

Then write updateState(Landscape scape) in each subclass, following the rules:

  1. Get the neighbor list: scape.getNeighbors(getX(), getY(), radius).
  2. Decide whether to move, using the list's size().
  3. If so, call moveRandomly(scape) and set moved = true; otherwise set moved = false.

Experiment before running the tester: put a SocialAgent alone on a small Landscape, call updateState, and print it. Then surround it with three other agents within its radius and call updateState again. Does it stay? Is getMoved() now false?

Task 7 — One Simulation Step: updateAgents()

Complete public int updateAgents() in Landscape. It does four things and returns how many agents moved:

  1. If there are no agents, return 0.
  2. Choose a random index from 0 to size() - 1 and remove that agent with remove(index). Every index must be possible.
  3. Create a new AntiSocialAgent with the removed agent's x, y, and radius, and add it with addAgent().
  4. Call updateState(this) on every agent in the list, counting how many report getMoved() as true.
Your list, under load: Step 4 is a for-each loop over the agents, and each updateState calls getNeighbors, which runs its own for-each loop over the same list. That only works because each call to iterator() returns a new LLIterator with its own position — one of the things Lab 3 Task 9 tested.

Once Task 7 passes, uncomment the loop at the end of LandscapeDisplay.main() and run java LandscapeDisplay to watch the simulation evolve.

Task 8 — The Experiment: AgentSimulation

Complete public static int runExpt(int N, boolean showDisplay) in AgentSimulation.java. Model it loosely on your LifeSimulation from Project 2.

  1. Create a 500 × 500 Landscape and add N SocialAgents with radius 25 at random positions.
  2. If showDisplay is true, create a LandscapeDisplay.
  3. Loop while the number of agents that moved in the last step is greater than zero and fewer than 5000 iterations have run. Inside the loop, call updateAgents(), store how many agents moved, and count the iteration. If showDisplay is true, call repaint() and Thread.sleep(10).
  4. Return the number of iterations.

The showDisplay parameter lets the same method power both the visualization and fast experiments: with false, there is no window and no sleeping. The provided main() reads N from the command line:

java AgentSimulation 100          100 agents, with the display
java AgentSimulation 100 off      100 agents, no display

Start small: watch a run with 50 agents. Do the agents behave the way the rules say they should? Then run the tester. A simulation that runs until nobody moves usually needs a few hundred iterations for 50 agents; with 250 agents it typically never settles and stops at 5000.

Exploration

Required Element 1

Run experiments with the number of agents set to 50, 100, 150, 200, and 250. Because the simulation is random, run at least 10 trials for each value of N. Make a table showing, for each N, the average number of iterations it takes the agents to stop moving, and the smallest and largest values you observed. (A run that reaches 5000 iterations has timed out; record it as 5000.) Discuss the trends you see.

Required Element 2

Design a second experiment of your choice and present it as a table, graph, or video. Clearly describe the experiment: number of agents, radius, Landscape size, number of trials, and what you measured. Discuss the trends you see. Some possibilities:

Think experimentally: Decide what you will vary, what you will measure, what you will hold constant, and how many trials you need. Use runExpt(N, false) in a loop for your data — it is far faster than watching the display.

Testing

The provided tester is designed to help you make incremental progress. Work through the project in order. Before using the tester, experiment with each method yourself using small situations whose behavior you can predict.

javac *.java
java Project3Tester          // runs Task 1, 2, 3, ... and stops at the first task that needs work
java Project3Tester 6        // runs only Task 6

As in Lab 3, you do not need the -ea flag. The tester prints [PASS] or [FAIL] with expected and actual values and a hint, and reports [CRASH] (with the method and line number) or [TIMEOUT] instead of crashing itself.

Basic Tester Self Check: Passing the provided tester is an important milestone, but it performs only basic checks. Passing all tests does not guarantee that every possible case in the project is correct. The graphical display is also useful evidence, but a picture that looks reasonable is not proof that the underlying algorithm is correct.

Report Format

Your intended audience is your peers who are not in this class but who have taken a computer science course. Your reader should be able to understand what you built, the important computer science ideas behind it, what experiments you performed, and what your results mean without having completed this assignment themselves.

Report Format: Google Doc Write your report as a Google Doc named Project3 Report and keep it in your Projects/Project3 folder, next to your code. Create it there directly (New → Google Docs inside the folder) so that it is a Google Doc rather than an uploaded Word or PDF file.

Your Project 3 folder should look like this

Projects/
└── Project3/
    ├── Project3 Report          (Google Doc)
    ├── LinkedList.java
    ├── Agent.java
    ├── SocialAgent.java
    ├── AntiSocialAgent.java
    ├── Landscape.java
    ├── LandscapeDisplay.java
    ├── AgentSimulation.java
    ├── LinkedListTester.java
    ├── Project3Tester.java
    └── Extension1/              (only if you did an extension)

Your project report should contain the following sections. Please include a header for each section.

Abstract

Briefly summarize the project in your own words. Identify both the core computer science ideas and the application: a generic singly-linked list with an iterator, inheritance from an abstract class, protected members, and polymorphism, used to build an agent-based simulation.

Explain why a linked list is a reasonable structure for a population of agents that is constantly being added to and removed from, and briefly identify the experiments you performed. Detailed results belong in the Results section.

Before finishing your Abstract, ask yourself:

Results

Present evidence that your simulation works: include a screenshot of an early state and a later state of a run, and explain how the colors and positions are consistent with the rules. Then present both Required Elements of the Exploration.

Evidence → Observation → Interpretation
  1. Evidence: Present the relevant image, table, graph, or numerical result.
  2. Observation: Describe what the evidence actually shows.
  3. Interpretation: Explain what you think the result means and why it may have occurred.

Your discussion should address questions such as:

Data Structure Analysis

Answer the following questions about your LinkedList, using big-O notation where appropriate.

  1. Give the running time of add(item), addLast(item), get(index), remove(index), and indexOf(o) for a list of n items. Explain add versus addLast with a drawing of the Nodes.
  2. Give the running time of getNeighbors for a Landscape of n agents, and of one call to updateAgents. Explain why visiting the agents with a for-each loop is faster than a loop that calls get(i).
  3. Which single field could you add to LinkedList to make addLast run in constant time? Which other methods would then need to update that field?

Extensions

Describe any work you completed beyond the required project. Focus on the design and behavior of the extension: what capability you added, what classes or methods changed, how the new logic works, and how you determined that it worked. If you did not complete an extension, simply state that no extension was completed. Some possibilities:

References/Acknowledgements

List the people and outside resources that contributed to your work. Include people you worked with or received help from, including TAs and instructors, and acknowledge outside references that helped you understand an algorithm, library, or programming technique.

Before You Submit

Remember: The provided testers perform only basic checks. Passing all of their tests does not guarantee full credit on the project. Your implementation must satisfy the complete project specification.