Inspired by this post, I decided to try to implement my own Conway's Game of Life.
I started with a non-warping board:
/**
* Represents a single generation of a Conway's Game of Life.
*
*/
public class Generation {
protected static final int[][] SURROUNDING_CELL_POSITIONS = { { -1, -1 },
{ 0, -1 }, { 1, -1 }, { -1, 0 }, { 1, 0 }, { -1, 1 }, { 0, 1 },
{ 1, 1 } };
protected final Cell[][] board;
protected final int width;
protected final int length;
public Generation(Cell[][] board) {
this.board = copyOfBoard(board);
width = board.length;
length = board[0].length;
}
public Generation getNextGeneration() {
Cell[][] result = new Cell[width][length];
for (int i = 0; i < width; i++) {
for (int j = 0; j < length; j++) {
int count = getSurroundingCellCount(i, j);
result[i][j] = board[i][j].clone();
if (result[i][j].isAlive()) {
if (count > Cell.ALIVE_TO_DEAD_OVER
|| count < Cell.ALIVE_TO_DEAD_UNDER) {
result[i][j].dead();
}
} else if (count == 3) {
result[i][j].alive();
}
}
}
return new Generation(result);
}
protected int getSurroundingCellCount(int i, int j) {
int result = 0;
for (int[] add : SURROUNDING_CELL_POSITIONS) {
int iIndex = (i + add[0]);
int jIndex = (j + add[1]);
if (iIndex >= 0 && iIndex < width && jIndex >= 0 && jIndex < length
&& board[iIndex][jIndex].isAlive()) {
result++;
}
}
return result;
}
public Generation skipToNthGeneration(int n) {
Generation result = this;
for (int i = 0; i < n; i++) {
result = result.getNextGeneration();
}
return result;
}
public Cell[][] getBoard() {
return copyOfBoard(board);
}
protected Cell[][] copyOfBoard(Cell[][] board) {
int length = board.length;
int subArrayLength = board[0].length;
Cell[][] result = new Cell[length][subArrayLength];
for (int i = 0; i < length; i++) {
for (int j = 0; j < subArrayLength; j++) {
result[i][j] = board[i][j] == null ? new Cell() : board[i][j].clone();
}
}
return result;
}
}
I immediately noticed that getNextGeneration() requires O(n) space. Is this necessary? I feel like it isn't, but I am unsure of how to do so.
Then I created the WarpingGeneration class, to implement a warping Conway's Game of Life:
public final class WarpingGeneration extends Generation {
public WarpingGeneration(Cell[][] board) {
super(board);
}
@Override
public WarpingGeneration getNextGeneration() {
return new WarpingGeneration(super.getNextGeneration().board);
}
@Override
protected int getSurroundingCellCount(int i, int j) {
int result = 0;
for (int[] add : SURROUNDING_CELL_POSITIONS) {
int iIndex = (i + add[0]) % width;
int jIndex = (j + add[1]) % length;
if (iIndex < 0) {
iIndex += width;
}
if (jIndex < 0) {
jIndex += length;
}
if (board[iIndex][jIndex].isAlive()) {
result++;
}
}
return result;
}
}
Since it is very similar to the Generation class, I used inheritance to my advantage here.
And of course, nothing can be done without the Cell class:
public class Cell implements Cloneable {
public static final int DEAD_TO_ALIVE = 3;
public static final int ALIVE_TO_DEAD_OVER = 3;
public static final int ALIVE_TO_DEAD_UNDER = 2;
private boolean isAlive;
public Cell() {
dead();
}
public Cell(boolean isAlive) {
setAlive(isAlive);
}
public boolean isAlive() {
return this.isAlive;
}
public void setAlive(boolean isAlive) {
this.isAlive = isAlive;
}
public void alive() {
this.isAlive = true;
}
public void dead() {
this.isAlive = false;
}
public void toggleLife() {
this.isAlive = !this.isAlive;
}
@Override
public Cell clone() {
return new Cell(isAlive);
}
}
Usage:
public static void main(String[] args) {
Cell[][] cells = new Cell[10][10];
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
cells[i][j] = new Cell(false);
}
}
cells[0][1].alive();
cells[1][2].alive();
cells[2][2].alive();
cells[2][1].alive();
cells[2][0].alive();
Generation g = new WarpingGeneration(cells);
printGen(g);
for (int i = 0; i < 100; i++) {
g = g.getNextGeneration();
printGen(g);
}
}
private static void printGen(Generation g) {
Cell[][] cellss = g.getBoard();
for (Cell[] cells : cellss) {
for (Cell cell : cells) {
System.out.print((cell.isAlive() ? '*' : ' ') + " ");
}
System.out.println();
}
}
This will print 100 generations of the "Walker".
Concerns:
- Is it possible to reduce space complexity from
O(n)? If so, how? - Is there a faster way to do
skipToNthGeneration()? - And as usual, anything else?
skipToNthGeneration()does seem unnecessarily inefficient. Why iterating from 0 tonevery time? Why not defining the starting indices ingetNextGeneration()on account of thisnvalue? This also brings the exact motivation behind the current implementation of the loops ingetNextGeneration(); it does seem improvable. Although as said, sharing the basic ideas about what you are trying to accomplish in each part would be definitively very helpful to motivate some people (at least, me :)) to take a deeper look at the code. \$\endgroup\$