6
\$\begingroup\$

Well, there are many game of life's already, but after posting an answer on it in C#, I thought I might as well check if I did any better and if there is anything new to learn - there always is.

Design:

  • main object is a Board which represents a board including the living cells;
  • both the initial board and the subsequent boards are created using a builder and are otherwise immutable
  • the actual state of the board is kept in an array of 64 bit words, this is not a two dimensional array but a single array consisting of the subsequent rows
  • the actual game is run in Game of course, using the deliberately simple next method
  • the Direction enum can be used to identify the neighboring cells
  • the Position class is too boring to explain, it's immutable as well but can be used to calculate other positions using relativePosition.

I've left out any JavaDoc for conciseness, the code should be mostly self explaining (please indicate if you think it doesn't). GameMain is just there for demonstration purposed, I've left out any UI work; I am not looking for UI advice. Also, the exceptions are deliberately left out; they are there but known to be dumbed down.

Finally, in Board.Builder you will find a seemingly unused method called applyPattern which can be used to apply patterns as a kind of "stamp". The code for that is slightly too expansive to post directly (I've designed a file format for boards and patterns for good measure).

Anything you would have done differently w.r.t. design? Coding practices or conciseness? Please let me know.

Board

package nl.owlstead.gameoflife;

import java.util.Arrays;

public class Board {
    private final int width;
    private final int height;

    private final long[] state;
    private final int stateWidth;
    
    private Board(int width, int height, long[] state) {
        this.width = width;
        this.height = height;
        this.state = state;
        this.stateWidth = state.length / height;
    }
    
    public boolean isAlive(Position pos) {
        if (!isValid(width, height, pos)) {
            throw new IllegalArgumentException("Position " + pos + " is not on the board.");
        }
        
        int x = pos.getX();
        int y = pos.getY();
        int cellsInState = calculateLocationInState(stateWidth, x, y);
        long cells = state[cellsInState];
        int cellInCells = calculateLocationInLong(x);
        return (cells & (1L << cellInCells)) != 0; 
    }
    
    public boolean isValid(Position pos) {
        return isValid(width, height, pos);
    }
    
    public int getWidth() {
        return width;
    }
    
    public int getHeight() {
        return height;
    }

    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof Board)) {
            return false;
        }
        
        var that = (Board) obj;
        // check dimensions
        if ((this.width != that.width) || (this.height != that.height)) {
            return false;
        }
        
        // simple array compare
        return Arrays.compare(this.state, that.state) == 0;
    }
    
    public String toString() {
        if (width * height > 6400) {
            return "Board too large";
        }
        
        // includes carriage return        
        var sb = new StringBuilder((width + 1) * height);
        
        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                sb.append(isAlive(new Position(x, y)) ? "\u25CF" : " "); // "\u25A1" is white square
            }
            sb.append("\n");
        }
        
        return sb.toString();
    }

    private static boolean isValid(int width, int height, Position pos) {
        int x = pos.getX();
        int y = pos.getY();
        return (x >= 0) && (x < width) && (y >= 0) && (y < height); 
    }

    private static int calculateLocationInState(int stateWidth, int x, int y) {
        return y * stateWidth + x / Long.SIZE;
    }

    private static int calculateLocationInLong(int x) {
        return x % Long.SIZE;
    }

    private static int calculateStateWidth(int width) {
        return (width + Long.SIZE - 1) / Long.SIZE;
    }
    
    private static int calculateStateSize(int width, int height) {
        return calculateStateWidth(width) * height;
    }

    public static class Builder {
        private final int width;
        private final int height;
        private final long[] state;
        private int stateWidth;

        public Builder(int width, int height) {
            this.width = width;
            this.height = height;
            this.state = new long[calculateStateSize(width, height)];
            this.stateWidth = calculateStateWidth(width);
        }

        public void makeAlive(Position pos) {
            // NOTE could be made assertion
            if (!isValid(width, height, pos)) {
                throw new IllegalArgumentException("Position is not valid for this board " + pos);
            }
            
            int x = pos.getX();
            int y = pos.getY();
            int cellsInState = calculateLocationInState(stateWidth, x, y);
            int cellInCells = calculateLocationInLong(x);
            long mask = 1L << cellInCells;  
            this.state[cellsInState] |= mask;
        }

        public void applyPattern(Position position, GolPattern pattern) {
            var alivePositions = pattern.getAlivePositions();
            for (var alivePosition : alivePositions) {
                var alivePositionOnBoard = alivePosition.relativePosition(position.getX(), position.getY());
                makeAlive(alivePositionOnBoard);
            }
        }

        public Board build() {
            return new Board(width, height, state);
        }
    }
}

Position

package nl.owlstead.gameoflife;

public final class Position {
    private final int x;
    private final int y;

    public Position(int x, int y) {
        this.x = x;
        this.y = y;
    }
    
    public int getX() {
        return x;
    }
    
    public int getY() {
        return y;
    }
    
    public Position relativePosition(int deltaX, int deltaY) {
        return new Position(x + deltaX, y + deltaY);
    }
    
    @Override
    public int hashCode() {
        return x + y * 0x10001;
    }
    
    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof Position)) {
            return false;
        }
        
        var that = (Position) obj;
        
        return (this.x == that.x && this.y == that.y);
    }
    
    @Override
    public String toString() {
        return String.format("(%d, %d)", x, y);
    }
}

Game

package nl.owlstead.gameoflife;

public class Game {
    
    // could be extended to detect cycles
    public enum Freshness {
        FRESH,
        // NOTE for future use
        CYCLING,
        STALE;
    }
    
    private Freshness freshness = Freshness.FRESH;
    private Board current;

    public Game(Board start) {
        this.current = start;
    }
    
    private int getNeighborCount(Position pos) {
        int count = 0;
        for (var direction : Direction.ALL_DIRECTIONS) {
            var candidate = pos.relativePosition(direction.getDeltaX(), direction.getDeltaY());
            if (current.isValid(candidate) && current.isAlive(candidate)) {
                count++;
            }
        }
        return count;
    }
    
    private boolean becomesOrStaysAlive(Position pos) {
        boolean isAlive = current.isAlive(pos);
        int neighborCount = getNeighborCount(pos);

        // condensed rules for game of life
        if (isAlive) {
            return neighborCount == 2 || neighborCount == 3;
        } else {
            return neighborCount == 3;
        }
    }
    
    private Board calculateNextBoardState() {
        int width = current.getWidth();
        int height = current.getHeight();
        var builder = new Board.Builder(width, height);
        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                Position pos = new Position(x, y);
                if (becomesOrStaysAlive(pos)) {
                    builder.makeAlive(pos);
                }
            }
        }
        return builder.build();
    }

    public boolean next() {
        var next = calculateNextBoardState();
        if (next.equals(current)) {
            this.freshness = Freshness.STALE;
            return false;
        } else {
            this.current = next;
            return true;
        }
    }

    public Board getCurrent() {
        return current;
    }

    public Freshness getFreshness() {
        return freshness;
    }
}

Direction

package nl.owlstead.gameoflife;

import java.util.EnumSet;
import java.util.Set;

public enum Direction {
    N(0, -1),
    NE(1, -1),
    E(1, 0),
    SE(1, 1),
    S(0, 1),
    SW(-1, 1),
    W(-1, 0),
    NW(-1, -1);
    
    public static final Set<Direction> ALL_DIRECTIONS = EnumSet.allOf(Direction.class);
    
    private final int deltaX;
    private final int deltaY;
    
    private Direction(int deltaX, int deltaY) {
        this.deltaX = deltaX;
        this.deltaY = deltaY;
    }
    
    public int getDeltaX() {
        return deltaX;
    }
    
    public int getDeltaY() {
        return deltaY;
    }
}

GameMain

package nl.owlstead.gameoflife;

import java.util.regex.Pattern;

public class GameMain {
    private static final Pattern POSITION_FINDER_PATTERN = Pattern.compile("[(](\\d+),(\\d+)[)]");
    
    public static void main(String[] args) {
        var builder = new Board.Builder(8, 8);
        String gliderStartState = "(1,0)(2,1)(0,2)(1,2)(2,2)";
        var m = POSITION_FINDER_PATTERN.matcher(gliderStartState);
        while (m.lookingAt()) {
            int x = Integer.parseInt(m.group(1));
            int y = Integer.parseInt(m.group(2));
            Position pos = new Position(x, y);
            builder.makeAlive(pos);
            
            m.region(m.end(), m.regionEnd());
        }
        if (!m.hitEnd()) {
            throw new RuntimeException();
        }
        var start = builder.build();
        
        var game = new Game(start);
        do {
            System.out.println(game.getCurrent());
        } while (game.next());
    }
}
\$\endgroup\$
0

2 Answers 2

5
\$\begingroup\$

Not bad at all, therefore here's only a few things that rub me the wrong way:

  • Encoding the state in a long. Why? We are talking about saving a few hundred bytes at most, and we are in an age where this will not even make a difference on a mobile phone. This had been a good idea in 1970, but today you're better off when you simply use an array which you can index.
  • Even if you absolutely want to save space by encoding more values in a single long, use java.util.BitSet instead of rolling your own.
  • Half of the methods in the Board class are static, probably because you use them in the Builder, too. This makes the class a mixup of object oriented encapsulation and a utility class. I don't like that.
  • "var" was a patently bad idea in my opinion, and it is banned from all projects where I can influence the coding guidelines.
  • Making classes final (your Position class) normally does not make sense. How can you tell today, that there won't be a good reason to extend the class a year down the road.
  • The ALL_DIRECTIONS set in Direction is (a) not necessary, as an enum has the values() method, and (b) mutable. The final only makes the reference final, but you could still call Direction.ALL_DIRECTIONS.clear() from outside. You have to wrap it in Collections.immutableSet() to achive your goal.
  • Having the Board encode the visual output is a mixup of concerns. OK for debugging, but not beyond that.
\$\endgroup\$
4
  • \$\begingroup\$ Interesting part about the memory management; I thought this was the best way to create a single compact & aligned piece of memory though. If you know a good way of creating a builder without the static methods then I'm all ears; I rewrote the original methods when I found out that the builder needed them as well, and I think extending the object with a builder may not be the best thing to do (but maybe I was wrong about that). \$\endgroup\$ Aug 10, 2021 at 14:12
  • \$\begingroup\$ I recreated one where the builder extends the original class and it seems to work; some private static methods still required as you can only call the super constructor directly though. One possible issue with that is that some of the none-builder methods may not work in an invalid state during building; you might want to go over those and override them throwing an OperationNotSupportedException. \$\endgroup\$ Aug 10, 2021 at 17:06
  • \$\begingroup\$ Worse though, you could now use the builder class as stand in for the original class, at which point I have to call defeat. \$\endgroup\$ Aug 10, 2021 at 17:08
  • \$\begingroup\$ The options I can immediately think of are a static utility class to encapsulate the common methods, or a common base class. Both have their drawbacks. Personally, I'd go for the utility class, as I'd rather pay the price for a silly utility than for a bad abstraction. \$\endgroup\$
    – mtj
    Aug 10, 2021 at 17:27
2
\$\begingroup\$

The Game of Life board is a sparse data structure. Replacing the array with a Map<Position,Freshness> would relieve you from allocating space for unused positions. You would iterate over actual existing cells, not empty locations. It would allow for dynamically expanding and "infinite" board size and it would make range checks mostly unnecessary.

Game is not immutable and I don't see a reason why it shouldn't be. It represents game state and one of the objectives was to make the game state immutable. If we define Board to be a dumb data object the Game class would represent a generation within the game and it should be renamed. In my vocabulary, "game" represents the whole program and I find it too generic in this case. A generation does not change once it has been created. A generation can be dead if does not contain any living cells or stable if it is identical to it's previous generation. The class should provide this information so that the user interface code can end the program when there is no point in continuing.

Expandin on mtj's opinion on var. It is a patently bad idea and should not be used. There is an argument for it that it reduces clutter when the type can be inferred from the statement (e.g. var value = new String(...)), but you use it in many places where a var is assigned a value that is returned from a method call and figuring out the type then requires inspecting the method signature. Because it is so easily misused and the misuses make the code so much harder to follow, it should not be used at all. Ever.

Direction seems a bit unnecessary class and it adds clutter as you have to manually add the delta to a Position. Instead just add a Position add(Position) method to the Position class and define the directions as Positions. And that's enough tautology for this paragraph. :)

\$\endgroup\$
2
  • \$\begingroup\$ Thanks for the view. I do think you got a few things wrong, possibly due to my naming. Freshness is used in the game to indicate if it is stale or not. The board is really the state of the board (I named it BoardState initially but thought that was a bit wordy and could call it Generation instead). That makes the argument to rename Game (which encapsulates the rules of a changing game) moot, I think. I don't like to mix uses for position to capture both coordinates and delta coordinates, but yeah, I get your point. \$\endgroup\$ Aug 11, 2021 at 12:55
  • \$\begingroup\$ @MaartenBodewes Correct, it all comes to how the responsibilities are divided. I think my preference would be having the Board or Generation as you have it, then place the evolutionary rules into a separate class (defined by an interface so that it can be changed easily) and the control structure that runs the process into a third class. \$\endgroup\$ Aug 12, 2021 at 4:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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