Hey ya’ll. So I have implemented Conway’s Game of Life. I have since optimized it as much as I can… but I still want faster. I am well aware of hashlife, but I don’t understand it. Until I can figure hashlife out, I would like to try to improve my current implementation as much as possible.
Here’s my code:
public static class Grid {
private static final boolean[] LOOKUP_TABLE = new boolean[32];
private static final int STATE_BIT = 4;
static {
for(byte i = 0; i < Grid.LOOKUP_TABLE.length; i++) {
final boolean live = i < 16;
final byte index = setBit(i, STATE_BIT, live);
final int neighbors = i >= 16 ? i - 16 : i;
Grid.LOOKUP_TABLE[index] = live && neighbors == 2 || neighbors == 3;
}
}
private final int width;
private final int height;
private byte[] grid;
public Grid(final int width, final int height) {
this.width = width;
this.height = height;
this.grid = new byte[this.width * this.width];
}
public int getWidth() {
return this.width;
}
public int getHeight() {
return this.height;
}
public boolean get(final int x, final int y) {
return getBit(this.grid[this.encode(x, y)], STATE_BIT);
}
public void set(final int x, final int y, final boolean state) {
this.set(this.grid, x, y, state);
}
public void cycle() {
byte[] newGrid = new byte[this.width * this.height];
for(int i = 0; i < this.width; i++) {
for(int j = 0; j < this.height; j++) {
final int idx = this.encode(i, j);
final int value = this.grid[idx];
if(value != 0)
this.set(newGrid, i, j, LOOKUP_TABLE[value]);
}
}
this.grid = newGrid;
}
public void clear() {
for(int x = 0; x < this.grid.length; x++) {
this.grid[x] = 0;
}
}
private void set(final byte[] grid, final int x, final int y, final boolean state) {
final int idx = this.encode(x, y);
final boolean oldState = getBit(grid[idx], STATE_BIT);
if(oldState == state) return;
grid[idx] = setBit(grid[idx], STATE_BIT, state);
for(int i = x - 1; i <= x + 1; i++) {
for(int j = y - 1; j <= y + 1; j++) {
if(i == x && j == y) continue;
int px = i;
int py = j;
// wrapping around - I prefer wrapping to infinite world/edged world
if(i < 0)
px += this.width;
if(j < 0)
py += this.height;
if(i >= this.width)
px -= this.width;
if(j >= this.height)
py -= this.height;
final int k = this.encode(px, py);
final byte pixel = grid[k];
final byte neighbors = setBit(pixel, STATE_BIT, false);
final boolean currentState = getBit(pixel, STATE_BIT);
grid[k] = setBit((byte) (neighbors + (state ? 1 : -1)), STATE_BIT, currentState);
}
}
}
private int encode(final int x, final int y) {
return y * this.width + x;
}
private static byte setBit(final byte value, final int bit, final boolean state) {
if(state)
return (byte) (value | (1 << bit));
else
return (byte) (value & ~(1 << bit));
}
private static boolean getBit(final byte value, final int bit) {
return (value & (1 << bit)) != 0;
}
}
I suppose I could manually inline functions like encode, getBit, and setBit, but I suspect the JVM does that anyway (if not the Java compiler). So, how else could I improve this? Can I make it more cache friendly perhaps?
Let me know what you think of my current implementation and how I can improve it. Thanks!
Uh… The first 4 bits are storing how many neighbors a cell has, the next one is the cell’s state. Then I can just zip through them with the LUT…
I was just pointing out that there are ways to do it that don’t involve conditionals. Anyway, swapping references at the end of the cycle as you mentioned in your last post is probably how I’d do it.