9
\$\begingroup\$

I have designed Conway's Game of Life in Java, the solution follows Object Oriented design and paradigm, please review and let me know the feedback

Class Cell

Cell has one property alive and behavior to update alive status

public class Cell {
    private boolean alive;

    public Cell( boolean alive) {
        this.alive = alive;
    }

    public void updateStatus(int aliveNeighboursCount) {
        if (alive && aliveNeighboursCount > 3) {
            alive = false;
        } else if (alive && aliveNeighboursCount < 2) {
            alive = false;
        } else if (aliveNeighboursCount == 3 && !alive) {
            alive = true;
        }
    }

    public boolean isAlive() {
        return this.alive;
    }
}

Class Grid

getAliveNeighboursCount method finds the alive neighbor of every cell and returns the count

nextCycle creates new cells with their alive status based neighbours count and replaces the current cells of the Grid

public class Grid {
    private Cell[][] cells;

    public Grid(int size, Randomizer randomizer) {
        this.cells = randomizer.loadCells(size);
    }


    private boolean isOutOfBound(int maxSize, int i, int j) {
        return (i < 0 || i == maxSize) || (j < 0 || j == maxSize);
    }


    int getAliveNeighboursCount(int xPos, int yPos) {
        int aliveNeighboursCount = 0;
        for (int i = xPos - 1; i <= xPos + 1; i++) {
            for (int j = yPos - 1; j <= yPos + 1; j++) {
                if (isOutOfBound(cells.length, i, j) || (i == xPos && j == yPos)) {
                    continue;
                }
                aliveNeighboursCount += cells[i][j].isAlive() ? 1 : 0;
            }
        }
        return aliveNeighboursCount;
    }


    public void nextCycle() {
        Cell[][] newCells = new Cell[this.cells.length][this.cells[0].length];
        for (int i = 0; i < newCells.length; i++) {
            for (int j = 0; j < newCells[0].length; j++) {
                Cell cell = new Cell(false);
                cell.updateStatus(getAliveNeighboursCount(i, j));
                newCells[i][j] = cell;
            }
        }
        this.cells = newCells;
    }

    @Override
    public String toString() {
        StringBuilder gridString = new StringBuilder();
        for (int i = 0; i < cells.length; i++) {
            for (int j = 0; j < cells[0].length; j++) {
                gridString.append(cells[i][j].isAlive() ? "*\t" : "-\t");
            }
            gridString.append("\n");
        }
        return gridString.toString();
    }

}

Class Randomizer

Grid takes Randomizer object to randomize cells based on the biased random number

import java.util.Random;

public class Randomizer {

    private final int aliveCellsForEveryTenCell;

    public Randomizer(int aliveCellsForEveryTenCell) {
        this.aliveCellsForEveryTenCell = aliveCellsForEveryTenCell;
    }

    private boolean getNext() {
        return new Random().nextInt(10) <= aliveCellsForEveryTenCell;
    }

    public Cell[][] loadCells(int size) {
        Cell[][] cells = new Cell[size][size];
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < cells[0].length; j++) {
                cells[i][j] = new Cell( getNext());
            }
        }
        return cells;
    }
}

Class Action

This class is to execute the Code

public class Action {
    public static void main(String[] args) throws InterruptedException {
        Randomizer randomizer = new Randomizer(4);
        Grid grid = new Grid(25, randomizer);
        System.out.println(grid);

        for (int i = 0; i < 10; i++) {
            Thread.sleep(1000);
            grid.nextCycle();
            System.out.println(grid);
        }
    }
}
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Possible bug: I believe cell.updateStatus is ever only called on a dead cell (new Cell(false)). \$\endgroup\$
    – RoToRa
    Apr 4 at 9:54
  • \$\begingroup\$ Your "updateStatus" method does not need to test the "alive" flag status. If there are more than 3 live neighbours, the status is dead whether it starts dead or not. Similarly for less than 2. And if there are 3 live neighbours, its status next time is always alive, whether it started dead or not. \$\endgroup\$ Apr 7 at 12:20

6 Answers 6

16
\$\begingroup\$

It's hard to judge a design when there is no information about what you want from it. If you wanted classes and methods, well you succeeded, but that's about it. But if you, for example, wanted extensibility and robustness, then it's a whole different thing. You added the "interview-questions" tag. Can you tell us what your interviewer was looking for?

Grid

For me the Grid class is supposed to encapsulate and protect the array. That is broken in your design as the array is created by Randomizer. There is very little point in trying to verify the bounds of the array in Grid because Grid doesn't even know the size of the array it has. There is no guarantee that Randomizer provides what it is asked to provide because a programmer can subclass Randomizer and return data that is not compatible to what Grid expects. You could add error checking to ensure the array returned by Randomizer has correct dimensions, but that's "treating the symptoms, not the disease." A better approach would be for Grid to initialize the array itself and ask Randomizer to place the live/dead value to the cells created by Grid using setter methods.

Randomizer

Conway's game of life is about creating seeds that provide interesting generations. You should define the Randomizer as an interface, called something like Seeder, and make Grid accept the interface instead of some concrete implementation. Then you can implement different seeders, like your RandomSeeder.

Cell

It has no meaning outside the Grid class. It seems to only exist as a container for the game rules, and even the rules have been split between the Grid and the Cell (grid being responsible for counting the neighbors and cell making the decision based on that count). Maybe it exists only for the sake of having a class?

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I often use abstractions like the Cell class, but I would probably make them private to Grid, if nothing about cell is needed in any other context: that way, its merely an implementation detail of Grid (a valid one IMO), and not part of a searchable api \$\endgroup\$ Apr 6 at 6:16
  • \$\begingroup\$ @Robominister I thought that it could have a purpose as an extension point, if you could provide a "CellFactory" for the grid and use it to construct the game with cells that implement a different alive/dead-rules. But that would require other major changes too and even then it might just be more practical to implement the game logic, that creates the next generation, as a replaceable component itself. \$\endgroup\$ Apr 6 at 11:23
14
\$\begingroup\$

Thanks for sharing your code!

OOP doesn't mean to "split up" code into random classes.

The ultimate goal of this is to reduce code duplication, improve readability and support reuse as well as extending the code.

Doing OOP means that you follow certain principles which are (amongst others):

  • information hiding / encapsulation
  • single responsibility
  • separation of concerns
  • KISS (Keep it simple (and) stupid.)
  • DRY (Don't repeat yourself.)
  • "Tell! Don't ask."
  • Law of demeter ("Don't talk to strangers!")
  • replace branching by polymorphism

IMHO Your approach fails OOP principles in several ways.

Arrays are no good OO data structures.

In an OO approach I would let every cell know its neighbors so I'd get some kind of mesh data structure. This would completely disconnect the games behavior (act on the neighbors states) from the topology. It would also remove the need for border checks at runtime, since there wouldn't bee any borders, just neighbors...

The game topology could be modified to be a 2 dimensional hexagon pattern or even a 4 dimensional structure by just giving each cell a different set of neighbors.

Classes hold differing behavior

In you approach the state of the cell is just a property of the cell class.
In fact a dead cell behaves differently then a living cell. This is a strong indication that two classes might be appropriate.

When we look a little closer, then we see that only the states behave differently while the cell only provides infrastructure (holding a collection of neighbors, returning the current state,...) so that the cell states should better be classes (sharing the same interface) then just boolean.

When moving the "next state calculation" into state classes you could even change the rules by just exchanging this state classes (sharing the same interface).

OO enables performance optimizations

The most important rule of performance optimization is: The fastest way to do something is not doing it.

When speaking of "Conways Game of Live" we should avoid calculating state changes for cells that will not change their state (which is the vast majority an a CGoL Game field).

A cell can only change its state in the next round, when one of its neighbors changed state in the current round.
Since each cell knows both, its neighbors and (if so) that its own state changed in the current round, it can add its neighbors to a collection of cells that need recalculation in the next round (hopefully a java.util.Set which eliminates double entries for us). This way we can run the next state calculation exclusively on the cells that might change their state and prevent us from iterating over all cells on the board.

\$\endgroup\$
5
  • 2
    \$\begingroup\$ Your idea of having Cells store their neighbors is a good one, even if it goes in a very different direction than my suggestion of getting rid of the Cells altogether. Which one's better really depends on what kind of flexibility the OP wants from their code. +1 anyway. \$\endgroup\$ Apr 4 at 22:32
  • 8
    \$\begingroup\$ Surely the real performance optimizations are prevented by the use of OOP for cells. \$\endgroup\$
    – user253751
    Apr 5 at 9:38
  • 3
    \$\begingroup\$ @user253751: Indeed, if you want a really fast Life implementation, you want to process multiple cells at once, e.g. with SIMD (lemire.me/blog/2018/07/18/… shows a factor of 25 speedup for AVX2 intrinsics over a scalar C implementation). Or by representing each one as a single bit, so you can pack 32 into an int and use bitwise booleans between rows (and shift within a row). This definitely means having contiguous cells contiguous in memory, so adjacency is built-in, not by following references that take 16x the data size. \$\endgroup\$ Apr 5 at 10:20
  • 1
    \$\begingroup\$ This answer's ideas are interesting, but probably not good for performance except on a very sparse grid where few cells change, using that Set idea. \$\endgroup\$ Apr 5 at 10:22
  • 1
    \$\begingroup\$ As far as I understood the main objective of the TO was to learn OOP. If the main target would be to write a fast, performant CGoL-Implementation I would suggest not using Java in the first place. \$\endgroup\$ Apr 6 at 11:55
10
\$\begingroup\$

As TorbenPutkonen notes, it's hard to judge your design without knowing what your goals are.

That said, in a practical GoL implementation (aiming at reasonable memory and CPU efficiency) your outward-facing API would typically consist primarily of the Grid class (or interface), with methods like:

public interface Grid {
  boolean getState(int x, int y);
  void setState(int x, int y, boolean state);
  int getLiveCellCount();
  Rectangle2D getGridBounds();
  Rectangle2D getLivePatternBounds();
  void nextCycle();
}

(You could call the getState method something like isAlive instead, and arguably that would be more natural if you're using booleans to represent the two possible cell states. But you might want to later change your code to support CA rules with more than two states, in which case you can't use booleans any more. Of course you could also just rename the method if and when you do that.)

The Grid implementation would then encapsulate the storage of the cell states (which could be done with a simple boolean[][] array, although there are other, more compact and efficient ways as well) and the state updating.

Notably there is no Cell interface or class in this API. In my experience, it simply doesn't make sense as an abstraction level.

You'd naïvely think it would, since obviously the grid consists of cells, but IME that's a trap. The cells just don't have any useful role apart from the grid they belong to: they don't encapsulate any state that the grid can't more easily and efficiently store itself, they can't update their state or do anything else useful without the grid telling them about their neighbors, and they don't even really make sense as part of the external API, since there's never any practical reason to manipulate a cell except as part of a grid. All they do is get in the way.

(There's one possible exception to the above, and that's if you want to have the option of using different state update rules for different cells on the grid. But in practice there are IMO better ways to do that, which I'll mention below. Another exception is if you want to generalize your code to support cellular automata on arbitrary graphs, as suggested by Timothy Truckle, in which case the Cell objects can serve as natural representations of the graph nodes. I won't discuss that option further here, though.)

There's a more general lesson to be learned here: not everything needs to be an object. A big part of good OO design is learning to identify which conceptual entities in your problem domain actually make sense to represent as distinct objects, given the kinds of operations you will be doing with them, and which are better treated as just parts, aspects or collections of other objects.


Optionally the Grid class could also handle its own initialization, but since it's possible to initialize a Grid to an arbitrary state using only its public API, it can also make sense to move the responsibility for that out of the Grid implementation. You could even define a GridInitializer interface for it, although the natural API for it would look kind of trivial:

public interface GridInitializer {
  void initialize(Grid grid);
}

A typical initialize() implementation would then get the bounds of the Grid passed to it, loop over all the x and y coordinates within those bounds, and call setState() for each of them.


In the Grid API described above, the nextCycle() method is responsible for updating the states of the cells according to the cellular automaton rule. In practice that will involve looping over all cells on the grid — or at least over all "active" cells that might need updating — and calculating their new states based on the previous state of the cell and its neighbors.

While this could all be done inside the Grid class, it could also make sense to separate the state update rule from the grid implementation into its own Rule class / interface, especially if you wanted your grids to be able to support several different CA rules.

In practice, you could handle that either by having the Grid store a reference to a Rule instance, or simply by passing the Rule you want to use as a parameter to the nextCycle() method. I actually rather like the latter idea, since it highlights the fact that the nextCycle() method is the only part of the Grid API that actually uses the update rule.


The API for the Rule, and consequently the implementation of the Grid's nextCycle() method, however, is where you'll start running into tradeoffs between simplicity, efficiency and generality. For example, if all you want to implement are Life-like cellular automata, then a simple and natural Rule API would look something like this:

public interface Rule {
  boolean nextState(boolean state, int liveNeighborCount);
}

With an API like this, the Grid would be responsible for counting the neighbors of each cell, which could be good for performance since you could implement all sorts of optimizations there. And the Rule class wouldn't have to know anything at all about Grids, which keeps the relationship between those classes nice and simple.


On the other hand, an API like the above severely limits the number and variety of possible rules you can have. Maybe, for example, you'd like to support rules with different kinds of neighborhoods, or non-totalistic or even non-isotropic rules.

You could have the Rule somehow tell the Grid which neighbors of a cell it wants to be counted and how, but that can quickly get complicated and awkward. Instead, for maximum generality, you could move the responsibility for neighbor-counting from the Grid to the Rule by having the Grid pass itself to the Rule's nextState() method, like this:

public interface Rule {
  boolean nextState(boolean state, int x, int y, Grid grid);
}

(Actually the state parameter above is kind of redundant and could be omitted, since the Rule can always obtain it by calling grid.getState(x, y). But since the rule is likely to need it anyway, passing it as a parameter may allow some minor optimizations in nextCycle(). And it just sort of intuitively feels like it belongs in the method signature, although it's always worth questioning such intuitions.)


Of course the price you pay for this flexibility (besides limiting your options for low-level performance optimization) is that a general nextState() implementation will now look a lot more complicated, as it now needs to also handle counting the live neighbors of the cell. But you can always encapsulate this complexity e.g. in an abstract base class for Life-like rules, so that you won't need to reimplement it several times:

public abstract class LifeLikeRule implements Rule {
  public abstract boolean nextState(boolean state, int liveNeighborCount);

  public boolean nextState(boolean state, int x, int y, Grid grid) {
    return nextState(state, countNeighbors(x, y, grid));
  }

  private static int countNeighbors(int x, int y, Grid grid) {
    int neighbors = 0;
    for (int dx = -1; dx <= 1; dx++) {
      for (int dy = -1; dy <= 1; dy++) {
        if ((dx != 0 || dy != 0) && grid.getState(x + dx, y + dy) == true) {
          neighbors++;
        }
      }
    }
    return neighbors;
  }
}

(Note that here I'm assuming that the Grid implementation takes care of handling boundary conditions appropriately and transparently, so that the Rule can just call getState() without having to worry about whether or not the coordinates are within bounds!)


Another useful option provided by this generalized Rule API is that it can support non-translation-invariant rules — that is, rules that are different for different cells on the grid. This could be handy if you wanted to experiment with, say, having one half of the grid follow a different update rule than the other one.

You could even define a generic adapter class that stores a Rule instance for each cell on the grid and delegates nextState() calls to those instances, e.g. something like this:

public class RuleMap implements Rule {
  private Rule[][] rules;

  public boolean nextState(boolean state, int x, int y, Grid grid) {
    return rules[x][y].nextState(state, x, y, grid);
  }
}

(Constructing and initializing this map is left as an exercise.)

And since this RuleMap is itself a Rule, you can pass it to a Grid without the Grid needing to even know that anything funny is going on!


Finally, I should note one more possible generalization you might be interested in: rules with more than two cell states. Fortunately, supporting those is easy enough — just change the types representing cell states in the API from boolean to e.g. int.

(In practice, to save memory, you might want to have different Grid implementations with different numbers of maximum states, and maybe a factory method to select the appropriate one at run-time depending on the rule. But that's an optimization you can implement later if you want to; for an initial implementation, just storing the states in an int[][] is fine.)


Ps. You might also want to consider making your Grids immutable, with nextCycle() returning a new Grid instead of mutating the current one. On a modern Java system with efficient GC and memory allocation the performance penalty should be fairly small, possibly even negligible. And in exchange you get the ability to safely pass references to Grids around (e.g. to record the time evolution of the CA pattern) without having to worry about them suddenly changing under you.

Of course, if you do that, you'll probably also want to implement some form of the Builder pattern so that you can initialize new Grids and/or create modified versions of existing ones.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ @OlivierGrégoire: I probably should've commented on that in the answer. The == true is, of course, redundant, and the method could be named e.g. isAlive, as it indeed was in my first version of the API. But as I noted later, one natural extension of this code would be to allow more than two cell states, in which case the type used to represent the states needs to be changed from boolean to something else (e.g. int or an enum type). \$\endgroup\$ Apr 6 at 11:06
5
\$\begingroup\$

The implementation seems pretty decent to me. I would refactor

    if (alive && aliveNeighboursCount > 3) {
        alive = false;
    } else if (alive && aliveNeighboursCount < 2) {
        alive = false;
    } else if (aliveNeighboursCount == 3 && !alive) {
        alive = true;
    }

as

if (alive) {
    if (aliveNeighboursCount > 3 || aliveNeighboursCount < 2)
        alive = false;
}
else {
    if (aliveNeighboursCount == 3)
        alive = true;
}

For getAliveNeighboursCount, rather than iterate-and-test for your bounds, I would sooner bound-and-iterate. In other words, define the upper, lower, left and right bounds using Math.min / Math.max. Alternatively, during the initialisation of your cells, give them a fixed collection of neighbour references so that they can be iterated unconditionally. I'd prefer the latter I think as it spends a bit more memory and up-front CPU for less continuous CPU.

Randomizer should not use an integer to 10. Instead it should use a floating-point probability between 0 and 1, and should call into Random.nextDouble.

\$\endgroup\$
4
  • \$\begingroup\$ alive = (aliveNeighboursCount == 3) || (aliveNeighboursCount == 2 && alive); is logically equivalent and more compact, if you're going to really simplify the logic. But yeah without really changing the way the logic is stated, I like the nested if better than a chain of conditions with alive && or && !alive attached to each. Interestingly C versions of these all compile differently with current compilers, with clang making an interesting branchless implementation of your way: godbolt.org/z/v4Wx7Gjfn \$\endgroup\$ Apr 5 at 10:49
  • 1
    \$\begingroup\$ Even more fun: godbolt.org/z/xP9YedMP3 aliveNeighboursCount |= (alive ? 1 : 0); to turn 2 into 3 for already-alive cells, then check for == 3. For booleans already stored as 0 or 1, that's just an OR and CMP. \$\endgroup\$ Apr 5 at 10:59
  • \$\begingroup\$ @PeterCordes Quite fun indeed, though I'm sure as you already know, (1) OP's code is Java and not C; and (2) a holistic optimisation for simulative purposes would start elsewhere. \$\endgroup\$
    – Reinderien
    Apr 5 at 11:12
  • \$\begingroup\$ Yeah, I know it's Java, that's why I didn't write aliveNeighboursCount |= alive;. I mostly put it on Godbolt to see if it would optimize to the same asm as the if version, which would have verified I got the logic right. No such luck, but if even ahead-of-time C compilers aren't going make major changes to the logic, then it might be remotely similar to what we get from a Java JIT. A branchless update function might actually be relevant to overall speed, if the loop around it ends up JITing down to something reasonable. Branch misses cost a lot of throughput. \$\endgroup\$ Apr 5 at 11:21
3
\$\begingroup\$

There's a design principle that says premature optimisation is bad; but there's another rule that says if optimisation involves a total redesign then it's not premature. You need to think right up front about whether the design is scaleable.

How large a grid do you want to be able to handle? My memory of it (last time I played with this was in the 1970s!) is that the grids can get pretty large. Allocating an object per cell is extravagant. In fact, even allocating a boolean per cell may be excessive; any efficient implementation is going to use sparse arrays, since it's likely (from my recollection) that most cells at most times will be empty.

An object oriented design should hide the implementation detail. What code needs changing if you want to move from an array of Cell objects to an array of booleans, and then to a sparse array of booleans? Pretty well everything.

Something to bear in mind is that it's usually much easier to tweak the algorithms in your code than to change the data structures. If you start with a data structure that doesn't scale to the volumes you need to handle, then you've got a major rewrite on your hands downstream, unless you're very careful to encapsulate the data structure behind an interface.

PS: I'm uniquely fortunate in having known a number of Conway's students quite well, and having spent the occasional evening sharing a pint with the great man himself.

\$\endgroup\$
3
  • \$\begingroup\$ The point of "premature optimization" is to choose a certain syntax or construct just because you think it will be faster then an existing / more readable version. Never opt for a more complex / less readable version unless you have proven by measurement that the code in question really is a bottle neck and the alternative really is (remarkably) faster. \$\endgroup\$ Apr 6 at 12:17
  • \$\begingroup\$ Yes, but... You don't always need to test alternative designs by measurement; theoretical analysis is often quite sufficient to decide what data structures are going to be scaleable. \$\endgroup\$ Apr 7 at 13:28
  • \$\begingroup\$ "theoretical analysis is often quite sufficient" No. The reason is that the theory on which the analysis bases on is surprisingly often wrong. This is more true for programming languages with memory management and predictive precompilation (as Java), since this techniques interfere with what people think of being efficient. Anyway the point is: address performance issues only when they occur. \$\endgroup\$ Apr 7 at 21:09
2
\$\begingroup\$

Further to the notes in TorbenPutkonen's answer, re Randomizer:

I agree with what is said there about implementing and interface Seeder, but I am going to call it Initializer to prevent confusion with the word "seed" as my answer mentions random number seeding.

Here, you are creating a Random object for each cell (each call to getNext())

private boolean getNext() {
    return new Random().nextInt(10) <= aliveCellsForEveryTenCell;
}

In fact a single Random object would do, as a private field of Randomizer

You are using a pseudo-random number generator but your code is not deterministic, you will never get the same results twice. One of the advantages of pseudo-random generators is that they can be re-run with the same seed to produce the exact same results at a later date.

So if you provide for that then your constructor is starting to look more like

public PsuedoRandomInitializer(int aliveCellsForEveryTenCell, long seed)   {
    this.aliveCellsForEveryTenCell = aliveCellsForEveryTenCell;
    this.random = new Random(seed);
}

Now to give the user the option of providing a seed, you could accept an optional command line argument, and use System.currentTimeMillis() if that argument is not provided. Furthermore if you generate the seed from something like argv[0].hashCode() it will allow the users to provide arbitrary strings as seeds.

Since the game runs repeatedly, you would maybe take the "initial" seed in main and feed this to another Random in the main loop which generates seeds for each individual run.

\$\endgroup\$
2
  • \$\begingroup\$ Regarding String.hashCode the formula used to calculate this is stated in the docs but I don't see a guarantee that it won't change in future releases, other hashing methods would be better, that was just an example \$\endgroup\$
    – Rodney
    Apr 6 at 11:18
  • \$\begingroup\$ Furthermore, one could use random.nextDouble() < probability with probability being provided, instead of aliveCellsForEverTenCells. Also, it's usually better to request the Random (or RandomGenerator since Java 17) instance instead of requesting a seed. \$\endgroup\$ Apr 6 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.