Conway's game of life with each cell being a thread
Hey guys, So like the title says, I have to make a program that implements threading in Conway's game of life, where each dead or alive cell is a thread. My first goal was to simply get the game working, which i did (pretty fun challenge) So i can print the 20x20 grid, and each cell is initialized as a random number 1 or 0, where 1 is alive, and 0 is dead. Now, I've been watching videos on how to use threading, but i'm still unsure as to how i'm supposed to implement this for each cell... I have 3 classes, Main, Cell, and CellRules my Cell class looks like:
public class Cell implements Runnable
{
public static int myCount = 0;
private String name;
private int neighbors;
private int alive; // 0 is dead; 1 is alive.
Random rand = new Random();
public Cell (String nm)
{
name = nm;
myCount = rand.nextInt(999);
neighbors = 0;
// 2 because it is exclusive
this.setLife(rand.nextInt(2));
}
public void run()
{
while(Cell.myCount <= 10){
try
{
System.out.println("Expl Thread: " + (++Cell.myCount));
Thread.sleep(100);
} catch (InterruptedException iex)
{
System.out.println("Exception in thread:
"+iex.getMessage());
}
}
}
There are a few other things in there, that are really for simplicity, i don't believe they are necessary to be shown, and same thing for the Cell Rules class. Cell Rules looks like:
/**
* This function simply gets the number of neighbors for each cell, and saves the future generation
* based on the number neighbors from arr to future array.
*
* @param arr Arr that will be checked for neighbors
* @param futureGen This array will keep track of the future generation
* @param columns numbers of columns
* @param rows numbers of rows
*/
public void checkN(Cell [][] arr, Cell [][] futureGen, int columns, int rows)
{
for (int x = 0; x < rows; x++)
{
for (int y = 0; y < columns; y++)
{
arr[x][y].setNeighbors(0);
// Upper left corner
if (x == 0 && y == 0)
for (int i = 0; i <= 1; i++)
for (int j = 0; j <= 1; j++)
if (arr[x + i][y + j].getLife() == 1)
arr[x][y].addNeighbor();
// Upper margin checks
if ((x == 0) && (y != 0 && y <= columns - 2))
for(int i = 0; i <= 1; i++)
for(int j = -1; j <= 1; j++)
if (arr[x + i][y + j].getLife() == 1)
arr[x][y].addNeighbor();
// Upper right corner
if ((x == 0) && (y == columns - 1))
for(int i = 0; i <= 1; i++)
for(int j = -1; j <= 0; j++)
if (arr[x + i][y + j].getLife() == 1)
arr[x][y].addNeighbor();
// Left margin checks
if ((y == 0) && (x != 0 && x <= rows - 2))
for (int i = -1; i <= 1; i++)
for (int j = 0; j <= 1; j++)
if (arr[x + i][y + j].getLife() == 1)
arr[x][y].addNeighbor();
// Lower left corner
if ((x == rows - 1) && y == 0)
for (int i = -1; i <= 0; i++)
for (int j = 0; j <= 1; j++)
if (arr[x + i][y + j].getLife() == 1)
arr[x][y].addNeighbor();
// Bottom margin checks
if ((x == rows - 1) && (y != 0 && y <= columns - 2 ))
for (int i = -1; i <= 0; i++)
for (int j = -1; j <= 1; j++)
if (arr[x + i][y + j].getLife() == 1)
arr[x][y].addNeighbor();
// Lower right corner
if ((x == rows - 1) && (y == columns - 1))
for (int i = -1; i <= 0; i++)
for (int j = -1; j <= 0; j++)
if (arr[x + i][y + j].getLife() == 1)
arr[x][y].addNeighbor();
// Right margin checks
if ((y == columns - 1) && (x != 0 && x <= rows - 2))
for (int i = -1; i <= 1; i++)
for (int j = -1; j <= 0; j++)
if (arr[x + i][y + j].getLife() == 1)
arr[x][y].addNeighbor();
// Middle area checks ( can check all around now )!
if ((x > 0) && (x < rows - 1) && (y > 0) && (y < columns - 1) )
for (int i = -1; i <= 1; i++)
for (int j = -1; j <= 1; j++)
if (arr[x + i][y + j].getLife() == 1)
arr[x][y].addNeighbor();
// Do not add yourself!
if (arr[x][y].getLife() == 1)
arr[x][y].subNeighbor();
// Get the new generation through the neighbors
if ((arr[x][y].getLife() == 1) &&
(arr[x][y].getNeighbors() < 2))
futureGen[x][y].setLife(0);
else if ((arr[x][y].getLife() == 1) &&
(arr[x][y].getNeighbors() > 3))
futureGen[x][y].setLife(0);
else if ((arr[x][y].getLife() == 0) &&
(arr[x][y].getNeighbors() == 3))
futureGen[x][y].setLife(1);
else
futureGen[x][y].setLife(arr[x][y].getLife());
}
}
}
I'm not sure where the implementation of the threads really goes, Any guidance or explanations would be greatly appreciated! Have a nice day :)
First of all, your checkN function is way overengineered. Let's simplify it a bit.
/**
* This function simply gets the number of neighbors for each cell, and saves the future generation
* based on the number neighbors from arr to future array.
*
* @param arr Arr that will be checked for neighbors
* @param futureGen This array will keep track of the future generation
* @param columns numbers of columns
* @param rows numbers of rows
*/
public void checkN(Cell [][] arr, Cell [][] futureGen, int columns, int rows) {
for (int x = 0; x < rows; x++) {
for (int y = 0; y < columns; y++) {
arr[x][y].setNeighbors(0);
for(int i = -1; i <= 1; i++) {
for(int j = -1; j <= 1; j++) {
if(i == 0 && j == 0) continue; //don't check self
if(x + i < 0 || x + i >= rows) continue; //bounds checking
if(y + j < 0 || y + j >= columns) continue; //bounds checking
if (arr[x + i][y + j].getLife() == 1)
arr[x][y].addNeighbor();
}
}
// Get the new generation through the neighbors
if(arr[x][y].getLife() == 1 &&
(arr[x][y].getNeighbors() == 2 || arr[x][y].getNeighbors() == 3))
futureGen[x][y].setLife(1);
else if(arr[x][y].getLife() == 0 && arr[x][y].getNeighbors() == 3)
futureGen[x][y].setLife(1);
else
futureGen[x][y].setLife(0);
}
}
}
We can then refactor this into a few extra functions:
private void countNeighbors(Cell[][] arr, int row, int column, int rows, int columns) {
Cell c = arr[row][column];
c.setNeighbors(0);
for(int i = -1; i <= 1; i++) {
for(int j = -1; j <= 1; j++) {
if(i == 0 && j == 0) continue; //don't check self
if(row + i < 0 || row + i >= rows) continue; //bounds checking
if(column + j < 0 || column + j >= columns) continue; //bounds checking
if (arr[row + i][column + j].getLife() == 1)
c.addNeighbor();
}
}
}
private void evaluateNeighbors(Cell oldCell, Cell newCell) {
if (oldCell.getLife() == 1 &&
(oldCell.getNeighbors() == 2 || oldCell.getNeighbors() == 3))
newCell.setLife(1);
else if(oldCell.getLife() == 0 && oldCell.getNeighbors() == 3)
newCell.setLife(1);
else
newCell.setLife(0);
}
public void checkN(Cell [][] arr, Cell [][] futureGen, int columns, int rows) {
for (int row = 0; row < rows; row++) {
for (int column = 0; column < columns; column++) {
countNeighbors(arr, row, column, rows, columns);
evaluateNeighbors(arr[row][column], futureGen[row][column]);
}
}
}
The reason we're refactoring like this will become apparent in a moment.
So back to the original question: where do we insert threading into this program?
You need to make a decision on how you want to split up threads. Based on your question, it sounds like you want to launch an independent thread for each cell that gets evaluated. While there's not any problems with this approach in theory, this really doesn't guarantee any significant speedup, simply because at thousands of cells (which you will quickly hit for even modest sizes of grids) you'll be creating thousands of threads, and only mega-servers will have enough threads to take advantage of it.
Nonetheless, if that's what you want to do, the code (Java 8 required) looks like this:
public void checkN(Cell [][] arr, Cell [][] futureGen, int columns, int rows)
{
ArrayList<Thread> threads = new ArrayList<>();
for (int row = 0; row < rows; row++) {
for (int column = 0; column < columns; column++) {
Integer thread_local_row = row;
Integer thread_local_column = column;
Thread t = new Thread(() -> {
countNeighbors(arr, thread_local_row, thread_local_column, rows, columns);
evaluateNeighbors(arr[thread_local_row][thread_local_column], futureGen[thread_local_row][thread_local_column]);
});
t.start();
threads.add(t);
}
}
for(Thread t : threads)
t.join();
}
The end result is that each cell will receive its own dedicated thread. Note how little we had to change once the code was refactored.
Like I mentioned, however, this is overkill in terms of the number of threads we're creating. So an alternative is to create a new thread for each row.
public void checkN(Cell [][] arr, Cell [][] futureGen, int columns, int rows)
{
ArrayList<Thread> threads = new ArrayList<>();
for (int row = 0; row < rows; row++) {
Integer thread_local_row = row;
Thread t = new Thread(() -> {
for (int column = 0; column < columns; column++) {
countNeighbors(arr, thread_local_row, column, rows, columns);
evaluateNeighbors(arr[thread_local_row][column], futureGen[thread_local_row][column]);
}
});
t.start();
threads.add(t);
}
for(Thread t : threads)
t.join();
}
This is better, but of course, it once again could become overkill if you have a lopsided grid that has lots of rows but very few columns.
So a third option is to make the number of threads constant, and scale the workload per thread to fit the number of threads.
public void checkN(Cell [][] arr, Cell [][] futureGen, int columns, int rows)
{
ArrayList<Thread> threads = new ArrayList<>();
final int NUM_OF_THREADS = 8; //Or can be passed as an argument
for(int tid = 0; tid < NUM_OF_THREADS; tid++) {
Integer thread_local_row_start = tid * rows / NUM_OF_THREADS;
Integer thread_local_row_end = (tid + 1) * rows / NUM_OF_THREADS;
Thread t = new Thread(() -> {
for (int row = thread_local_row_start; row < thread_local_row_end; row++) {
for (int column = 0; column < columns; column++) {
countNeighbors(arr, row, column, rows, columns);
evaluateNeighbors(arr[row][column], futureGen[row][column]);
}
}
});
t.start();
threads.add(t);
}
for(Thread t : threads)
t.join();
}
This option tends to be the most performant, since you can set NUM_OF_THREADS to be equal to the number of processor cores in your machine, or whatever value you find in testing to yield ideal performance.
You can use any of these techniques, or else come up with a different technique to split up the threads (for example, maybe an algorithm that perfectly splits the workloads, rather than rounding to nearest-row-counts?). The important part is simply keeping your code organized well enough to facilitate your workload splitting mechanism.
If you're limited to Java 7, all of the code written can still be used, but the lambda structure needs to be replaced with an Anonymous Inner Class, and any variables that need to be used in the thread body need to be made final:
public void checkN(final Cell [][] arr, final Cell [][] futureGen, final int columns, final int rows)
{
ArrayList<Thread> threads = new ArrayList<>();
for (int row = 0; row < rows; row++) {
for (int column = 0; column < columns; column++) {
final Integer thread_local_row = row;
final Integer thread_local_column = column;
Thread t = new Thread(new Runnable() {
public void run() {
countNeighbors(arr, thread_local_row, thread_local_column, rows, columns);
evaluateNeighbors(arr[thread_local_row][thread_local_column], futureGen[thread_local_row][thread_local_column]);
}
});
t.start();
threads.add(t);
}
}
for(Thread t : threads)
t.join();
}