Allocate a rectangular Java array:Java initializes every new boolean array element to
java
boolean[][] board = new boolean[1000][1000];false, so all cells are initially dead without a filling loop. This allocates a top-level array of row references and a distinct boolean array for every row.Count only the existing neighbours, excluding the center, then apply the Conway Game of Life transition:The short-circuit bounds test occurs before indexing a neighbour. Out-of-range cells therefore contribute zero, including at corners, and no opposite-edge wrapping occurs. The center is explicitly excluded. Birth requires three neighbours; survival requires two or three. The method accepts a nonempty rectangular board and a valid cell index and does not change the old Java array.
java
static boolean nextCell(boolean[][] old, int i, int j) {
int height = old.length;
int width = old[0].length;
int neighbours = 0;
for (int di = -1; di <= 1; di++) {
for (int dj = -1; dj <= 1; dj++) {
if (di == 0 && dj == 0) continue;
int r = i + di;
int c = j + dj;
if (r >= 0 && r < height && c >= 0 && c < width
&& old[r][c]) {
neighbours++;
}
}
}
return neighbours == 3 || (old[i][j] && neighbours == 2);
}Use disjoint Java arrays for the old and new generations:Every decision reads only
java
static void step(boolean[][] old, boolean[][] next) {
for (int i = 0; i < old.length; i++) {
for (int j = 0; j < old[i].length; j++) {
next[i][j] = nextCell(old, i, j);
}
}
}old, so all cells undergo the simultaneous Conway Game of Life transition. The second board must have the same dimensions and share no row arrays with the first. Afterwards swap their references for the following step.Writing each new cell immediately into the input board would expose a mixture of old and new states to later neighbour counts. The result would depend on the traversal order and would no longer be the specified simultaneous automaton. For example, put the three live cells at on an otherwise dead board. The simultaneous result is the vertical triple . During a naive row-major overwrite, becomes live first. The next cell now sees that new cell as well as the old cells , so it is incorrectly born with three counted neighbours. This explicitly exhibits the mixture of generations. A second generation array, or explicit preservation of overwritten old information, is essential.
A one-row in-place Life update needs only one saved row plus a few running sums. Before processing row , When column is processed,
above[j] stores the old row , and all rows and below are still old. Let a column sum be the number of old live cells in that column in rows . The three adjacent column sums, minus the center, give the required neighbour count.java
static int columnSum(boolean[][] board, boolean[] above,
int i, int j) {
int total = above[j] ? 1 : 0;
if (board[i][j]) total++;
if (i + 1 < board.length && board[i + 1][j]) total++;
return total;
}
static void stepInPlace(boolean[][] board) {
int width = board[0].length;
boolean[] above = new boolean[width];
for (int i = 0; i < board.length; i++) {
int left = 0;
int middle = columnSum(board, above, i, 0);
for (int j = 0; j < width; j++) {
int right = j + 1 < width
? columnSum(board, above, i, j + 1) : 0;
boolean oldCenter = board[i][j];
int neighbours = left + middle + right
- (oldCenter ? 1 : 0);
boolean newCenter = neighbours == 3
|| (oldCenter && neighbours == 2);
above[j] = oldCenter;
board[i][j] = newCenter;
left = middle;
middle = right;
}
}
}left and middle were computed before their cells were overwritten. right is computed now from untouched column , including its untouched above[j+1] entry. Thus all three sums describe old cells. Saving oldCenter into above[j] preserves the old current row for the next row's processing; no later computation in the current row rereads that changed entry, because its old contribution is already in the running sums. This proves the inner-loop invariant and then the row invariant by induction.Initially
above is all false, representing the dead exterior above the board. The missing left and right columns contribute zero; the bottom row omits any row below it. Hence all four boundaries follow the required convention. The update takes time and one -element auxiliary boolean vector, which is exactly a 1000-element vector for the requested board. It uses one board array throughout and does not silently keep a second board or two auxiliary rows.Choose bit zero of each integer to represent the leftmost cell in its group of 32 columns. Then use a quotient to choose the word and a remainder to choose the bit:For valid ,
java
static boolean getBit(int[][] board, int i, int j) {
return ((board[i][j >>> 5] >>> (j & 31)) & 1) != 0;
}j >>> 5 is and ranges from zero to 31. The bit mask j & 31 is the offset . The logical right bit shift brings the desired bit to position zero; the final mask selects only that bit. Even bit 31 of a negative stored word is extracted correctly, because >>> inserts zeros. A different convention, with the leftmost cell in the most significant bit, would instead shift by 31 - (j & 31) and must be used consistently. Articles by others on the same topic
There are currently no matching articles.