9
\$\begingroup\$

I wrote a simple implementation of Conway's Game of Life in Java using 2 arrays and for loop and used StdDraw library for plotting generations. It turned out that algorithm works ok for little number of cells (e.g. glider pattern), but becomes terribly slow for big number of cells (e.g. random filling) even with small array sizes (e.g., 100*100 cells). What can be the bottlenecks of my algorithm and how can I improve it?

import java.util.*;
import edu.princeton.cs.introcs.StdDraw;

public class GameOfLife {
public static void main(String[] args) {

    // the size of cells' array
    final int ROWS_NUM = 500;
    final int COLS_NUM = 500;

    Boolean[][] curGen = new Boolean[ROWS_NUM][COLS_NUM];

    // sets dead cells array
    for (int row = 0; row < ROWS_NUM; row++) {
        Arrays.fill(curGen[row], false);
    }

    // sets initial pattern - glider
    // curGen[149][150] = true;
    // curGen[150][151] = true;
    // curGen[151][149] = true;
    // curGen[151][150] = true;
    // curGen[151][151] = true;

    // fills array with random booleans, veeery slow
    Random random = new Random();
    for (int row = 0; row < ROWS_NUM; row++) {
        for (int col = 0; col < COLS_NUM; col++) {
            curGen[row][col] = random.nextBoolean();
        }
    }

    // initialises field for drawing cells
    StdDraw.setCanvasSize(COLS_NUM, ROWS_NUM);
    StdDraw.setYscale(0, ROWS_NUM);
    StdDraw.setXscale(0, COLS_NUM);
    StdDraw.setPenRadius(0);
    StdDraw.setPenColor(StdDraw.BLACK);

    // infinitely draws field
    while (true) {
        curGen = countNextGen(curGen, ROWS_NUM, COLS_NUM);
        StdDraw.clear();
        for (int row = 0; row < ROWS_NUM; row++) {
            for (int col = 0; col < COLS_NUM; col++) {
                if (curGen[row][col] == true) {
                    StdDraw.point(col, row);
                }
            }
        }
    }
}

// counts next generation
public static Boolean[][] countNextGen(Boolean[][] curGen, int rowsNum, int colsNum) {

    // copies the current array of cells into temporary array so grid can
    // be changed without affecting the other cells
    Boolean[][] nextGen = new Boolean[rowsNum][];
    for (int row = 0; row < rowsNum; row++) {
        nextGen[row] = Arrays.copyOf(curGen[row], colsNum);
    }

    // decides what will happen to cell
    for (int row = 0; row < rowsNum; row++) {
        for (int col = 0; col < colsNum; col++) {

            int numOfNeighbours = countCellNeighbours(curGen, rowsNum, colsNum, row, col);

            // under or overpopulation, cell dies
            if ((numOfNeighbours < 2) || (numOfNeighbours > 3)) {
                nextGen[row][col] = false;
            }

            // cell lives on to next generation
            if (numOfNeighbours == 2) {
                nextGen[row][col] = curGen[row][col];
            }

            // cell either stays alive, or is born
            if (numOfNeighbours == 3) {
                nextGen[row][col] = true;
            }
        }
    }
    return nextGen;
}

// counts cell's neighbours
public static int countCellNeighbours(Boolean[][] curGen, int rowsNum, int colsNum, int row, int col) {
    int numOfNeighbours = 0;

    // decides which neighbour cells to count (for edge cells
    // checks for neighbours from opposite edge)
    // not edge cells
    if ((row > 0) && (row < rowsNum - 1) && (col > 0) && (col < colsNum - 1)) {
        if (curGen[row - 1][col - 1]) {
            numOfNeighbours++;
        }
        if (curGen[row - 1][col]) {
            numOfNeighbours++;
        }
        if (curGen[row - 1][col + 1]) {
            numOfNeighbours++;
        }
        if (curGen[row][col - 1]) {
            numOfNeighbours++;
        }
        if (curGen[row][col + 1]) {
            numOfNeighbours++;
        }
        if (curGen[row + 1][col - 1]) {
            numOfNeighbours++;
        }
        if (curGen[row + 1][col]) {
            numOfNeighbours++;
        }
        if (curGen[row + 1][col + 1]) {
            numOfNeighbours++;
        }
    }

    // top cells
    else if (row == 0) {

        // top-left cells
        if (col == 0) {

            // above
            if (curGen[rowsNum - 1][colsNum - 1]) {
                numOfNeighbours++;
            }
            if (curGen[rowsNum - 1][col]) {
                numOfNeighbours++;
            }
            if (curGen[rowsNum - 1][col + 1]) {
                numOfNeighbours++;
            }

            // same row
            if (curGen[row][colsNum - 1]) {
                numOfNeighbours++;
            }
            if (curGen[row][col + 1]) {
                numOfNeighbours++;
            }

            // below
            if (curGen[row + 1][colsNum - 1]) {
                numOfNeighbours++;
            }
            if (curGen[row + 1][col]) {
                numOfNeighbours++;
            }
            if (curGen[row + 1][col + 1]) {
                numOfNeighbours++;
            }
        }

        // top-right cells
        else if (col == colsNum - 1) {

            // above
            if (curGen[rowsNum - 1][col - 1]) {
                numOfNeighbours++;
            }
            if (curGen[rowsNum - 1][col]) {
                numOfNeighbours++;
            }
            if (curGen[rowsNum - 1][0]) {
                numOfNeighbours++;
            }

            // same row
            if (curGen[row][col - 1]) {
                numOfNeighbours++;
            }
            if (curGen[row][0]) {
                numOfNeighbours++;
            }

            // below
            if (curGen[row + 1][col - 1]) {
                numOfNeighbours++;
            }
            if (curGen[row + 1][col]) {
                numOfNeighbours++;
            }
            if (curGen[row + 1][0]) {
                numOfNeighbours++;
            }
        }

        // top but not left or right
        else {

            // above
            if (curGen[rowsNum - 1][col - 1]) {
                numOfNeighbours++;
            }
            if (curGen[rowsNum - 1][col]) {
                numOfNeighbours++;
            }
            if (curGen[rowsNum - 1][col + 1]) {
                numOfNeighbours++;
            }

            // same row
            if (curGen[row][col - 1]) {
                numOfNeighbours++;
            }
            if (curGen[row][col + 1]) {
                numOfNeighbours++;
            }

            // below
            if (curGen[row + 1][col - 1]) {
                numOfNeighbours++;
            }
            if (curGen[row + 1][col]) {
                numOfNeighbours++;
            }
            if (curGen[row + 1][col + 1]) {
                numOfNeighbours++;
            }
        }
    }

    //bottom cells
    else if (row == rowsNum - 1) {

        // bottom-left cells
        if (col == 0) {

            // above
            if (curGen[row - 1][colsNum - 1]) {
                numOfNeighbours++;
            }
            if (curGen[row - 1][col]) {
                numOfNeighbours++;
            }
            if (curGen[row - 1][col + 1]) {
                numOfNeighbours++;
            }

            // same row
            if (curGen[row][colsNum - 1]) {
                numOfNeighbours++;
            }
            if (curGen[row][col + 1]) {
                numOfNeighbours++;
            }

            // below
            if (curGen[0][colsNum - 1]) {
                numOfNeighbours++;
            }
            if (curGen[0][col]) {
                numOfNeighbours++;
            }
            if (curGen[0][col + 1]) {
                numOfNeighbours++;
            }
        }

        // bottom-right cells
        else if (col == colsNum - 1) {

            // above
            if (curGen[row - 1][col - 1]) {
                numOfNeighbours++;
            }
            if (curGen[row - 1][col]) {
                numOfNeighbours++;
            }
            if (curGen[row - 1][0]) {
                numOfNeighbours++;
            }

            // same row
            if (curGen[row][col - 1]) {
                numOfNeighbours++;
            }
            if (curGen[row][0]) {
                numOfNeighbours++;
            }

            // below
            if (curGen[0][col - 1]) {
                numOfNeighbours++;
            }
            if (curGen[0][col]) {
                numOfNeighbours++;
            }
            if (curGen[0][0]) {
                numOfNeighbours++;
            }
        }

        // bottom but not left or right
        else {

            // above
            if (curGen[row - 1][col - 1]) {
                numOfNeighbours++;
            }
            if (curGen[row - 1][col]) {
                numOfNeighbours++;
            }
            if (curGen[row - 1][col + 1]) {
                numOfNeighbours++;
            }

            // same row
            if (curGen[row][col - 1]) {
                numOfNeighbours++;
            }
            if (curGen[row][col + 1]) {
                numOfNeighbours++;
            }

            // below
            if (curGen[0][col - 1]) {
                numOfNeighbours++;
            }
            if (curGen[0][col]) {
                numOfNeighbours++;
            }
            if (curGen[0][col + 1]) {
                numOfNeighbours++;
            }
        }
    }

    // left but not top or bottom cells
    else if (col == 0) {

        // above
        if (curGen[row - 1][colsNum - 1]) {
            numOfNeighbours++;
        }
        if (curGen[row - 1][col]) {
            numOfNeighbours++;
        }
        if (curGen[row - 1][col + 1]) {
            numOfNeighbours++;
        }

        // same row
        if (curGen[row][colsNum - 1]) {
            numOfNeighbours++;
        }
        if (curGen[row][col + 1]) {
            numOfNeighbours++;
        }

        // below
        if (curGen[row + 1][colsNum - 1]) {
            numOfNeighbours++;
        }
        if (curGen[row + 1][col]) {
            numOfNeighbours++;
        }
        if (curGen[row + 1][col + 1]) {
            numOfNeighbours++;
        }
    }

    // right but not top or bottom cells
    else if (col == colsNum - 1) {

        // above
        if (curGen[row - 1][col - 1]) {
            numOfNeighbours++;
        }
        if (curGen[row - 1][col]) {
            numOfNeighbours++;
        }
        if (curGen[row - 1][0]) {
            numOfNeighbours++;
        }

        // same row
        if (curGen[row][col - 1]) {
            numOfNeighbours++;
        }
        if (curGen[row][0]) {
            numOfNeighbours++;
        }

        // below
        if (curGen[row + 1][col - 1]) {
            numOfNeighbours++;
        }
        if (curGen[row + 1][col]) {
            numOfNeighbours++;
        }
        if (curGen[row + 1][0]) {
            numOfNeighbours++;
        }
    }
    return numOfNeighbours;
}

}

\$\endgroup\$
  • \$\begingroup\$ Do you really need to repaint the canvas as many times per second as possible? Wouldn't it be better to limit the rendering to about 60 frames per second? Because in the while (true) loop there are a lot of (nested!) for loops created which is, what I think, the reason of your performance problem. \$\endgroup\$ – Datagrammar Apr 18 '16 at 21:02
  • 2
    \$\begingroup\$ Welcome to Code Review and nice job on your first question. I added a few tags, one is the "beginner" tag since you said you were new. I hope you get some great answers! \$\endgroup\$ – Phrancis Apr 18 '16 at 21:06
  • 1
    \$\begingroup\$ Thanks for answers! @Datagrammar, can you, please, write an example of fps limitation? I tried a couple of variants, but they didn't seem to improve the speed. \$\endgroup\$ – snowfinch27 Apr 19 '16 at 7:53
  • \$\begingroup\$ @snowfinch27 Ok I'll try and post it soon. \$\endgroup\$ – Datagrammar Apr 19 '16 at 8:25
8
\$\begingroup\$

Performance

  1. StdDraw.show(int) If you take a look at the documentation for StdDraw.show(int), you'll notice the following:

    It also speeds up drawing a huge number of shapes (call {@code show(0)} to defer drawing on screen, draw the shapes, and call {@code show(0)} to display them all on screen at once).
    With that in mind, let's take a look at your drawing loop:

    // infinitely draws field
    while (true) {
        curGen = countNextGen(curGen, ROWS_NUM, COLS_NUM);
        StdDraw.clear();
        for (int row = 0; row < ROWS_NUM; row++) {
            for (int col = 0; col < COLS_NUM; col++) {
                if (curGen[row][col] == true) {
                    StdDraw.point(col, row);
                }
            }
        }
    }
    

    Using the suggestion in the documentation, we add StdDraw.show(0) calls before and after painting each generation. We end up with the following:

    // infinitely draws field
    while (true) {
        curGen = countNextGen(curGen, ROWS_NUM, COLS_NUM);
        StdDraw.show(0);
        StdDraw.clear();
        for (int row = 0; row < ROWS_NUM; row++) {
            for (int col = 0; col < COLS_NUM; col++) {
                if (curGen[row][col] == true) {
                    StdDraw.point(col, row);
                }
            }
        }
        StdDraw.show(0);
    }
    

    If we run the application now, we'll already see a huge visual improvement! Moral of the story: get familiar with the libraries you're using by reading the documentation. Any good library will provide code samples of common use cases.

    How (and why) this works: StdDraw (and just about any other graphics library) has the ability to do what's called Double Buffering. In short, you put a bunch of stuff a bunch of times in the off-screen buffer, and when you're ready it will all be drawn at once to the on-screen buffer. The alternative is to constantly be drawing things one at a time to the on-screen buffer, which is what your code does currently. In fact, it's so slow that you can see each generation being drawn pixel by pixel, line by line. By using StdDraw.show(0), you're saying: "Wait! Let me tell you everything I want to see before you go make it happen." instead of saying: "Here, draw this" (StdDraw draws it) "Oh, draw this too" (StdDraw goes and draws that too) "And this too", back and forth, back and forth, etc. etc.

  2. Boolean vs. boolean One of the first things that jumped out at me was the use of the Boolean object as opposed to the boolean primitive. Here's a good post detailing the differences between Boolean and boolean. In your situation, there isn't a need to be creating Boolean objects - the primitive will be sufficient. This is a simple change in your code; just do a find-replace for all instances of "Boolean" and replace them with "boolean"!

Design

  1. Separating the view This review is tagged beginner, but it's never too early to learn good design practices! Enter SoC. SoC stands for Separation of Concerns, and essentialy means that a piece of code should have one and only one responsibility. This will make your code more modular, and therefore reusable. In a simple case such as this it may not seem important, but it's simple to implement and it's better to learn on simple examples before jumping to a complex application!

    In this code, the biggest change is to pull out the "view" code from the rest. That is, anything dealing with drawing on the screen should be in its own view class. The idea is to separate the UI from business logic (in this case the business logic will be determining which cells are to be drawn, etc.). The view should be dumb and have little to no logic. A common design pattern to follow is called MVP (Model-View-Presenter). I won't go into the details of MVP here because your application is not driven by user interaction. That is, you aren't responding to button clicks, etc. Once you kick off the simulation, you kick back and enjoy a cold one.

    In practice, we can start with the following template:

    public class GameOfLifeView {
    
        public GameOfLifeView() {
    
        }
    
    }
    
    public class GameOfLifePresenter {
    
        private final GameOfLifeView view;
    
        public GameOfLifePresenter(final GameOfLifeView view) {
            this.view = view;
        }
    
    }
    
    public class GameOfLifeApp {
    
        public GameOfLifeApp() {
            new GameOfLifePresenter(new GameOfLifeView());
        }
    
        public static void main(String... args) {
            new GameOfLifeApp();
        }
    
    }
    

    By passing in the view to the presenter, we allow the presenter to handle the business logic and control what happens to the view.

    But, where's the "M" from MVP?? I'm glad you asked! The model is what maintains state in an program. In our case, it is the 2D boolean array. We could make a Generation class which just has a boolean[][] in order to better illustrate MVP, but it's not really necessary.

    Adding in our "model":

    public class GameOfLifeView {
    
        public GameOfLifeView() {
    
        }
    
        /**
         * Returns the non-negative, non-zero height of drawable area.
         */
        public int getHeight() {
    
        }
    
        /**
         * Returns the non-negative, non-zero width of drawable area.
         */
        public int getWidth() {
    
        }
    
    }
    
    public class GameOfLifePresenter {
    
        private final GameOfLifeView view;
        private final boolean[][] currentGeneration;
    
        public GameOfLifePresenter(final GameOfLifeView view) {
            this.view = view;
            this.currentGeneration = new boolean[view.getHeight()][view.getWidth()];
        }
    
    }
    

    Great! Now how do we actually make this thing move? Well, we need to be able to tell the view what to do. Let's add a drawGeneration(boolean[][]) method to our view.

    public class GameOfLifeView {
    
        public GameOfLifeView() {
            StdDraw.setCanvasSize(width, height);
            StdDraw.setYscale(0, height);
            StdDraw.setXscale(0, width);
            StdDraw.setPenRadius(0);
            StdDraw.setPenColor(StdDraw.BLACK);
        }
    
        public int getHeight() {...}
        public int getWidth() {...}
    
        /**
         * Draws the given generation to the screen.
         */
        public void drawGeneration(final boolean[][] generation) {
            StdDraw.show(0);
            StdDraw.clear();
            for (int row = 0; row < generation.length; row++) {
                for (int col = 0; col < generation[row].length; col++) {
                    if (generation[row][col] == true) {
                        StdDraw.point(col, row);
                    }
                }
            }
            StdDraw.show(0);
        }
    
    }
    

    Look familiar? It should - it's the same code we ended up with earlier, except instead of being inside a while-loop, we're only drawing a single generation. You'll also notice that we've just moved all of the StdDraw code into the view! Now our presenter doesn't know or care about StdDraw - which is great! To take this a step further (baby steps!) let's make GameOfLifeView an interface. Why? Well, suppose that a few months from now you decide to learn a new graphics library. You could come back to this little application and implement the GameOfLifeView interface using the new graphics library! Modularity FTW.

    public interface GameOfLifeView {
        public int getHeight();
        public int getWidth();
        public void drawGeneration(final boolean[][] generation);
    }
    
    public class GameOfLifeViewStdDraw implements GameOfLifeView {
    
        public GameOfLifeViewStdDraw() {
            // StdDraw setup stuff from before
        }
    
        @Override
        public int getHeight() {
            // ...
        }
    
        @Override
        public int getWidth() {
            // ...
        }
    
        @Override
        public void drawGeneration(final boolean[][] generation) {
            // ...
        }
    
    }
    
    public GameOfLifePresenter {
        // We still want to use the interface type here - the presenter shouldn't care about which implementation we're using!
        private final GameOfLifeView view;
    
        public GameOfLifePresenter(final GameOfLifeView view) {
            this.view = view;
        }
    }
    
  2. Neighbor-checking Now that we've tackled the difficult task of extracting the view and presenter into different classes, the only thing left to address is some of the complex logic. Right now we have a HUGE block of if-else statements trying to handle every possible scenario to count the neighbors of a given cell. Well, one way we can simplify this is to realize that for any given cell, there are 8 possible neighbors. So our logic can be reduced to only 8 simple checks that should work for every cell!

    private int countNeighbors(final boolean[][] generation, final int row, final int col) {
        int numNeighbors = 0;
    
        // Look NW
        if ((row - 1 >= 0) && (col - 1 >= 0)) {
            numNeighbors = generation[row - 1][col - 1] ? numNeighbors + 1 : numNeighbors;
        }
        // Look W
        if ((row >= 0) && (col - 1 >= 0)) {
            numNeighbors = generation[row][col - 1] ? numNeighbors + 1 : numNeighbors;
        }
        // Look SW
        if ((row + 1 < generation.length) && (col - 1 >= 0)) {
            numNeighbors = generation[row + 1][col - 1] ? numNeighbors + 1 : numNeighbors;
        }
        // Look S
        if ((row + 1 < generation.length) && (col < generation[0].length)) {
            numNeighbors = generation[row + 1][col] ? numNeighbors + 1 : numNeighbors;
        }
        // Look SE
        if ((row + 1 < generation.length) && (col + 1 < generation[0].length)) {
            numNeighbors = generation[row + 1][col + 1] ? numNeighbors + 1 : numNeighbors;
        }
        // Look E
        if ((row < generation.length) && (col + 1 < generation[0].length)) {
            numNeighbors = generation[row][col + 1] ? numNeighbors + 1 : numNeighbors;
        }
        // Look NE
        if ((row - 1 >= 0) && (col + 1 < generation[0].length)) {
            numNeighbors = generation[row - 1][col + 1] ? numNeighbors + 1 : numNeighbors;
        }
        // Look N
        if ((row - 1 >= 0) && (col < generation[0].length)) {
            numNeighbors = generation[row - 1][col] ? numNeighbors + 1 : numNeighbors;
        }
    
        return numNeighbors;
    }
    
  3. Kicking it all off This is all fine and great, but we still don't have a way to get things rolling. Well, we want to start things from the application level. This is for a couple of reasons. We can't start from the view, because our view is dumb (remember?) so it needs someone to tell it what to do! The presenter is an option, but that would require starting somehow in the constructor - what if we don't want to start right away? That leaves us with the application.

    public class GameOfLifePresenter {
    
        // ...
    
        /**
         * Starts the task of progressing through generations
         */
        public void start() {
            // The while-loop from before!
            while(true) {
                // Progress through the generations
            }
        }
    
    }
    
    public class GameOfLifeApp {
    
        public GameOfLifeApp() {
            new GameOfLifePresenter(new GameOfLifeView()).start();
        }
    
        public static void main(String... args) {
            new GameOfLifeApp();
        }
    
    }
    

    Now the real meat and potatoes: progressing through each generation. You've already got the algorithm down, so we can just do a bit of cleanup work to make the good look good.

    public class GameOfLifePresenter {
        private boolean[][] currentGeneration;
    
        // ...
    
        public void start() {
            while(true) {
                currentGeneration = progressGeneration(currentGeneration);
                view.drawGeneration(currentGeneration);
            }
        }
    
        private boolean[][] progressGeneration(final boolean[][] generation) {
            final boolean[][] nextGeneration = cloneGeneration(generation);
    
            // Decide the fate of each cell
            for (int row = 0; row < generation.length; ++row) {
                for (int col = 0; col < generation[row].length; ++col) {
                    final int numNeighbors = countNeighbors(generation, row, col);
                    // If under-populated or over-populated, cell dies
                    if ((numNeighbors < 2) || (numNeighbors > 3)) {
                        nextGeneration[row][col] = false;
                    }
                    // No change
                    if (numNeighbors == 2) {
                        nextGeneration[row][col] = generation[row][col];
                    }
                    // Cell stays alive, or a new cell is born
                    if (numNeighbors == 3) {
                        nextGeneration[row][col] = true;
                    }
                }
            }
    
            return nextGeneration;
        }
    
        private boolean[][] cloneGeneration(final boolean originalGeneration[][]) {
            final boolean[][] newGeneration = new boolean[originalGeneration.length][];
            for (int row = 0; row < originalGeneration.length; ++row) {
                newGeneration[row] = Arrays.copyOf(originalGeneration[row], originalGeneration[row].length);
            }
            return newGeneration;
        }
    
        private int countNeighbors(final boolean[][] generation, final int row, final int col) {...}
    }
    

    Now you just have to initialize our current generation in the constructor with whatever you like (random, or the glider, etc) and we're good to go!

  4. Execution I don't want to throw too much at you, but one problem that you might notice is that we've started our simulation, but we're stuck in the while loop inside GameOfLifePresenter.start(), and that's no good. I'd also like to simultaneously address the framerate. To do this, we can leverage java.util.Timer and java.util.TimerTask. This will let us schedule all the work of advancing the generation and updating the view without being stuck in an infinite loop! Notice that the last parameter in the Timer.schedule() method is the period. This will be the duration in milliseconds between executions. So if we desire a frame rate of 60fps, then we can do (1000ms/sec)/(60fps) which is about 16-17. I chose 15 because it seemed like a nicer number :). This post is a nice short example of using a Timer: How to use java.util.Timer.

    In the case of the code at hand:

    public class GameOfLifePresenter {
        private TimerTask task;
    
        // ...
    
        public void start() {
            task = new TimerTask() {
                @SuppressWarnings("synthetic-access")
                @Override
                public void run() {
                    currentGeneration = progressGeneration(currentGeneration);
                    view.drawGeneration(currentGeneration);
                }
            };
            new Timer().schedule(task, 0, 15);
        }
    
        public void stop() {
            if (task == null) {
                return;
            }
            task.cancel();
        }
    }
    

    Now we can start/stop the simulation from the app level and the code isn't stuck in an infinite loop!

Full Code

GameOfLifeApp.java

public class GameOfLifeApp {

    /**
     * Creates a new GameOfLifeApp
     * @param width The width to use for the application window. Cannot be negative or zero.
     * @param height The height to use for the application window. Cannot be negative or zero.
     */
    public GameOfLifeApp(final int width, final int height) {
        if (width < 1) {
            throw new IllegalArgumentException("width must be positive");
        }
        if (height < 1) {
            throw new IllegalArgumentException("height must be positive");
        }
        final GameOfLifeView gameOfLifeView = new GameOfLifeViewStdDraw(width, height);
        final GameOfLifePresenter gameOfLifePresenter = new GameOfLifePresenter(gameOfLifeView);
        gameOfLifePresenter.start();
    }

    /**
     * Main method.
     * @param args The runtime args.
     */
    public static void main(final String... args) {
        // Optionally, you can get these dimensions at runtime from the user
        new GameOfLifeApp(500, 500);
    }

}

GameOfLifePresenter.java

public class GameOfLifePresenter {

    private final GameOfLifeView view;
    private boolean[][] currentGeneration;
    private TimerTask task;

    /**
     * Constructor
     * @param view The GameOfLifeView. Cannot be null.
     */
    public GameOfLifePresenter(final GameOfLifeView view) {
        if (view == null) {
            throw new IllegalArgumentException("view cannot be null");
        }
        this.view = view;
        this.currentGeneration = new boolean[view.getHeight()][view.getWidth()];
        final Random random = new Random();
        for (int row = 0; row < currentGeneration.length; ++row) {
            for (int col = 0; col < currentGeneration[row].length; ++col) {
                currentGeneration[row][col] = random.nextBoolean();
            }
        }
    }

    /**
     * Starts the task of progressing through generations and updating the view.
     */
    public void start() {
        task = new TimerTask() {
            @SuppressWarnings("synthetic-access")
            @Override
            public void run() {
                currentGeneration = progressGeneration(currentGeneration);
                view.drawGeneration(currentGeneration);
            }
        };
        new Timer().schedule(task, 0, 15);
    }

    private boolean[][] progressGeneration(final boolean[][] generation) {
        final boolean[][] nextGeneration = cloneGeneration(generation);

        // Decide the fate of each cell
        for (int row = 0; row < generation.length; ++row) {
            for (int col = 0; col < generation[row].length; ++col) {
                final int numNeighbors = countNeighbors(generation, row, col);
                // If under-populated or over-populated, cell dies
                if ((numNeighbors < 2) || (numNeighbors > 3)) {
                    nextGeneration[row][col] = false;
                }
                // No change
                if (numNeighbors == 2) {
                    nextGeneration[row][col] = generation[row][col];
                }
                // Cell stays alive, or a new cell is born
                if (numNeighbors == 3) {
                    nextGeneration[row][col] = true;
                }
            }
        }

        return nextGeneration;
    }

    private boolean[][] cloneGeneration(final boolean originalGeneration[][]) {
        final boolean[][] newGeneration = new boolean[originalGeneration.length][];
        for (int row = 0; row < originalGeneration.length; ++row) {
            newGeneration[row] = Arrays.copyOf(originalGeneration[row], originalGeneration[row].length);
        }
        return newGeneration;
    }

    private int countNeighbors(final boolean[][] generation, final int row, final int col) {
        int numNeighbors = 0;

        // Look NW
        if ((row - 1 >= 0) && (col - 1 >= 0)) {
            numNeighbors = generation[row - 1][col - 1] ? numNeighbors + 1 : numNeighbors;
        }
        // Look W
        if ((row >= 0) && (col - 1 >= 0)) {
            numNeighbors = generation[row][col - 1] ? numNeighbors + 1 : numNeighbors;
        }
        // Look SW
        if ((row + 1 < generation.length) && (col - 1 >= 0)) {
            numNeighbors = generation[row + 1][col - 1] ? numNeighbors + 1 : numNeighbors;
        }
        // Look S
        if ((row + 1 < generation.length) && (col < generation[0].length)) {
            numNeighbors = generation[row + 1][col] ? numNeighbors + 1 : numNeighbors;
        }
        // Look SE
        if ((row + 1 < generation.length) && (col + 1 < generation[0].length)) {
            numNeighbors = generation[row + 1][col + 1] ? numNeighbors + 1 : numNeighbors;
        }
        // Look E
        if ((row < generation.length) && (col + 1 < generation[0].length)) {
            numNeighbors = generation[row][col + 1] ? numNeighbors + 1 : numNeighbors;
        }
        // Look NE
        if ((row - 1 >= 0) && (col + 1 < generation[0].length)) {
            numNeighbors = generation[row - 1][col + 1] ? numNeighbors + 1 : numNeighbors;
        }
        // Look N
        if ((row - 1 >= 0) && (col < generation[0].length)) {
            numNeighbors = generation[row - 1][col] ? numNeighbors + 1 : numNeighbors;
        }

        return numNeighbors;
    }

    /**
     * Stops the task of progressing through generations. Can safely be called prior to calling start().
     */
    public void stop() {
        if (task == null) {
            return;
        }
        task.cancel();
    }

}

GameOfLifeView

public interface GameOfLifeView {

    /**
     * Returns the width of drawable area.
     * @return The non-negative, non-zero width of drawable area.
     */
    public int getWidth();

    /**
     * Returns the height of drawable area.
     * @return The non-negative, non-zero height of drawable area.
     */
    public int getHeight();

    /**
     * Draws the given generation.
     * @param generation The generation to draw as a boolean[][]. Cannot be null.
     */
    public void drawGeneration(final boolean[][] generation);

}

GameOfLifeViewStdDraw

public class GameOfLifeViewStdDraw implements GameOfLifeView {

    private final int width;
    private final int height;

    /**
     * Constructor
     * @param width The width to use for the application window. Cannot be negative or zero.
     * @param height The height to use for the application window. Cannot be negative or zero.
     */
    public GameOfLifeViewStdDraw(final int width, final int height) {
        if (width < 1) {
            throw new IllegalArgumentException("width must be a positive value");
        }
        if (height < 1) {
            throw new IllegalArgumentException("height must be a positive value");
        }
        this.width = width;
        this.height = height;

        StdDraw.setCanvasSize(width, height);
        StdDraw.setYscale(0, height);
        StdDraw.setXscale(0, width);
        StdDraw.setPenRadius(0);
        StdDraw.setPenColor(StdDraw.BLACK);
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public int getWidth() {
        return width;
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public int getHeight() {
        return height;
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public void drawGeneration(final boolean[][] generation) {
        StdDraw.show(0);
        StdDraw.clear();
        for (int row = 0; row < generation.length; row++) {
            for (int col = 0; col < generation[row].length; col++) {
                if (generation[row][col] == true) {
                    StdDraw.point(col, row);
                }
            }
        }
        StdDraw.show(0);
    }

}

Summary

Great job! Conway's Game of Life is a great way to start learning programming concepts and get a taste of UI code. The code above is just my suggestion of ways you can make improvements, and is clearly not the only correct way to do things.

\$\endgroup\$

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.