24

I've been wrestling with a problem in a Java project about circular references. I'm trying to model a real-world situation in which it seems the objects in question are interdependent and need to know about each other.

The project is a generic model of playing a board game. The basic classes are non-specific, but are extended to deal with specifics of chess, backgammon and other games. I coded this up as an applet 11 years ago with half a dozen different games, but the problem is that it's full of circular references. I implemented it back then by stuffing all the intertwined classes in a single source file, but I get the idea that that's bad form in Java. Now I want to implement a similar thing as an Android app, and I want to do things properly.

The classes are:

  • RuleBook: an object that can be interrogated for such things as the initial layout of the Board, other initial game State information like who moves first, the Moves that are available, what happens to the game State after a proposed Move, and an evaluation of a current or proposed board position.

  • Board: a simple representation of a game board, which can be instructed to reflect a Move.

  • MoveList: a list of Moves. This is dual-purpose: a choice of moves available at a given point, or a list of moves that have been made in the game. It could be split into two near-identical classes, but that's not relevant to the question I'm asking and may complicate it further.

  • Move: a single move. It includes everything about the move as a list of atoms: pick up a piece from here, put it down there, remove a captured piece from there.

  • State: the full state information of a game in progress. Not only the Board position, but a MoveList, and other state information such as who is to move now. In chess one would record whether the king and rooks of each player have been moved.

Circular references abound, for example: the RuleBook needs to know about the game State to determine what moves are available at a given time, but the game State needs to query the RuleBook for the initial starting layout and for what side effects accompany a move once it is made (e.g. who moves next).

I tried organising the new set of classes hierarchically, with RuleBook at the top as it needs to know about everything. But this results in having to move lots of methods into the RuleBook class (such as making a move) making it monolithic and not particularly representative of what a RuleBook should be.

So what's the proper way to organise this? Should I turn RuleBook into BigClassThatDoesAlmostEverythingInTheGame to avoid circular references, abandoning the attempt to model the real-world game accurately? Or should I stick with the interdependent classes and coax the compiler into compiling them somehow, retaining my real-world model? Or is there some obvious valid structure I'm missing?

Thanks for any help you can give!

  • 7
    What if the RuleBook took e.g. the State as an argument, and returned the valid MoveList, i.e. "here's where we are now, what can be done next?" – jonrsharpe May 29 '15 at 6:50
  • What @jonrsharpe said. When playing a real board game the rule book also doesn't know about any actual games being played. I would probably even introduce another class to actually calculate moves, but that might depend on how big this RuleBook class already is. – Sebastiaan van den Broek May 29 '15 at 7:42
  • 4
    Avoiding the god object (BigClassThatDoesAlmostEverythingInTheGame) is much more important than avoiding circular references. – user281377 May 29 '15 at 8:08
  • 2
    @user281377 they aren't necessarily mutually exclusive objectives, though! – jonrsharpe May 29 '15 at 9:11
  • 1
    Can you show the modeling attempts? A diagram for example? – User May 29 '15 at 9:33

10 Answers 10

47

I've been wrestling with a problem in a Java project about circular references.

Java's garbage collector doesn't rely on reference counting techniques. Circular references do not cause any kind of problem in Java. Time spent eliminating perfectly natural circular references in Java is time wasted.

I coded this up [...] but the problem is that it's full of circular references. I implemented it back then by stuffing all the intertwined classes in a single source file, [...]

Not necessary. If you just compile all the source files at once (e.g., javac *.java), the compiler will resolve all forward references without problems.

Or should I stick with the interdependent classes and coax the compiler into compiling them somehow, [...]

Yes. Application classes are expected to be interdependent. Compiling all Java source files that belong to the same package at once isn't a clever hack, it's precisely the way Java is supposed to work.

  • 24
    "Circular references do not cause any kind of problem in Java." In terms of compilation, this is true. Circular references are considered bad design, though. – Chop May 29 '15 at 7:40
  • 22
    Circular references are perfectly natural in many situations, that's why Java and other modern languages use a sophisticated garbage collector instead of a simple reference counter. – user281377 May 29 '15 at 8:06
  • 3
    Java being able to resolve circular references is great, and it's definitely true that they're natural in many situations. But OP presented a specific situation, and that ought to be considered. Tangled spaghetti code is probably not the best way to handle this problem. – Matthew Read May 29 '15 at 15:33
  • 3
    Please don't spread unsubstantiated FUD about unrelated programming languages. Python has supported GC of reference cycles since ages (docs, also on SO: here and here). – Christian Aichinger May 30 '15 at 11:45
  • 2
    IMHO this answer is only mediocre, since there is not one word about circular references beeing useful for example of the OP. – Doc Brown May 30 '15 at 18:20
22

Granted, circular dependencies are a questionable practice from a design point of view, but they are not prohibited, and from a purely technical point of view they are not even necessarily problematic, as you seem to regard them to be: they are perfectly legal in most scenarios, they are inevitable in some situations, and on some rare occasions they can even be regarded as a useful thing to have.

Actually, there are very few scenarios where the java compiler will deny a circular dependency. (Note: there may be more, I can only think of the following right now.)

  1. In inheritance: You cannot have a class A extend class B which in turn extends class A, and it is perfectly reasonable that you cannot have this, since the alternative would make absolutely no sense from a logical point of view.

  2. Among method-local classes: classes declared within a method may not circularly reference each other. This is probably nothing but a limitation of the java compiler, possibly because the ability to do such a thing is not useful enough to justify the additional complexity that would have to go into the compiler to support it. (Most java programmers are not even aware of the fact that you can declare a class within a method, let alone declare multiple classes, and then having these classes circularly reference each other.)

So, it is important to realize and get it out of the way that the quest to minimize circular dependencies is a quest for design purity, not a quest for technical correctness.

As far as I know there exists no reductionist approach to eliminating circular dependencies, meaning that there is no recipe consisting of nothing but simple predetermined "no-brainer" steps for taking a system with circular references, applying them one after the other, and ending up with a system free of circular references. You have to put your mind to work, and you have to perform refactoring steps which are dependent on the nature of your design.

In the particular situation that you have at hand, it seems to me that what you need is a new entity, perhaps called "Game" or "GameLogic", which knows all the other entities, (without any of the other entities knowing it,) so that the other entities do not have to know each other.

For example, it seems to me unreasonable that your RuleBook entity needs to know anything whatsoever about the GameState entity, because a rule book is something that we consult in order to play, it is not something that takes active part in playing. So, it is this new "Game" entity which needs to consult both the rule book and the game state in order to determine what moves are available, and this eliminates the circular dependencies.

Now, I think I can guess what your problem is going to be with this approach: coding the "Game" entity in a game-agnostic way will be very hard, so you are most likely going to end up with not just one but two entities that will need to have custom-made implementations for each different type of game: the "RuleBook" and the "Game" entity. Which in turn defeats the purpose of having a "RuleBook" entity in the first place. Well, all I can say about this is that maybe, just maybe, your initial aspiration of writing a system which can play many different types of games may have been noble, but perhaps ill conceived. If I were in your shoes I would have focused on using a common mechanism for displaying the state of all the different games, and a common mechanism for receiving user input for all these games, and then I would have allowed the implementation of the different games to vary wildly, having very little code in common, so as to guarantee maximum flexibility in the implementation of each game.

  • 1
    Thanks Mike. You're right about the drawbacks of the Game entity; with the old applet code I've been able to draw up new games with little more than a new RuleBook subclass and the appropriate graphic design. – Damian Walker May 29 '15 at 10:03
10

Game theory treats games as a list of previous moves (value types including who played them) and a function ValidMoves(previousMoves)

I would try and follow this pattern for the non UI part of the game and treat things like board setup as moves.

the UI can then be standard OO stuff with one way ref to the logic


Update to condense comments

Consider Chess. Games of chess are commonly recorded as lists of moves . http://en.wikipedia.org/wiki/Portable_Game_Notation

the list of moves defines the complete state of the game much better than a picture of the board.

Say for example we start making objects for Board, Piece, Move etc and Methods like Piece.GetValidMoves()

first we see we have to have piece reference the board, but then we consider castling. which you can only do if you have not already moved your king or rook. So we need a MovedAlready flag on the king and rooks. Similarly pawns can move 2 squares on their first move.

Then we see that in castling the valid move of the king depends on the existence and state of the rook, so board needs to have pieces on it and reference those pieces. we are getting into your circular ref problem.

However, if we define Move as an immutable struct and game state as the list of previous moves we find these problems vanish. To see if castling is valid, we can check the move list of the existence of castle and king moves. To see if the pawn can take en-passent we can check to see if the other pawn made a double move on the move before. No references are needed except Rules -> Move

Now chess has a static board, and the peices are always setup the same way. But lets say we have a variant where we allow an alternate setup. perhaps omitting some pieces as a handicap.

If we Add the setup moves as moves, 'from box to square X' and adapet the Rules object to understand that move, then we can still represent the game as a sequence of moves.

Similarly if in your game the board itself is non static, say we can add squares to chess or remove squares from the board so they cant be moved across. These changes can also be represented as Moves without changing the overall structure of your Rules engine or having to reference a BoardSetup object of similar

  • This will tend to complicate the implementation of ValidMoves, which will slow your logic down. – Taemyr May 29 '15 at 10:28
  • not really, I'm assuming the board setup is variable, so you need to define it somehow. If you convert the setup moves to some other struct or object to aid calculation you can cache the result if required. Some games have boards which change with play and some valid moves can depend on previous moves rather than current position (eg. castling in chess) – Ewan May 29 '15 at 10:37
  • 1
    Adding flags and stuff is the complexity you avoid by just having move history. its not expensive to loop over say 100 chess moves to get current board setup and you can cache the result between moves – Ewan May 29 '15 at 11:27
  • 1
    you also avoid changing your object model to reflect rules. ie for chess, if you make validMoves -> Piece + Board, you fail castling, en-passent, first move for pawns and piece promotion and have to add extra info to the objects or reference a third object. You also lose the idea of who's go it is and concepts such as discovered check – Ewan May 29 '15 at 11:58
  • 1
    @Gabe The boardLayout is a function of all priorMoves (i.e. if we did maintain it as state, nothing would be contributed other than each thisMove). Hence Ewan's suggestion is essentially "cut the middle man" - valid moves a direct function of all prior, instead of validMoves( boardLayout( priorMoves ) ). – OJFord May 30 '15 at 13:31
8

The standard way of removing a circular reference between two classes in object oriented programming is to introduce an interface that can then be implemented by one of them. So in your case, you could have RuleBook referring to State which then refers to an InitialPositionProvider (which would be an interface implemented by RuleBook). This also makes testing easier, because you can then create a State that uses a different (presumably simpler) initial position for test purposes.

7

I believe the circular references and the god object in your case could be easily removed by separating the control of the game flow from the state and rule models of the game. By doing that you would probably gain a lot of flexibility and get rid of some needless complexity.

I think you should have a controller ("a game master" if you wish) that controls the game flow and handles actual state changes instead of giving the rule book or the game state this responsibility.

A game state object does not need to change itself or to be aware of the rules. The class just needs to provide a model of easily handled (created, inspected, altered, persisted, logged, copied, cached etc) and efficient game state objects for the rest of the application.

The rule book shouldn't need to know about or fiddle with any ongoing game. It should only need a view to a game state to be able to tell which moves are legal and it only needs to answer with a resulting game state when asked what happens when a move is applied to a game state. It could also provide a beginning game state when asked for an initial layout.

The controller has to be aware of game states and the rule book and perhaps some other objects of the game model, but it shouldn't need to mess with the details.

  • 4
    EXACTLY my thinking. The OP is mixing up too much data and procedure in the same classes. It's better to split these out more. This is a good talk on the subject. Btw, when I read "view to a game state", I think "argument to the function." +100 if I could. – jpmc26 May 29 '15 at 22:59
5

I think the problem here is that you have not given a clear description of what tasks are to be handled by which classes. I will describe what I think is a good description of what each class should do, then I will give an example of generic code that illustrates the ideas. We will see that the code is less coupled, and so it doesn't really have circular references.

Let's start with describing what each class does.

The GameState class should only contain information about the current state of the game. It should not contain any information about what the past states of the game or what future moves are possible. It should only contain information about what pieces are on what squares in chess, or how many and what type of checkers are on what points in backgammon. The GameState will have to contain some extra information, like information about castling in chess or about the doubling cube in backgammon.

The Move class is a little tricky. I would say that I can specify a move to play by specifying the GameState that results from playing the move. So you could imagine that a move can just be implemented as a GameState. However, in go (for example) you could imagine that is a lot easier to specify a move by specifying a single point on the board. We want our Move class to be flexible enough to handle either of these to cases. Therefore the Move class is actually going to be an interface with a method that takes a pre-move GameState and returns a new post-move GameState.

Now the RuleBook class is responsible for knowing everything about the rules. This can be broken down into three things. It needs to know what the initial GameState is, it needs to know what moves are legal, and it needs to be able to tell if one of the players has won.

You could also make a GameHistory class to keep track of all the moves that have been made and all the GameStates that have happened. A new class is necessary because we decided that a single GameState should not be responsible for knowing all the GameStates that came before it.

This concludes the classes/interfaces I will discuss. You also have a Board class. But I think boards in different games are different enough that it is hard to see what could generically be done with boards. Now I will go on to give generic interfaces and implement generic classes.

First is GameState. Since this class is completely dependent on the particular game, there is no generic Gamestate interface or class.

Next is Move. As I said, this can be represented with a interface that has a single method that takes a pre-move state and produces a post-move state. Here is the code for this interface:

package boardgame;

/**
 *
 * @param <T> The type of GameState
 */
public interface Move<T> {

    T makeResultingState(T preMoveState) throws IllegalArgumentException;

}

Notice that there is a type parameter. This is because, for example, a ChessMove will need to know about the particulars of the pre-move ChessGameState. So, for example, the class declaration of ChessMove would be

class ChessMove extends Move<ChessGameState>,

where you would have already defined a ChessGameState class.

Next I will discuss the generic RuleBook class. Here is the code:

package boardgame;

import java.util.List;

/**
 *
 * @param <T> The type of GameState
 */
public interface RuleBook<T> {

    T makeInitialState();

    List<Move<T>> makeMoveList(T gameState);

    StateEvaluation evaluateState(T gameState);

    boolean isMoveLegal(Move<T> move, T currentState);

}

Again there is a type parameter for the GameState class. Since the RuleBook is supposed to know what the initial state is, we have put a method to give the initial state. Since the RuleBook is supposed to know what moves are legal, we have methods to test if a move is legal in a given state and to give a list of legal moves for a given state. Finally, there is a method to evaluate the GameState. Notice the RuleBook should only be responsible for describing if one or the other players has already won, but not who is in a better position in middle of a game. Deciding who is in a better position is a complicated thing that should be moved into its own class. Therefore the StateEvaluation class is actually just a simple enum given as follows:

package boardgame;

/**
 *
 */
public enum StateEvaluation {

    UNFINISHED,
    PLAYER_ONE_WINS,
    PLAYER_TWO_WINS,
    DRAW,
    ILLEGAL_STATE
}

Lastly, let's describe the GameHistory class. This class is responsible for remembering all positions that were reached in the game as well as the moves that were played. The main thing it should be able to do is record a Move as played. You can also add functionality for undoing Moves. I have an implementation below.

package boardgame;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * @param <T> The type of GameState
 */
public class GameHistory<T> {

    private List<T> states;
    private List<Move<T>> moves;

    public GameHistory(T initialState) {
        states = new ArrayList<>();
        states.add(initialState);
        moves = new ArrayList<>();
    }

    void recordMove(Move<T> move) throws IllegalArgumentException {
        moves.add(move);
        states.add(move.makeResultingState(getMostRecentState()));
    }

    void resetToNthState(int n) {
        states = states.subList(0, n + 1);
        moves = moves.subList(0, n);
    }

    void undoLastMove() {
        resetToNthState(getNumberOfMoves() - 1);
    }

    T getMostRecentState() {
        return states.get(getNumberOfMoves());
    }

    T getStateAfterNthMove(int n) {
        return states.get(n + 1);
    }

    Move<T> getNthMove(int n) {
        return moves.get(n);
    }

    int getNumberOfMoves() {
        return moves.size();
    }

}

Finally, we could imagine making a Game class to tie everything together. This Game class is supposed to expose methods that make it possible for people to see what the current GameState is, see who, if anyone has one, see what moves can be played, and play a move. I have an implementation below

package boardgame;

import java.util.List;

/**
 *
 * @author brian
 * @param <T> The type of GameState
 */
public class Game<T> {

    GameHistory<T> gameHistory;
    RuleBook<T> ruleBook;

    public Game(RuleBook<T> ruleBook) {
        this.ruleBook = ruleBook;
        final T initialState = ruleBook.makeInitialState();
        gameHistory = new GameHistory<>(initialState);
    }

    T getCurrentState() {
        return gameHistory.getMostRecentState();
    }

    List<Move<T>> getLegalMoves() {
        return ruleBook.makeMoveList(getCurrentState());
    }

    void doMove(Move<T> move) throws IllegalArgumentException {
        if (!ruleBook.isMoveLegal(move, getCurrentState())) {
            throw new IllegalArgumentException("Move is not legal in this position");
        }
        gameHistory.recordMove(move);
    }

    void undoMove() {
        gameHistory.undoLastMove();
    }

    StateEvaluation evaluateState() {
        return ruleBook.evaluateState(getCurrentState());
    }

}

Notice in this class that the RuleBook is not responsible for knowing what the current GameState is. That is the GameHistory's job. So the Game asks the GameHistory what the current state is and gives this information to the RuleBook when the Game needs to say what the legal moves are or if anyone has won.

Anyway, the point of this answer is that once you have made a reasonable determination of what each class is responsible for, and you make each class focused on a small number of responsibilities, and you assign each responsibility to a unique class, then the classes tend to be decoupled, and everything gets easy to code. Hopefully that is apparent from the code examples I gave.

3

In my experience, circular references generally indicate that your design isn't well-thought-out.

In your design, I don't understand why RuleBook needs to "know" about the State. It might receive a State as a parameter to some method, sure, but why should it need to know (i.e. hold as an instance variable) a reference to a State? That doesn't make sense to me. A RuleBook doesn't need to "know" about the state of any particular game in order to do its job; the rules of the game don't change depending on the current state of the game. So either you've designed it incorrectly, or you've designed it correctly but are explaining it incorrectly.

  • +1. You buy a physical board game, you get a rule book that is able to describe the rules without state. – souser12345 May 30 '15 at 17:26
1

The circular dependency isn't necessarily a technical problem, but it should be considered a code smell, that usually is a violation of the Single Responsibility Principle.

Your circular dependency comes from the fact that you're trying to do too much from your State object.

Any stateful object should only provide methods that directly relate to managing that local state. If it requires anything more than the most basic logic, then it should probably be broken out into a larger pattern. Some people have different opinions about this, but as a general rule of thumb, if you're doing anything more than getters and setters on data, you're doing too much.

In this case, you'd be better off having a StateFactory, which could know about a Rulebook. You'd probably have another controller class which uses your StateFactory to create a new game. State definitely shouldn't know about Rulebook. Rulebook might know about a State depending on the implementation of your rules.

0

Is there any need for a rulebook object to be bound to a particular game state, or would it make more sense to have a rulebook object with a method that, given a game state, will report what moves are available from that state (and, having reported that, remember nothing about the state in question)? Unless there is something to be gained by having the object which is asked about available moves retain a memory of the game state, there's no need for it to persist a reference.

It's possible in some cases there would be advantages to having the rules-evaluating object maintain state. If you think such a situation may arise, I would suggest adding a "referee" class, and having the rulebook provide a "createReferee" method. Unlike the rulebook, which cares nothing whether it's asked about one game, or fifty, a referee object would expect to officiate one game. It wouldn't be expected to encapsulate all of the state related to the game it's officiating, but could cache whatever information about the game it deemed useful. If a game supports "undo" functionality, it may be helpful to have the referee include a means of producing a "snapshot" object which could be stored along with earlier game states; that object should, given a copy of the game state when it was created, be able to in turn produce a new referee which whose state should match the state the original referee had when the snapshot was created.

If some coupling might be necessary between the rules-processing and game-state-processing aspects of the code, using a referee object will make it possible to keep such coupling out of the main rulesbook and game-state classes. It may also make it possible to have new rules consider aspects of game state that the game-state class wouldn't consider relevant (e.g. if a rule was added which said "Object X can't do Y if it's ever been to location Z", the referee could be changed to keep track of which objects have been to location Z without having to change the game-state class).

-2

The proper way of dealing with this is to use interfaces. Instead of having two classes know about eachother, have each class implement an interface and reference that in the other class. Let's say you have class A and class B that need to reference eachother. Have class A implement interface A and class B implement interface B then you can reference interface B from class A and interface A from class B. Class A can than be in it's own project, as can class B. The interfaces are in a seperate project which both other projects reference.

  • 2
    this seems to merely repeat points made and explained in a prior answer posted few hours before this one – gnat May 29 '15 at 17:24

protected by gnat Aug 15 '15 at 19:28

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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