Click here to Skip to main content
15,113,531 members
Articles / Programming Languages / Java
Article
Posted 27 Oct 2015

Tagged as

Stats

12.5K views
185 downloads
7 bookmarked

The Game Of Life, Advanced Style of Programmation

Rate me:
Please Sign up or sign in to vote.
5.00/5 (5 votes)
27 Oct 2015CPOL7 min read
The "Game of Life" is a mathematical representation of the human evolution, in which a few patterns develop through the time.

Download GameOfLife.zip

Introduction

The "Game of Life" is a mathematical representation of human evolution, in which a few patterns develop through time. Each pattern changes the state of the bidimensional orthogonal universe through the evolution of time. It is very cool to see and, with easy rules, it has incredibly complex behaviour.

Rule

The Life universe is very simple. A square grid contains cells, which may be dead or alive. The behaviour of each cell interacts with its eight neighbours, according to the following rules:

  1. Any live cell with fewer than two live neighbours dies, as if caused by under-population.
  2. Any live cell with two or three live neighbours lives on to the next generation.
  3. Any live cell with more than three live neighbours dies, as if by over-population.
  4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

It starts with a pattern on the grid - generation at time t0 - and it apply the rules at the same time, on all cells. This action results in a new pattern (generation at time t1) in which the state of bidimensional universe has been changed.

Afterwards, we apply the rules, again, on all the cells, etcetera.

That’s it. There are no other rules.

Approach

There are differents mode to approach the problem. 

There is the Probability that an unskilled developer would depart directly from the rules, without any analysis, implementing maybe the pattern MVC, without taking advantage of a possible concurrent programming style.

Most concurrent applications are organized around the execution of tasks: dividing the work of an application into tasks simplifies program organization, facilitates error recovery by providing natural transaction boundaries, and promotes concurrency by providing a natural structure for parallelizing work, acting in asynchronous mode.

Steps in Design Space

Firstly, we have to analyze the problem of identify exploitable concurrency and, then, a concurrent architecture. We can do it by identifying:

  • possible Tasks
    • a sequence of instruction that corresponds to some logical part of the algorithm. In practice this is a piece of work required to be done as a assignment (design-oriented definition)
  • data decomposition and their dependencies
    • mapping tasks in entities
      • activate the entities responsible for performing task
      • encapsulate the control logic of task execution

Data Decomposition Pattern

Conceptual class

The problem can be easily decomposed into units that can be operated relatively independently; like a divide-et-impera principle, it can be naturally decomposed into a collection of independent tasks:

  • tasks must be sufficiently independent so that managing dependencies takes only a small fraction of the program’s overall execution time
  • independence facilitates concurrency, as independent tasks can be executed in parallel if there are adequate processing resources
  • choosing good task boundaries, coupled with a sensible task execution policy, can help achieve these goals.

More precisely:

  • first, data units are identified, then task related so that units can be identified
  • in this case, task decomposition follows data decomposition
  • the execution proceeds in asynchronous mode: different tasks help to calculate the result and, afterwards, they are synchronized in passive mode through a simple monitor

Caution regarding synchronization: poisoning of the concurrent programming style

  • serializations / sequentialization are poison for performances
  • but are necessary for correctness (safety properties)

We cannot have everything in life, each story has two faces :-)

 

Architectures and patterns

In this case I’ll use the Master-Workers pattern.
The architecture is composed by a master entity and a dynamic set of worker entities, interacting through a proper coordination medium functioning as a bag of tasks

  • Master
    • decompose the global task into subtasks
    • assign the subtasks by inserting their assignment in the bag
    • collect tasks result
  • Worker
    • retrieve the task to do from the bag, execute the task 
    • communicate the results
      • the monitor of data structures can be used to aggregate and synchronize the results

Architecture

It has selected an MVC architecture, in which:

  • View: 
    • start the algorithm
    • stop the algorithm
    • design the cell over the grid
    • check the number of cell lives
  • Controller:
    • setup the Model and View
    • implement the start method
    • create a Flag for “safe start”
    • call the Model for starting the algorithm
    • implement the stop method
  • Model:
    • The Model is the core of all project, that implements the strategy chosen. 
    • We have chosen the Executor Framework to realize the strategy above: this Executor is based on the producer-consumer pattern, where activities that submit tasks are the producers (producing units of work to be done) and the threads that execute tasks are the consumers (consuming those units of work).

Let’s start!

View:
Java
public GameOfLifeView(Dimension windowsSize, Dimension matrixSize,int blockSize) {
    super("Game Of Life Viewer Small Grid");
	setSize(windowsSize);
	// Center the window in the middle of the screen
	setLocation(
				(Toolkit.getDefaultToolkit().getScreenSize().width - getWidth()) / 2,
				(Toolkit.getDefaultToolkit().getScreenSize().height - getHeight()) / 2
                );

	listeners = new ArrayList<inputlistener>();

	startButton = new JButton("start");
	stopButton = new JButton("stop");

	// When start the program, the Button "stop" is not enabled
	stopButton.setEnabled(false);

	JPanel controlPanel = new JPanel();

	controlPanel.add(startButton);
	controlPanel.add(stopButton);

	setPanel = new GameOfLifePanel(matrixSize, blockSize);
	setPanel.setSize(matrixSize);

	addMouseMotionListener(this);
	addMouseListener(this);

	JPanel infoPanel = new JPanel();
	state = new JTextField(20);
	state.setText("Ready...");
	state.setEditable(false);
	infoPanel.add(new JLabel("State"));
	infoPanel.add(state);
	JPanel cp = new JPanel();
	LayoutManager layout = new BorderLayout();
	cp.setLayout(layout);
	cp.add(BorderLayout.NORTH, controlPanel);

	// Add in the grid the Gosper Glider Gun like a test
	setPanel.CannoneAliantiGosper();

	cp.add(BorderLayout.CENTER, setPanel);
	cp.add(BorderLayout.SOUTH, infoPanel);
	setContentPane(cp);

	startButton.addActionListener(this);
	stopButton.addActionListener(this);
	setDefaultCloseOperation(EXIT_ON_CLOSE);
	setResizable(false);
}

First, I create the View in which I insert:
- Button to start
- Button to stop
- Grid (set Panel is the class that implements the Grid)
- label for check the cells - dead or alive -

Once created the view, the result of the GUI should be this:

Controller:
public class Controller implements InputListener {

	private GameOfLifeView view;
	private GameOfLifeSet set;
	private Flag stopFlag;
	
	public Controller(GameOfLifeSet set, GameOfLifeView view){
		this.set = set;
		this.view = view;
	}

	@Override
	public void started(ArrayList< point > matrix){
		set.setupMatrix(matrix);
		stopFlag = new Flag();
		new QuadratureService(set,view,stopFlag, matrix).start();	
	}

	@Override
	public void stopped() {
		stopFlag.set();
	}
}

The class Controller is very simple: given the structure of the program, the controller limiteds to linking the model and the view, creating the monitor for the method start and stop.

Model:

The Model of the program is the core the article, in which the architecture explained above comes to life.
First I create the class QuadratureService that:

  • create the thread Master that returns the status of all cells "live" or "dead" to the grid. 
  • Next, it update the grid of the model (GameOfLifeSet) and view (GameOfLifeView)
Java
/**
* Main thread to check the status of the algorithm Game of Life
* 
* @param set
* @param view
* @param stopFlag
* @param matrix
*/
public QuadratureService(GameOfLifeSet set, GameOfLifeView view, Flag stopFlag, ArrayList< point > matrix) {
	this.view = view;
	this.set = set;
	this.stopFlag = stopFlag;
	pointBoardT0 = new boolean[3][3];
}
@Override
public void run() {
	try {
		if (set.getMatrix().isEmpty()) {
			stopFlag.set();
			view.changeState("No point in Matrix!");
		}
		while (!stopFlag.isSet()) {
			Thread.sleep(50);
            //The numbers of core in your pc
			int poolSize = Runtime.getRuntime().availableProcessors() + 1;

			/*
			 * I create master which calculates the state of the cells. the
			 * result of all cells counted is saved in Variable result
			 * (ArrayList < point >) that it is passed to both the Model that
			 * the View to update the status of the structure Data and the
			 * grid display screen
			 */
			Master master = new Master(set, poolSize, stopFlag);
			ArrayList< point > result = master.compute();
			set.setupMatrix(result);
			view.setUpdated(result);

			if (stopFlag.isSet()) {
				view.changeState("Interrupted. Cell live: " + result.size());
			} else
				view.changeState(String.valueOf(result.size()));
		}
	} catch (Exception ex) {
		ex.printStackTrace();
	}
}

The Thread Master is an Executor, more precisly an Executors.newFixedThreadPool(poolSize); 
But, why should I use it?

  • newFixedThreadPool. A fixed-size thread pool creates threads as tasks are submitted, up to the maximum pool size, and then attempts to keep the pool size constant (adding new threads if a thread dies due to an unexpected Exception).
  • newCachedThreadPool. A cached thread pool has more flexibility to reap idle threads when the current size of the pool exceeds the demand for processing, and to add new threads when demand increases, but places no bounds on the size of the pool.

To keep it simple: I have created one asynchronous task for each cell alive. Statistically the cell alive are a number very high, so I prefered use the method newFixedThreadPool.

Java
public Master(GameOfLifeSet set, int poolSize, Flag stopFlag) {
	this.executor = Executors.newFixedThreadPool(poolSize);
	// this.executor = Executors.newCachedThreadPool();
	this.set = set;
	this.stopFlag = stopFlag;
}

/**
 * The function returns the list of the living cells of the game
 * 
 * @return
 * @throws InterruptedException
 */
public ArrayList< point > compute() throws InterruptedException {

	ArrayList< future < point > > pointT1 = new ArrayList< future < point > >();
	gameBoard = new boolean[set.getSizeX() + 1][set.getSizeY() + 1];
	for (Point current : set.getMatrix()) {
		if (current != null)
			gameBoard[current.x + 1][current.y + 1] = true;
	}
	for (int i = 1; i < gameBoard.length - 1; i++) {
		for (int j = 1; j < gameBoard[0].length - 1; j++) {
			try {
				pointBoardT0 = new boolean[3][3];
				// load points near instant T0
				pointBoardT0[0][0] = gameBoard[i - 1][j - 1];
				pointBoardT0[0][1] = gameBoard[i - 1][j];
				pointBoardT0[0][2] = gameBoard[i - 1][j + 1];
				pointBoardT0[1][0] = gameBoard[i][j - 1];
				// pointBoard[1][1] (me)
				pointBoardT0[1][2] = gameBoard[i][j + 1];
				pointBoardT0[2][0] = gameBoard[i + 1][j - 1];
				pointBoardT0[2][1] = gameBoard[i + 1][j];
				pointBoardT0[2][2] = gameBoard[i + 1][j + 1];

				/*
				 * If the point is evaluated "false" (white grid) then it is
				 * useless to create the res object type Future < point > as
				 * it will always be "false" and the grid does not change.
				 */
				int check = 0;
				for (boolean state[] : pointBoardT0) {
					for (boolean b : state) {
						if (b)
							check++;
					}
				}

				if (check != 0) {
				    /*
				     * I create the object of res futures; that is a
				     * "promise" of Point ("live" or. "Dead")
				     */
				    Future< point > res = executor.submit(new ComputeTask(
						    set, gameBoard[i][j], pointBoardT0, i, j,
						    stopFlag));
				    // The result I insert it in the list point T1 (at time T1)
                    // Like a monitor barrier
				    pointT1.add(res);
			    }
			} catch (Exception e) {
			e.printStackTrace();
		}
	}
}

We go down deep! At this point, the program creates an asynchronous task for each alive cell. This means that the concurrency is maximized.

Java
@Override
public Point call() {
	Point pointT1 = null;
	try {
		pointT1 = result.computePoint(pointT0, pointBoard, i, j);
		if (stopFlag.isSet()) {
			// log("task interrupted");
		} else {
			// log("task completed");
		}
	} catch (Exception ex) {
		ex.printStackTrace();
	}

	return pointT1;
}

Finally, computePoint calculates if the cell is alive or dead, implementing the rules of Game Of Life.

Java
public Point computePoint(boolean pointT0, boolean[][] pointBoard, int i, int j) {
	int surrounding = 0;
	if (pointBoard[0][0]) surrounding++;
	if (pointBoard[0][1]) surrounding++;
	if (pointBoard[0][2]) surrounding++;
	if (pointBoard[1][0]) surrounding++;
	// pointBoard[1][1]
	if (pointBoard[1][2]) surrounding++;
	if (pointBoard[2][0]) surrounding++;
	if (pointBoard[2][1]) surrounding++;
	if (pointBoard[2][2]) surrounding++;

	if (pointT0) {
		// A cell m [i, j] that in state s (t) is live and has
		// two or three neighbouring cells live,
		// in state s (t + 1) remains live ("survives")

		if ((surrounding == 2) || (surrounding == 3))
			return new Point(i - 1, j - 1);
	} else {
		// A cell m [i, j] that in state s (t) is dead and has
		// Three neighbouring cells live,
		// In state s (t + 1) become live
		if (surrounding == 3)
			return new Point(i - 1, j - 1);
	}
	/**
	 * 1) a cell m [i, j] that in state s (t) is live and has zero or more a
	 * neighbouring cell live (and other dead), in state s (t + 1) becomes
	 * Dead ("die of loneliness")
	 *
	 * 2) a cell m [i, j] that in state s (t) is live and has four or more
	 * neighbouring cells live in the state s (t + 1) becomes dead ("dies
	 * over-population ")
	 */
	return null;
}

Shutdown

Once the tasks are parallelized, and the concurrency is maximized, how should shutdown the algorithm?
We’ve seen how to create an Executor but not how to shut one down. Because an Executor processes tasks asynchronously, at any given time the state of previously submitted tasks is not immediately obvious.
Some may have completed, some may be currently running, and others may be queued awaiting execution.
In order to shutdown an application, there is a spectrum from:

  • graceful shutdown:
    • finish what you’ve started but don’t accept any new work
  • abrupt shutdown
    • turn off the power to the machine room and various points in between.

For this application, I have used:

  • monitor Flag: check with the user that the button start/stop presents in the View
  • graceful shutdown: initiates an orderly shutdown in which previously submitted tasks are executed, no new tasks will be accepted.
Java
public class Flag {
	
	private boolean isSet;
	
	public Flag(){
		isSet = false;
	}
	
	public synchronized void set(){
		isSet = true;
	}
	
	public synchronized boolean isSet(){
		return isSet;
	}
	
	public synchronized void reset(){
		isSet = false;
	}
}

Curiosity

The British mathematician John Conway, who is currently at Princeton University, invented the Game of Life in the late 1960s. He chose rules that produced the most unpredictable behaviour.
If you are curious to find out more about the Game of Life, the historical context, there's a recent interview of John Conway about the origins of the Game of Life.

Conclusion

Structuring applications around the Execution of tasks can simplify development and facilitate concurrency. The Executor framework permits you to decouple task submission from execution policy and supports a variety of execution policies.
To maximize the benefit of decomposing an application into tasks, you must identify sensible task boundaries, which you can do through the phases of analyzing the problem.
In some applications, the obvious task boundaries work well, whereas in others some analysis may be required to discover finer-grained exploitable parallelism, maybe like this case study.

Bibliography

  • http://www.theguardian.com/science/alexs-adventures-in-numberland/2014/dec/15/the-game-of-life-a-beginners-guide
  • https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life
  • Java Concurrency in Practice - Goetz et al., Addison Wesley, 2006

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Maximilian1986
Student University of Bologna
Italy Italy
Student at University of Bologna

Comments and Discussions

 
GeneralThoughts Pin
PIEBALDconsult30-Oct-15 17:21
professionalPIEBALDconsult30-Oct-15 17:21 
I don't think I've ever seen Life made so complicated. Thumbs Up | :thumbsup:
Bugmissing download file Pin
BillW3328-Oct-15 12:04
professionalBillW3328-Oct-15 12:04 
GeneralRe: missing download file Pin
BillW3329-Oct-15 5:15
professionalBillW3329-Oct-15 5:15 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.