Overview · Design · Rules · Files · Tasks · Simulation · Exploration · Testing · Report Format · Checklist
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.
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
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
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| Modifier | Visible in the class itself | Visible in subclasses | Visible everywhere |
|---|---|---|---|
private | yes | no | no |
protected | yes | yes | no* |
public | yes | yes | yes |
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.
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.
x by a random amount between −10 and 10 and y by a random amount between −10 and 10, then keeps the agent inside the Landscape.moved to true if it moved and false if it did not.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.
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.
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.
Every file compiles as soon as you download it; each method you need to write is marked
TODO with the task number.
Project3Tester before building the next layer.
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(T item) inserts item at the end of the list. [A, B] → [A, B, C]indexOf(Object o) returns the position of the first item satisfying item.equals(o), or -1 if there is none. [A, B, C, B].indexOf(B) → 1addLast(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.
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:
Agent(double x0, double y0, int radius) sets all four fields. A new agent has not moved.getX(), getY(), getRadius(), getMoved()setX(double newX), setY(double newY), setRadius(int newRadius)toString() returns the position with three decimals, e.g. "(3.024, 4.245)".
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.
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.
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.
A Landscape has a width, a height, a Random object, and a
LinkedList<Agent> — your LinkedList. Complete:
Landscape(int w, int h) stores the size and creates an empty agent list and a Random.getWidth(), getHeight()getAgents() returns the Landscape's agent list itself (not a copy).addAgent(Agent a) inserts an agent at the beginning of the list.toString() returns a short description that includes the number of agents.draw(Graphics g) asks every agent to draw itself.
The list is declared LinkedList<Agent>, so it can hold SocialAgents and
AntiSocialAgents side by side.
getNeighbors(double x0, double y0, double radius) returns a new
LinkedList<Agent> of every agent whose distance from (x0, y0) is
less than or equal to radius. The result must list the agents in the
same order as the Landscape's list. (Which of add and addLast
preserves order?)
removeAgent(Agent a) removes that exact agent and returns true, or
returns false if it is not on the Landscape. Two of your list methods do the work:
indexOf finds the position and remove(int index) removes it.
countSocialAgents() and countAntiSocialAgents() walk the list and use
instanceof to count each kind.
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
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.
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:
scape.getNeighbors(getX(), getY(), radius).size().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?
updateAgents()Complete public int updateAgents() in Landscape. It does four things and returns how many agents moved:
0 to size() - 1 and remove that agent with remove(index). Every index must be possible.AntiSocialAgent with the removed agent's x, y, and radius, and add it with addAgent().updateState(this) on every agent in the list, counting how many report getMoved() as true.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.
AgentSimulation
Complete public static int runExpt(int N, boolean showDisplay) in
AgentSimulation.java. Model it loosely on your LifeSimulation from Project 2.
N SocialAgents with radius 25 at random positions.showDisplay is true, create a LandscapeDisplay.updateAgents(), store how many
agents moved, and count the iteration. If showDisplay is true, call
repaint() and Thread.sleep(10).
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.
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.
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:
countSocialAgents() to record how the population changes over the course of a run.runExpt(N, false) in a loop for your data — it is far faster than
watching the display.
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.
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.
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.
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.
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.
Your discussion should address questions such as:
Answer the following questions about your LinkedList, using big-O notation where appropriate.
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.
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).
LinkedList to make addLast run in
constant time? Which other methods would then need to update that field?
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:
Agent) with its own rule set. Be intentional about its design, and evaluate it experimentally.tail field to your LinkedList so that addLast runs in constant time, and measure the effect.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.
LinkedList.java, including addLast and indexOf, is in the Project3 folder.LinkedList.java, Agent.java, SocialAgent.java, AntiSocialAgent.java, Landscape.java, LandscapeDisplay.java, and AgentSimulation.java compile together.LinkedListTester and Project3Tester and fixed every [FAIL].Extension1, Extension2, and so on. Each extension folder must contain ALL files necessary to compile and run that extension; do not rely on files located elsewhere in your Project3 folder.