Tutorial 3: Build a Multiagent Simulation

In this tutorial we will build a simple model of particles bouncing off walls, leaving trails, and interacting with one another.

This tutorial teaches:

Create a Basic Model

We'll start with a basic Model. In the sim/app/tutorial3 application directory reate a file called Tutorial3.java. Add to it:


package sim.app.tutorial3;
import sim.engine.*;
import sim.field.grid.*;
import sim.util.*;
import ec.util.*;

public class Tutorial3 extends SimState
    {
    public DoubleGrid2D trails;
    public SparseGrid2D particles;
    
    public int gridWidth = 100;
    public int gridHeight = 100;
    public int numParticles = 500;
    
    public Tutorial3(long seed)
        {
        super(seed);
        }

    public void start()
        {
        super.start();
        trails = new DoubleGrid2D(gridWidth, gridHeight);
        particles = new SparseGrid2D(gridWidth, gridHeight);

Wherever did you get such a phenominal implementation of Mersenne Twister?

Thank you! This implementation is believed to be the fastest Java version available anywhere, and is used fairly widely. And its author — who also wrote this tutorial — is understandably proud of it. :-) And yes, there's a synchronized java.util.Random subclass version available, though not in the MASON distribution...

Let's start with the random number generator. MASON uses an implementation of the Mersenne Twister random number genenerator algorithm called ec.util.MersenneTwisterFast. This generator is far more random than the Java-standard generator, java.util.Random, and it has a massive — for all intents and purposes infinite — generation period. You should never use java.util.Random for real simulation work: it's very bad. The provided Java implementation of Mersenne Twister, which isn't synchronized, is also about 1.5 times the speed of Java's standard generator.

The MersenneTwisterFast instance we created is stored in the instance variable random. Don't worry about having to learn a new class: MersenneTwisterFast has an identical API to java.util.Random. Just call it like you've always done (for example, random.nextInt(5); to get a random integer from 0 to 4 inclusive). But keep in mind that MersenneTwisterFast isn't threadsafe.
Is there a 2 Dimensional Grid of Objects like DoubleGrid2D is for doubles?

Yes. It's called ObjectGrid2D, and it works just like DoubleGrid2D and IntGrid2D. It differs from SparseGrid2D in important ways: first, ObjectGrid2D allows one, and exactly one, object per array location (it's just a wrapper for an Object[][] array). SparseGrid2D uses hash tables rather than arrays, and allows many objects to pile up on the same array location. Also, SparseGrid2D is much faster at looking up the location of an object, and is much more memory efficient, but looking up objects at locations is slower (a constant hash table lookup overhead). Generally speaking, if you need an array of Objects, use ObjectGrid2D. If you want a few agents scattered in different locations (possibly the same locations), use SparseGrid2D.

Also, note the declaration of a SparseGrid2D and DoubleGrid2D. Previously we used an IntGrid2D, which was little more than a wrapper for a two dimensional array of integers. Likewise, a DoubleGrid2D wraps a two dimensional array of doubles.

SparseGrid2D is a different beast. It's not an array of objects: instead it uses hash tables internally, and allows you to put an Object at a given location. Multiple objects may occupy the same location in a SparseGrid2D.

In this tutorial, we're going to make a class called Particle, which is an agent that bounces around the environment. Particles will be stored in the SparseGrid2D and will leave "trails" in the DoubleGrid2D. Particles will have a direction (x and y values of 0, 1, or -1 each). Particles will be embodied agents (they're both agents -- they're Steppable and manipulate the world ; and they're also in the world).

Let's make numParticles Particles, put them in the world at random locations, given them random directions, and schedule them to be fired as Steppables at every time step. Add:


        Particle p;
        for(int i=0 ; i < numParticles ; i++)
            {
            p = new Particle(random.nextInt(3) - 1, random.nextInt(3) - 1);  // random direction
            schedule.scheduleRepeating(p);
            particles.setObjectLocation(p,
                new Int2D(random.nextInt(gridWidth),random.nextInt(gridHeight)));  // random location
            }
Why not use java.awt.Point?

Point is mutable. So are java.awt.geom.Point2D, etc. But SparseGrid2D uses hashtables. Mutable objects break hashtables: put the location in the hash table as a key, then change the values in the location. Instant broken hashtable. This is a serious Java flaw that Sun has not said much about.

Note the use of Int2D. This class is essentially the same as java.awt.Point: it holds an x and a y location as ints. However, Int2D is immutable -- once it is constructed, its values cannot be changed. SparseGrid2D stores locations as Int2D. Likewise, SparseGrid3D stores locations as Int3D, and other fields use Double2D or Double3D.


I'm not used to code like this. Can you really make a Steppable class like that?

Sure you can. It's called an anonymous class, and it's a construct for creating one-shot classes which exist solely to provide an instance of some superclass or interface. Without it, you'd need to write something like:


package sim.app.tutorial3;
import sim.field.grid.*;
import sim.engine.*;
public class MyDecreaser implements Steppable
	{
	DoubleGrid2D myTrails;
	public MyDecreaser(DoubleGrid2D tr)
		{
		myTrails = tr;
		}

	public void step(SimState state)
		{
		trails.multiply(0.9);
		}
	}
And then say...

Steppable decreaser = new MyDecreaser(trails);
schedule.scheduleRepeating(Schedule.EPOCH,2,decreaser,1);

That's an awful lot of typing just for scheduling a Steppable which calls a single function! Instead, an anonymous class makes for simpler code. Plus note that inside the anonymous class we can directly access the trails variable, so we don't have to make some complicated constructor nonsense like in the example above. This is the approximate equivalent to what's known, in modern languages, as a closure.

Note though that in Java we can only reference trails like this if it's an outer instance variable or is a final local variable. And we have some versioning issues in using anonymous classes, which may or may not mattter to you, as is discussed further below.

As the agents traverse the world, they will leave trails by setting DoubleGrid2D locations to 1.0. Let's also create a "decreaser" agent which slowly decreases the DoubleGrid2D values.


        // Schedule the decreaser
        Steppable decreaser = new Steppable()
            {
            public void step(SimState state)
                {
                // decrease the trails
                trails.multiply(0.9);

The multiply function is a simple mapper which multiplies all values in the 2D array by 0.9. There are other simple functions like that so you don't have to do the for-loops yourself. Continuing...


                }
            };
        schedule.scheduleRepeating(
            Schedule.EPOCH,2,decreaser,1);
        }

Notice that we're scheduling the decreaser in a different fashion than before. This time we're providing four pieces of information:

An ordering is a sub-ordering of a timestep. Let's say you have ten items you want to occur at timestep 10.4321121. But you want five of those items to be stepped before the other five. You can do this by scheduling the first five for one ordering, and the second five for a higher ordering. The default ordering is 0. Within an ordering, the order of agents' firing is random.

What's the point of orderings? A variety of items occur every time the schedule steps a single timestep. For example, the GUI's displays are updated each timestep, as are various inspectors. If you want items to be performed in a certain order within a timestep, an ordering is the easy way to do it.

You could achieve a similar effect using the classes sim.engine.Sequence and sim.engine.RandomSequence, which we'll get to in Tutorial 5.

What goes at Order 1?

Patience, grasshopper, patience.

We'll schedule the Decreaser to happen at every time step as well, starting at the Epoch, -- but at Order 2 (so it happens after the Particles do their thing):

We finish with main() introduced at the end of tutorial 2. Note the change in class.


    public static void main(String[] args)
        {
        doLoop(Tutorial3.class, args);
        System.exit(0);
        }
        
    }

Save the file.

Create our Particle

Now we'll write the Particle agent. Create a file called Particle.java, and in it, add:


package sim.app.tutorial3;
import sim.engine.*;
import sim.util.*;

public class Particle implements Steppable
    {
    public boolean randomize = false;
    public int xdir;  // -1, 0, or 1
    public int ydir;  // -1, 0, or 1
    
    public Particle(int xdir, int ydir)
        {
        this.xdir = xdir;
        this.ydir = ydir;
        }

The particle will behave as follows. If it hits a wall, it "bounces" off the wall. If it lands on another particle, all particles at that location will have their direction randomized. The randomization happens by setting their randomize flags, and next time they're stepped, the Particles will randomize their own directions if necessary. The first thing we need to do is get the current position of the Particle. We could have stored that in the Particle itself, but it's easy enough to just use the location it was set to in the SparseGrid2D:


    public void step(SimState state)
        {
        Tutorial3 tut = (Tutorial3)state;
        Int2D location = tut.particles.getObjectLocation(this);

Now we leave a trail in the DoubleGrid2D at our location, and randomize direction if needed


        // leave a trail
        tut.trails.field[location.x][location.y] = 1.0;
        
        // Randomize my direction if requested
        if (randomize)
            {
            xdir = tut.random.nextInt(3) - 1;
            ydir = tut.random.nextInt(3) - 1;
            randomize = false;
            }

Now we move and check to see if we hit a wall...


        // move
        int newx = location.x + xdir;
        int newy = location.y + ydir;
        
        // reverse course if hitting boundary
        if (newx < 0) { newx++; xdir = -xdir; }
        else if (newx >= tut.trails.getWidth()) {newx--; xdir = -xdir; }
        if (newy < 0) { newy++ ; ydir = -ydir; }
        else if (newy >= tut.trails.getHeight()) {newy--; ydir = -ydir; }

Now store our new location in the SparseGrid2D.


        // set my new location
        Int2D newloc = new Int2D(newx,newy);
        tut.particles.setObjectLocation(this,newloc);

Last, get all the objects at our new location out of the SparseGrid2D and set their randomize flags.


        // randomize everyone at that location if need be
        Bag p = tut.particles.getObjectsAtLocation(newloc);
        if (p.numObjs > 1)
            {
            for(int x=0;x < p.numObjs;x++)
                ((Particle)(p.objs[x])).randomize = true;
            }
        }
    }
Bags are only for Objects?

Yes. But we also provide extensible arrays for integers (IntBag) and doubles (DoubleBag) as well. They have nearly identical functionality to Bags.

We just used a Bag for the first time. A sim.util.Bag is a wrapper for an array, like an ArrayList or a Vector. The difference is that Bags have explicitly public, modifiable underlying arrays. Specifically, Bags have an array of Objects called objs, and a count of objects called numObjs. The objects stored in a Bag run from position 0 through numObjs-1 in the objs array (objs can be longer than is actually used to store the objects). Bags also have a special fast remove function which doesn't guarantee maintaining order. The result is that Bags are significantly (over 3 times) faster than ArrayLists or Vectors.

Save the file.

Add A Simple Visualizer

Now we'll write the Particle agent. Create a file called Tutorial3WithUI.java. We begin by adding lots of stuff you've already seen before -- except we're specifying a SparseGridPortrayal2D to draw our SparseGrid2D, and we're specifying a FastValueGridPortrayal2D to draw our DoubleGrid2D (various ValueGridPortrayal2Ds can draw either DoubleGrid2D or IntGrid2D). To the file, add:


package sim.app.tutorial3;
import sim.engine.*;
import sim.display.*;
import sim.portrayal.grid.*;
import sim.portrayal.*;
import java.awt.*;
import javax.swing.*;

public class Tutorial3WithUI extends GUIState
    {
    public Display2D display;
    public JFrame displayFrame;

    SparseGridPortrayal2D particlesPortrayal = new SparseGridPortrayal2D();
    FastValueGridPortrayal2D trailsPortrayal = new FastValueGridPortrayal2D("Trail");

    public static void main(String[] args)
        {
        new Tutorial3WithUI().createController();
        }
    
    public Tutorial3WithUI() { super(new Tutorial3(System.currentTimeMillis())); }
    
    public Tutorial3WithUI(SimState state) { super(state); }
    
    public static String getName() { return "Tutorial3: Particles"; }
    
    public static Object getInfo()
        {
        return "<H2>Tutorial3</H2><p>An odd little particle-interaction example.";
        }
    
    public void quit()
        {
        super.quit();
        
        if (displayFrame!=null) displayFrame.dispose();
        displayFrame = null;  // let gc
        display = null;       // let gc
        }

    public void start()
        {
        super.start();
        setupPortrayals();
        // this time, we'll call display.reset() and display.repaint() in setupPortrayals()
        }
    
    public void load(SimState state)
        {
        super.load(state);
        setupPortrayals();
        // likewise...
        }

Why not from range Transparent Clear to Opaque White?

Don't do this unless you need to for your problem. FastValueGridPortrayal2D can draw grids in two ways: either by drawing lots of rectangles, or by poking a bitmap and stretching the bitmap to fit the area.

The problem is that in Windows and X Windows, the first method is the fastest when your colors are all opaque, but the slowest by far if the colors are transparent -- except for 100% transparent regions, which the simulator avoids drawing at all (fast!). But the second method consumes more memory and generally only runs well if you increase your heap size to something bigger than normal (see the sim.portrayal.grid.FastValueGridPortrayal2D documentation), so Windows and X Windows by default use the first method.

MacOS X's default is to always use the bitmap (MacOS X is handles bitmaps much more efficiently), except when writing to a movie or to a snapshot (see the documentation). On MacOS X, you'll likely never need to deviate from the defaults.

You can specify which method to use by calling setBuffering(...); but it's not really necessary as the user can stipulate the method to use in the 2D Options panel as well.

Now let's set up our trails portrayal, this time using the setMap method to state that values from 0.0 to 1.0 should range from black to white -- and values outside these bounds will round to either black or white.


    public void setupPortrayals()
        {
        // tell the portrayals what to
        // portray and how to portray them
        trailsPortrayal.setField(
        	((Tutorial3)state).trails);
        trailsPortrayal.setMap(
	        new sim.util.gui.SimpleColorMap(
		    	0.0,1.0,Color.black,Color.white));

So far you've only seen FastValueGridPortrayal2Ds. These are very basic portrayals which always draw their underlying doubles as squares of a given color. But that's not the general mechanism for the simulator. Instead, various Field Portrayals usually draw their underlying objects by looking up the proper SimplePortrayal registered for that object, and asking it to draw the object on-screen. The procedure for looking up the proper SimplePortrayal is used is as follows:

  1. If there is a portrayalForAll, use that.
  2. Else if the object itself implements the appropriate Portrayal interface, use the object as its own Portrayal.
  3. Else if a portrayal is registered for the object, use that portrayal. Portrayals may be registered for null as well.
  4. Else if the object is null:
    1. Use the portrayalForNull if one has been set.
    2. Else use the defaultNullPortrayal (often a gray circle).
  5. Else if a Portrayal is registered for the object's exact class (superclasses are ignored), use that.
  6. Else return the portrayalForRemainder if one has been set.
  7. Else return the defaultPortrayal (often a gray circle).
What other SimplePortrayals are there?

RectanglePortrayal2D, HexagonalPortrayal2D, and ImagePortrayal2D come to mind. It's easy to make your own Portrayals as well.

For now, we use the setPortrayalForAll method to specify that all objects stored in the SparseGrid2D should be portrayed with the same Simple Portrayal. The SimplePortrayal we pick is a green OvalPortrayal2D.


        particlesPortrayal.setField(((Tutorial3)state).particles);
        particlesPortrayal.setPortrayalForAll(
            new sim.portrayal.simple.OvalPortrayal2D(Color.green) );
                   
        // reschedule the displayer
        display.reset();
                
        // redraw the display
        display.repaint();
        }

Last, we need to build the display and add the field portrayals to it. First, add stuff you've seen before:


    public void init(Controller c)
        {
        super.init(c);
        display = new Display2D(400,400,this,1);
        displayFrame = display.createFrame();
        c.registerFrame(displayFrame);
        displayFrame.setVisible(true);
        display.setBackdrop(Color.black);

Now we attach the field portrayals. The display will draw the portrayals on top of each other. The order of drawing is the same as the order of attachment. We want the trails to be drawn first, then the particles drawn on top of them. Display2D has a menu option that lets you selectively turn on or off the drawing of these objects -- the names of the menus should be "Trails" and "Particles". Thus we write:


        display.attach(trailsPortrayal,"Trails");
        display.attach(particlesPortrayal,"Particles");
        }
    }

Run that Puppy

Save the file. Compile all three java files. Run the java code as java sim.app.tutorial3.Tutorial3WithUI. You should be able to see agents bouncing around and leaving trails! The Layers menu (the icon at the top-left corner of the Display2D) lets you turn on or off either of the two layers.

About Serialized Versioning

The simulator relies on Java's Serialization facility to do its checkpointing. Serialization writes objects, and all objects they point to (and so on) out to a stream automatically if you obey a few rules. If you don't obey the rules, you may get an exception such as a NotSerializableException.

Basic Rules

If you will only use a single java compiler to compile your code, and reuse those class files regardless of platform, this is sufficient and you can skip the rest of this section. But if you plan on using different java compilers for your code -- one to compile on your workstation and a different one to compile on your back-end server, say, or different versions of the Java JVM, then you need to be aware of some gotchas.

First Gotcha

Will Sun ever fix this stupdity?

Likely not. This misfeature has been on Sun's bugfix request list for years now.

Serialization relies on "version" numbers, essentially unique IDs for each class. They don't have to be correct; they just ought to be (but don't need to be) different for different versions of a class. Ordinarily, Java generates version numbers using the name of the class, features of its inner classes, and various fields in the class. Unfortunately, Java compilers are free to give different version numbers for different non-static inner classes or their enclosing classes! Thus if you compile a class in Linux, and the same class in MacOS X, you may not be able to hand a checkpoint file from one to the other, unless you hard-set the version numbers yourself.

This only matters if you care about moving a checkpoint file from one platform to another -- for example, running it in Linux and visualizing it on the Mac. If you don't plan on ever doing this, you can skip the rest of this section.

What we need is hard-coded version numbers for any non-static inner class and for its enclosing classes. You can make up any version number you want. But if you'd like to be extra-official today, the "one true" way to do it is to call the serialver program, part of the Java SDK. Pass it the full class name. non-static inner classes should be provided with the dollar-sign stuff appended to the end. For example, on MacOS X, compiling the Tutorial3 file results in the classes "sim.app.tutorial3.Tutorial3" and "sim.app.tutorial3.Tutorial3$1". We pass those to serialver. Note the use of the backslash in Unix to allow the $ to get passed through:


poisson> serialver sim.app.tutorial3.Tutorial3
sim.app.tutorial3.Tutorial3:    static final long serialVersionUID = 9115981605874680023L;
poisson> serialver sim.app.tutorial3.Tutorial3\$1
sim.app.tutorial3.Tutorial3$1:    static final long serialVersionUID = 6330208160095250478L;

Now that we have some version numbers (or now that we've made some up! that's fine too), we can put them into the Tutorial3 code. Tutorial3$1 is the Decreaser. In the Tutorial3 file:

FROM...CHANGE TO

// Schedule the decreaser
Steppable decreaser = new Steppable()
    {
    public void step(SimState state)
        {
        // decrease the trails
        trails.multiply(0.9);
        }
    };

// Schedule the decreaser
Steppable decreaser = new Steppable()
    {
    public void step(SimState state)
        {
        // decrease the trails
        trails.multiply(0.9);
        }
    static final long serialVersionUID = 6330208160095250478L;
    };

Similarly, we'll set the version number for Tutorial3:

FROM...CHANGE TO

    tutorial3.finish();
    }

}

    tutorial3.finish();
    }
    static final long serialVersionUID = 9115981605874680023L;
}

Second Gotcha

Now things should checkpoint and restore on different platforms smoothly. But there's a further gotcha. Because we've hard-coded the serialVersionUIDs, if we change the classes in any way, they'll be incompatible with the serialized versions of previous classes but Java won't know that and icky things could happen. This happens all through the simulator, so: if you change and recompile your code, you should not then try to load an old checkpoint file created using the old code.

Third Gotcha

Serialization doesn't work across Java Virtual Machine versions. For example, don't expect to be able to serialize code in Java 1.3.1 and load it successfully in Java 1.5.

Fourth and Final Gotcha

It may be that you have done all the versioning correctly and still it doesn't work across different platforms with different compilers; here you might get a ClassNotFoundException perhaps. There's one last possibility: the compilers are naming your inner classes differently. This isn't very common, but it's a definite possibility, and unfortunately there's no way around it. If this occurs, your only recourse is to use the same compiler and just move your .class files over to the other machine.