In this tutorial we will build a basic version of Conway's Game of Life, a simple two-dimensional cellular automata. The simulation will run from the command line and will not be visualizable (that's Tutorial 2) so you'll have to take it on faith that it runs properly.
This tutorial teaches:
In the sim/app/tutorial1and2 directory, create a file called Tutorial1.java In this file, add:
package sim.app.tutorial1and2;
import sim.engine.*;
import sim.field.grid.*;
import ec.util.*;
public class Tutorial1 extends SimState
{
public Tutorial1(long seed)
{
super(new MersenneTwisterFast(seed), new Schedule(1));
}
A sim.engine.SimState is the basic class for modelling a simulation. You can think of it as a singleton object which holds all of your simulation information. You create a model by subclassing SimState and adding things to it as you like.
|
Why the ec package rather than the sim package?
Because MersenneTwisterFast was originally part of GMU's ECJ Evolutionary Computation system |
The SimState constructor needs a MersenneTwisterFast and a Schedule. We built of each and passed them in. Here we constructed the Schedule with 1 order. An order is a subdivision of a time tick. When a Schedule is ready to fire off the events at a given time tick, it must determine which events to fire first. To do this, the events are first sorted by order. Within an order, events are shuffled randomly. In our simulation, we will only have a single agent to register events for on the schedule; so there's no reason to have more than a single order.
In this simulation we will implement Conway's Game of Life, a simple two-dimensional, two-state, eight-neighbor cellular automaton. The Game of Life is played out on a 2D grid of "live" (state=1) and "dead" (state=0) cells. It begins with some initial configuration of cells. Each timestep, all of the cells simultaneously (synchronously) update themselves. Each cell uses the same rule to update itself, based on its eight neighboring cells. That rule is:
We will use a two-dimensional toroidal grid that is 100 x 100 in size, consisting entirely of 1's and 0's. To do this, we'll borrow special Field called sim.field.grid.IntGrid2D. Fields are our simulation's representation of space: they relate objects or data using some neighborhood function. In this case, our field is simply a wrapper two-dimensional array of integers. Feel free to examine the IntGrid2D code: it's very simple and straightforward. The 2D integer array it contains is public, and you are strongly encouraged to directly access the data for speed.
Add the grid as follows:
public IntGrid2D grid;
// our own parameters for setting the grid size later on
public int gridWidth = 100;
public int gridHeight = 100;
|
What's a b-heptomino?
A heptomino is seven live cells. Martin Gardner popularized the Game of Life by showing the dynamics of various heptominos, which he named the a-heptomino, b-heptomino, c-heptomino, etc. |
// A b-heptomino looks like this:
// X
// XXX
// X XX
public static final int[][] b_heptomino = new int[][]
{{0, 1, 1},
{1, 1, 0},
{0, 1, 1},
{0, 0, 1}};
void seedGrid()
{
// we stick a b_heptomino in the center of the grid
for(int x=0;x<b_heptomino.length;x++)
for(int y=0;y<b_heptomino[x].length;y++)
grid.field[x + grid.field.length/2 - b_heptomino.length/2]
[y + grid.field[x].length/2 - b_heptomino[x].length/2] =
b_heptomino[x][y];
}
Notice that we're directly accessing the grid's 2D integer field array. IntGrid2D's require that their 2D array be rectangular, so we could have written grid.width and grid.height instead of grid.field.length and grid.field[x].length respectively.
The general structure of a simulation is as follows:
We don't need a finish() method, but we do need a start() method. In this method, we need to call super.start() to let the SimState set up its Schedule. Then we create the grid and seed it. Last, we schedule our (in this case) single agent (called CA -- we'll come to that) to repeatedly manipulate the simulation:
public void start()
{
super.start(); // very important! This resets and cleans out the Schedule.
grid = new IntGrid2D(gridWidth, gridHeight);
seedGrid();
schedule.scheduleRepeating(new CA());
}
|
How do you stop an infinitely repeating schedule?
schedule.scheduleRepeating(agent) returns a sim.engine.Stoppable object. Call stop() on that object. |
Last we'll write a very simple main(String[] args) method which creates a Tutorial1 with a random seed, starts it, calls step(tutorial1) until the schedule ticks to 5000, then finishes up:
public static void main(String[] args)
{
Tutorial1 tutorial1 = new Tutorial1(System.currentTimeMillis());
tutorial1.start();
long time;
while((time = tutorial1.schedule.time()) < 5000)
{
if (time % 500 == 0) System.out.println(time);
if (!tutorial1.schedule.step(tutorial1))
break;
}
tutorial1.finish();
}
}
time is a long just to be consistent with the fact that Schedules perceive timesteps as longs.
All that's left is to write the actual agent which updates the cells in the grid. Since all the cells must be updated synchronously, at each time step this agent will dump the grid into a secondary grid; then it will update the original grid cells based on the secondary grid cell values. Create a new file called CA.java. In this file, put:
package sim.app.tutorial1and2;
import sim.engine.*;
import sim.field.grid.*;
public class CA implements Steppable
{
// the width and height will change later
public IntGrid2D tempGrid = new IntGrid2D(0,0);
|
What's an Agent?
We define an Agent in a very specific manner. An Agent is an object which can be scheduled on a Schedule to be activated at some time step, obstensibly in order for it to change the simulation environment in some way. Agents don't have to be physically in the environment (that is, in any Field). They can of course, and often are: we call such agents embodied agents. |
Here's the step(SimState) method:
public void step(SimState state)
{
Tutorial1 tut = (Tutorial1)state;
tempGrid.setTo(tut.grid); // first copy the grid into tempGrid
// for each cell...
int width = tempGrid.getWidth();
int height = tempGrid.getHeight();
for(int x=0;x<width;x++)
for(int y=0;y<height;y++)
{
int count = 0;
// count the number of live neighbors around the cell,
// and to simplify the for-loop, just include the cell itself
for(int dx = -1; dx < 2; dx++)
for(int dy = -1; dy < 2; dy++)
count += tempGrid.field[tempGrid.stx(x+dx)][tempGrid.sty(y+dy)];
// since we're including the cell itself, the rule is slightly different:
// if the count is 2 or less, or 5 or higher, the cell dies
// else if the count is 3 exactly, a dead cell becomes live again
// else the cell stays as it is
if (count <= 2 || count >= 5) // death
tut.grid.field[x][y] = 0;
else if (count == 3) // birth
tut.grid.field[x][y] = 1;
}
}
}
|
Can this be faster?
In HotSpot, you can get a 15% improvement in speed by copying instance variables to final local variables, like this:
final int width = tempGrid.width;
final int height = tempGrid.height;
final int[][] field = tempGrid.field;
final int[][] field2 = tut.grid.field;
for(int x=0;x<width;x++)
for(int y=0;y<height;y++)
{
count = 0;
for(int dx = -1; dx < 2; dx++)
for(int dy = -1; dy < 2; dy++)
count += field[tempGrid.stx(x+dx)][tempGrid.sty(y+dy)];
if (count <= 2 || count >= 5)
field2[x][y] = 0;
else if (count == 3)
field2[x][y] = 1;
}
Unfortunately, HotSpot doesn't inline the stx(...) and sty(...) methods -- they're slightly too big (real smart, Sun!). So to get still faster (a 50% improvement total), you'd also need to implement your own toroidal math instead:
for(int dx = -1; dx < 2; dx++)
for(int dy = -1; dy < 2; dy++)
{
int xx = x+dx;
int yy = y+dy;
if (xx < 0) xx += width;
else if (xx >= width) xx -= width;
if (yy < 0) yy += height;
else if (yy >= height) yy -= height;
count += field[xx][yy];
}
Some other tricks can make it a little faster yet. Anyway, the first one is easily readable. The second one is messier (eight lines replacing one line), and even though it's significantly faster, I personally don't think it's worth the trouble for more complex simulations where the toroidal math is less prevalent. |
As mentioned before, when we run the simulation from the command line, it won't do anything exciting. You can see the simulation by completing Tutorial 2.
Compile the simulation's two Java files. Then issue java sim.app.tutorial1and2.Tutorial1 from the command line. Java should run for a second, then silently finish.