Game of Life

[Paul Morrison]

My implementation of the Game of Life stores the cells in the type: byte[][]
The sides of the world must *wrap* around, ie a cell on the very right of
the world is actually the neighbour of the cell on the very left of the
world.

When wanting to insert a glider into the word the following code is used:

public void glider (int i, int j) throws NotInLifeException {
cell[j] = Cell.ALIVE;
cell[j+2] = Cell.ALIVE;
cell[i+1][j+1] = Cell.ALIVE;
cell[i+1][j+2] = Cell.ALIVE;
cell[i+2][j+1] = Cell.ALIVE;
}

ie:

...X .X..
.....XX..
.....X.....

The problem is when the glider gets to the edge of the world. In order to
check that the glider will stay in the world I have used the following code:

public void checkBounds (int i, int j) {
while (i < 0) {
i += width;
}
while (i > width) {
i -= width;
}
while (j < 0) {
j += depth;
}
while (j > depth) {
j -= depth;
}
}

The problem I am having is incorporating the checkBounds method into the
glider method. Any help would be appreciated.

Paul Morrison

 

[Josef Garvi]

Two suggestions:

1) change CheckBounds into two functions.
Something like:

public int checkBoundsCol (int i) {
while (i < 0) {
i += width;
}
while (i >= width) {
i -= width;
}
return i;
}

and

public int checkBoundsRow (int j) {
while (j < 0) {
j += height
}
while (j >= height) {
j -= height;
}
return j;
}

Please note that you should check "(i >= width)" rather than "(i > width)"
because the array is 0-based, so the column of value width falls outside of
your grid. Same thing applies to rows.

Then, in your glider method, wrap the variables i and j into the
checkBoundsXXX functions as in:

cell[checkBoundsCol(i)][checkBoundsRow(j)] = Cell.ALIVE;



2) Replace your byte array by an array of Cell objects (Cell being a class
that you create). Upon creating the grid, you can link each cell to it's
neighbours. Then you could do something like:

myCell.getWest().setAlive(true);



--
Josef Garvi

"Reversing desertification through drought tolerant trees"
http://www.eden-foundation.org/

new income - better environment - more food - less poverty

 

[Paul Morrison]

Brilliant! Thanks, went for the first option as I have to stick to using the
byte array to store cells as that is part of the specification!

Thank you again.

Paul

 

[Michael Borgwardt]

Um... have neither of you ever heard of the modulus operator "%" ??

 

[Tim Ward]

My implementation of the Game of Life stores the cells in the type: byte[][]
The sides of the world must *wrap* around, ie a cell on the very right of
the world is actually the neighbour of the cell on the very left of the
world.

When I was a student this one was an exercise in sparse arrays ...
wraparound was not allowed, and the pattern had to be allowed to grow to
around 4,000,000 x 4,000,000 in size (certainly one had to cope with as many
generations of a glider gun as one could afford the (mainframe) CPU cycles
for), using only a few hundred k of memory. So, no byte[][] equivalent in
whatever language one chose (I think I chose to do it in BCPL).

 

[Paul Morrison]

Um... have neither of you ever heard of the modulus operator "%" ??

Do you mean if i used

public int checkBoundsCol (int i) {
while (i < 0) {
i = i % width;
}
return i;
}

instead of

public int checkBoundsCol (int i) {
while (i < 0) {
i += width;
}
while (i >= width) {
i -= width;
}
return i;
}

Paul

 

[Paul Morrison]

public int checkBoundsCol (int i) {

while (i < 0) {
i = i % width;
}
return i;
}

or even

public int checkBoundsCol (int i) {
i = i % width;
}

That would probably be more efficient!

Paul

 

[Michael Borgwardt]

Do you mean if i used

public int checkBoundsCol (int i) {
while (i < 0) {
i = i % width;
}
return i;
}

instead of

public int checkBoundsCol (int i) {
while (i < 0) {
i += width;
}
while (i >= width) {
i -= width;
}
return i;
}

No, more like


public int checkBoundsCol (int i) {
return (i + width)%width;
}

which is so simple that you could drop the method completely
and inline it, i.e.

cell[(i + width)%width][(j + height)%height] = Cell.ALIVE

 

[Josef Garvi]

Do you mean if i used

public int checkBoundsCol (int i) {
while (i < 0) {
i = i % width;

No, he means you should just use...

public int checkBoundsCol (int i) {
return i % width;
}

....without any while loop.

--
Josef Garvi

"Reversing desertification through drought tolerant trees"
http://www.eden-foundation.org/

new income - better environment - more food - less poverty

 

[Michael Borgwardt]

or even

public int checkBoundsCol (int i) {
i = i % width;
}

That would probably be more efficient!

Unlike the first one, it would not run into an
endless loop with negative i, but still return
negative results.

 

[Gregory A. Swarthout]

or even

public int checkBoundsCol (int i) {
i = i % width;
}

That would probably be more efficient!

Paul

You do realize this only takes into account wrapping from right to
left and not vice-versa, right? If you pass in a negative, this won't
turn it into a positive.

 

[Filip Larsen]

Michael Borgwardt wrote

public int checkBoundsCol (int i) {
return (i + width)%width;
}

which is so simple that you could drop the method completely
and inline it, i.e.

cell[(i + width)%width][(j + height)%height] = Cell.ALIVE

Inlining that every time you need to access a cell is not a good idea. I
would probably use a Cell enumeration on the interface and have two
methods to encapsulate the access:

public class CellWorld {

final private int width;
final private int height;
final private Cell[][] cell;

...

final public int width() { return width; }
final public int height() { return height; }

public Cell get(int x, int y) {
return cell[(x+width)%width][(y+height)%height];
}

public void set(int x, int y, Cell c) {
cell[(x+width)%width][(y+height)%height] = c;
}

}

Then most other things can be expressed using those, like pasting one
pattern into another:

public void set(int x, int y, CellWorld w) {
for (int i = 0; i < w.width(); i++) {
for (int j = 0; j < w.height(); j++) {
set(x+i,y+j,w.get(i,j));
}
}
}

which then can be used like

CellWorld glider = ...
CellWorld myWorld = ...
myWorld.set(x,y,glider);


And if the internal storage needs to more efficient than Cell[][], then
only the first set and get needs to be changed, for instance to map a
Cell into a bit in a sparse matrix (as someone mentioned).



Regards,