Description
This is my code for the Weekend Challenge Reboot - Tic Tac Toe Ultimate.
The game can be played here: http://www.zomis.net/ttt (along with some other variations that are also use the same code base, but with other 'controllers').
This question contains the game model and a 'controller' for the TicTacToe Ultimate game.
The classic TTT is 3*3. TTT Ultimate is a 3*3 grid of classic TTTs, so 3*3 * 3*3. As usual I wanted this code to be flexible, so technically it should be possible to extend it to a TTTUltimatePlus which would be a 3*3 grid of TTTUltimate games, or 3*3 * 3*3 * 3*3. I have not done a controller for TTTUltimatePlus yet, but the TTBase system would support it. When I started this project, I did not expect myself to make it work with Reversi (a.k.a. Othello), or Quantum Tic-Tac-Toe but well... when I realized how I could structure this I thought "Why not?".
My first code, having a TTUltimateGame, TTBoard and a TTField class had a lot of code duplication which I wanted to avoid. This made me want to make this code. The TTBase class is the most important one, to support any number of recursiveness (by making a TTTUltimatePlus for example) I made it as a recursive class. Each clickable field is a TTBase, each area containing the fields is a TTBase, and the outermost game itself is a TTBase.
Class Summary (695 lines in 12 files, making a total of 18218 bytes)
- HasSub.java: Interface indicating that a class contains smaller parts, 'subs' (a small field is a sub to a 3x3 area for example).
- TicFactory.java: Interface for creating TTBase objects.
- TicUtils.java: Utility methods, including code to create the Win Conditions for a TTBase.
- TTBase.java: Class that can contain more TTBases in a rectangular grid. Can be won and played by players.
- TTController.java: Abstract class for determining which TTBases that can be played and for playing at them.
- TTFactories.java: Code to instanciate variations of TTBases.
- TTMNKParameters.java: Parameters for creating a TTBase. Determines the size of the board and the number of consecutive fields that must be won by the same player.
- TTMoveListener.java: Interface for when a move has been made
- TTPlayer.java: An enum for players; X or O, and none, or both.
- TTUltimateController.java: Provides a TTController for TTT Ultimate.
- TTWinCondition.java: A rule for determining if a board is won by checking a number of fields. A classic TTT board for example has 8 win conditions: 3 rows, 3 columns and 2 diagonals.
- Winnable.java: Interface for something that can be won by a TTPlayer.
Code
This code can also be downloaded from GitHub
HasSub.java: (15 lines, 369 bytes)
/**
* Interface for classes that can contain other objects, 'subs', in a rectangular way
*
* @param <T> Type of sub
*/
public interface HasSub<T> extends Winnable {
T getSub(int x, int y);
Iterable<TTWinCondition> getWinConds();
int getSizeX();
int getSizeY();
int getConsecutiveRequired();
boolean hasSubs();
}
TicFactory.java: (5 lines, 117 bytes)
public interface TicFactory {
TTBase construct(TTBase parent, int x, int y);
}
TicUtils.java: (140 lines, 4211 bytes)
public class TicUtils {
/**
* Get which board a tile will send the opponent to (in a TTTUltimate context)
*
* @param tile The tile to be played
* @return The board which the tile directs to
*/
public static TTBase getDestinationBoard(TTBase tile) {
TTBase parent = tile.getParent();
if (parent == null)
return null;
TTBase grandpa = parent.getParent();
if (grandpa == null)
return null;
return grandpa.getSub(tile.getX(), tile.getY());
}
/**
* Find the win conditions which contains a specific field
*
* @param field The field to look for
* @param board Where to look for win conditions
* @return A collection which only contains win conditions which contains the field
*/
public static <E extends Winnable> Collection<TTWinCondition> getWinCondsWith(E field, HasSub<E> board) {
Collection<TTWinCondition> coll = new ArrayList<>();
for (TTWinCondition cond : board.getWinConds()) {
if (cond.hasWinnable(field))
coll.add(cond);
}
return coll;
}
/**
* Get all smaller tiles/boards in a board
*
* @param board Board to scan
* @return Collection of all smaller tiles/boards contained in board.
*/
public static <T> Collection<T> getAllSubs(HasSub<T> board) {
List<T> list = new ArrayList<>();
int sizeX = board.getSizeX();
int sizeY = board.getSizeY();
for (int x = 0; x < sizeX; x++) {
for (int y = 0; y < sizeY; y++) {
list.add(board.getSub(x, y));
}
}
return list;
}
/**
* Recursively scan for smaller subs
*
* @param game The outermost object to scan
* @return A collection containing all fields within the specified 'game' which do not have any subs
*/
public static Collection<TTBase> getAllSmallestFields(TTBase game) {
Collection<TTBase> all = new ArrayList<>();
for (TTBase sub : TicUtils.getAllSubs(game)) {
if (sub.hasSubs())
all.addAll(getAllSmallestFields(sub));
else all.add(sub);
}
return all;
}
/**
* Create win conditions
*
* @param board The board to create win conditions for
* @return A list of all WinConditions that was created
*/
public static List<TTWinCondition> setupWins(final HasSub<? extends Winnable> board) {
if (!board.hasSubs()) {
ArrayList<TTWinCondition> list = new ArrayList<>();
list.add(new TTWinCondition(board));
return list;
}
int consecutive = board.getConsecutiveRequired();
List<TTWinCondition> conds = new ArrayList<>();
// Scan columns for a winner
for (int xx = 0; xx < board.getSizeX(); xx++) {
newWin(conds, consecutive, loopAdd(board, xx, 0, 0, 1));
}
// Scan rows for a winner
for (int yy = 0; yy < board.getSizeY(); yy++) {
newWin(conds, consecutive, loopAdd(board, 0, yy, 1, 0));
}
// Scan diagonals for a winner: Bottom-right
for (int yy = 0; yy < board.getSizeY(); yy++) {
newWin(conds, consecutive, loopAdd(board, 0, yy, 1, 1));
}
for (int xx = 1; xx < board.getSizeX(); xx++) {
newWin(conds, consecutive, loopAdd(board, xx, 0, 1, 1));
}
// Scan diagonals for a winner: Bottom-left
for (int xx = 0; xx < board.getSizeY(); xx++) {
newWin(conds, consecutive, loopAdd(board, xx, 0, -1, 1));
}
for (int yy = 1; yy < board.getSizeY(); yy++) {
newWin(conds, consecutive, loopAdd(board, board.getSizeX() - 1, yy, -1, 1));
}
return conds;
}
private static void newWin(List<TTWinCondition> conds, int consecutive, List<Winnable> winnables) {
if (winnables.size() >= consecutive) // shorter win conditions doesn't need to be added as they will never be able to win
conds.add(new TTWinCondition(winnables, consecutive));
}
private static List<Winnable> loopAdd(HasSub<? extends Winnable> board,
int xx, int yy, int dx, int dy) {
List<Winnable> winnables = new ArrayList<>();
Winnable tile;
do {
tile = board.getSub(xx, yy);
xx += dx;
yy += dy;
if (tile != null)
winnables.add(tile);
}
while (tile != null);
return winnables;
}
}
TTBase.java: (149 lines, 3623 bytes)
public class TTBase implements Winnable, HasSub<TTBase> {
// Container
private final TTBase[][] subs;
private final TTMNKParameters mnkParams;
private final List<TTWinCondition> winConditions;
// Winnable
private final TTBase parent;
private final int x;
private final int y;
private TTPlayer playedBy = TTPlayer.NONE;
public TTBase(TTBase parent, TTMNKParameters parameters, TicFactory factory) {
this(parent, 0, 0, parameters, factory);
}
public TTBase(TTBase parent, int x, int y, TTMNKParameters parameters, TicFactory factory) {
this.parent = parent;
this.mnkParams = parameters;
this.x = x;
this.y = y;
this.subs = new TTBase[parameters.getWidth()][parameters.getHeight()];
for (int xx = 0; xx < parameters.getWidth(); xx++) {
for (int yy = 0; yy < parameters.getHeight(); yy++) {
this.subs[xx][yy] = factory.construct(this, xx, yy);
}
}
this.winConditions = Collections.unmodifiableList(TicUtils.setupWins(this));
}
public void determineWinner() {
TTPlayer winner = TTPlayer.NONE;
for (TTWinCondition cond : this.winConditions) {
winner = winner.or(cond.determineWinnerNew());
}
this.playedBy = winner;
}
@Override
public TTBase getSub(int x, int y) {
if (!hasSubs() && x == 0 && y == 0)
return this;
if (x < 0 || y < 0)
return null;
if (x >= getSizeX() || y >= getSizeY())
return null;
return subs[x][y];
}
@Override
public List<TTWinCondition> getWinConds() {
return winConditions;
}
@Override
public TTPlayer getWonBy() {
return this.playedBy;
}
@Override
public int getSizeX() {
return this.mnkParams.getWidth();
}
@Override
public int getSizeY() {
return this.mnkParams.getHeight();
}
@Override
public int getConsecutiveRequired() {
return this.mnkParams.getConsecutiveRequired();
}
public TTMNKParameters getMNKParameters() {
return this.mnkParams;
}
public TTBase getParent() {
return parent;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
public boolean isWon() {
return playedBy != TTPlayer.NONE;
}
public void setPlayedBy(TTPlayer playedBy) {
if (playedBy == null && this.hasSubs() && parent != null)
new Exception().printStackTrace();
this.playedBy = playedBy;
}
public boolean hasSubs() {
return getSizeX() != 0 && getSizeY() != 0;
}
@Override
public String toString() {
return "{Pos " + x + ", " + y + "; Size " + getSizeX() + ", " + getSizeY() + "; Played by " + getWonBy() + ". Parent is " + parent + "}";
}
public void reset() {
this.setPlayedBy(TTPlayer.NONE);
for (int xx = 0; xx < getSizeX(); xx++) {
for (int yy = 0; yy < getSizeY(); yy++) {
this.getSub(xx, yy).reset();
}
}
}
public int getGlobalX() {
if (parent == null)
return 0;
if (parent.getParent() == null)
return x;
return parent.getX() * parent.getParent().getSizeX() + this.x;
}
public int getGlobalY() {
if (parent == null)
return 0;
if (parent.getParent() == null)
return y;
return parent.getY() * parent.getParent().getSizeY() + this.y;
}
public TTBase getSmallestTile(int x, int y) {
int subX = x / getSizeX();
int subY = y / getSizeY();
TTBase board = getSub(subX, subY);
if (board == null)
throw new NullPointerException("No such smallest tile found: " + x + ", " + y);
return board.getSub(x - subX*getSizeX(), y - subY*getSizeY());
}
}
TTController.java: (110 lines, 2867 bytes)
public abstract class TTController {
protected final TTBase game;
protected TTPlayer currentPlayer = TTPlayer.X;
private TTMoveListener moveListener;
private StringBuilder history;
public TTController(TTBase board) {
this.game = board;
this.history = new StringBuilder();
}
public abstract boolean isAllowedPlay(TTBase tile);
public final boolean play(TTBase tile) {
if (tile == null)
throw new IllegalArgumentException("Tile to play at cannot be null.");
if (!isAllowedPlay(tile)) {
System.out.println("Warning: Move was not made. Unable to play at " + tile);
return false;
}
TTBase playedTile = tile;
if (!this.performPlay(tile))
return false;
this.addToHistory(tile);
if (this.moveListener != null)
this.moveListener.onMove(playedTile);
return true;
}
private void addToHistory(TTBase tile) {
if (history.length() > 0)
history.append(",");
history.append(Integer.toString(tile.getGlobalX(), Character.MAX_RADIX));
history.append(Integer.toString(tile.getGlobalY(), Character.MAX_RADIX));
}
protected abstract boolean performPlay(TTBase tile);
public boolean play(int x, int y) {
return this.play(game.getSmallestTile(x, y));
}
public TTPlayer getCurrentPlayer() {
return currentPlayer;
}
protected void nextPlayer() {
currentPlayer = currentPlayer.next();
}
public TTBase getGame() {
return game;
}
public boolean isGameOver() {
return game.isWon();
}
public TTPlayer getWonBy() {
return game.getWonBy();
}
public void setOnMoveListener(TTMoveListener moveListener) {
this.moveListener = moveListener;
}
public void makeMoves(String history) throws IllegalStateException, IllegalArgumentException {
for (String move : history.split(",")) {
if (move.isEmpty())
continue;
if (move.length() != 2)
throw new IllegalArgumentException("Unexcepted move length. " + move);
int x = Integer.parseInt(String.valueOf(move.charAt(0)), Character.MAX_RADIX);
int y = Integer.parseInt(String.valueOf(move.charAt(1)), Character.MAX_RADIX);
TTBase tile = game.getSmallestTile(x, y);
if (!this.play(tile))
throw new IllegalStateException("Unable to make a move at " + x + ", " + y + ": " + tile);
}
}
public String saveHistory() {
return this.history.toString();
}
public void reset() {
this.currentPlayer = TTPlayer.X;
this.history = new StringBuilder();
this.game.reset();
this.onReset();
}
protected abstract void onReset();
public String getViewFor(TTBase tile) {
return tile.isWon() ? tile.getWonBy().toString() : "";
}
}
TTFactories.java: (52 lines, 1616 bytes)
public class TTFactories {
private static final TTMNKParameters mnkEmpty = new TTMNKParameters(0, 0, 0);
private static final TicFactory lastFactory = new TicFactory() {
@Override
public TTBase construct(TTBase parent, int x, int y) {
return new TTBase(parent, x, y, mnkEmpty, null);
}
};
private static final TicFactory areaFactory = new TicFactory() {
@Override
public TTBase construct(TTBase parent, int x, int y) {
return new TTBase(parent, x, y, parent.getMNKParameters(), lastFactory);
}
};
public static class Factory implements TicFactory {
private final TTMNKParameters mnk;
private final TicFactory next;
public Factory(TTMNKParameters mnk, TicFactory nextFactory) {
this.mnk = mnk;
this.next = nextFactory;
}
@Override
public TTBase construct(TTBase parent, int x, int y) {
return new TTBase(parent, x, y, mnk, next);
}
}
public TTBase classicMNK(int width, int height, int consecutive) {
return new TTBase(null, new TTMNKParameters(width, height, consecutive), lastFactory);
}
public TTBase classicMNK(int mnk) {
return classicMNK(mnk, mnk, mnk);
}
public TTBase ultimate(int mnk) {
return ultimate(mnk, mnk, mnk);
}
public TTBase ultimate(int width, int height, int consecutive) {
return new TTBase(null, new TTMNKParameters(width, height, consecutive), areaFactory);
}
public TTBase ultimate() {
return ultimate(3);
}
public TTBase othello(int size) {
return new TTBase(null, new TTMNKParameters(size, size, size + 1), lastFactory);
}
}
TTMNKParameters.java: (27 lines, 533 bytes)
public class TTMNKParameters {
private final int width;
private final int height;
private final int consecutiveRequired;
public TTMNKParameters(int width, int height, int consecutiveRequired) {
this.width = width;
this.height = height;
this.consecutiveRequired = consecutiveRequired;
}
public int getConsecutiveRequired() {
return consecutiveRequired;
}
public int getHeight() {
return height;
}
public int getWidth() {
return width;
}
}
TTMoveListener.java: (5 lines, 104 bytes)
public interface TTMoveListener {
void onMove(TTBase playedAt);
}
TTPlayer.java: (54 lines, 1273 bytes)
public enum TTPlayer {
NONE, X, O, XO;
public TTPlayer next() {
if (!isExactlyOnePlayer())
throw new UnsupportedOperationException("Only possible to call .next() on a real player but it was called on " + this);
return this == X ? O : X;
}
/**
* Determine if this player is (also) another player.<br>
* This is the same as <code>this.and(other) == other</code>
*
* @param other
* @return
*/
public boolean is(TTPlayer other) {
return this.and(other) == other;
}
public TTPlayer and(TTPlayer other) {
if (this == NONE || other == NONE || other == null)
return NONE;
if (isExactlyOnePlayer() && other.isExactlyOnePlayer())
return this == other ? this : NONE;
if (this == XO)
return other;
return other.and(this);
}
public boolean isExactlyOnePlayer() {
return this == X || this == O;
}
public static boolean isExactlyOnePlayer(TTPlayer winner) {
return winner != null && winner.isExactlyOnePlayer();
}
public TTPlayer or(TTPlayer other) {
if (this == NONE || other == null)
return other;
if (other == NONE)
return this;
if (this == XO)
return this;
if (this != other)
return XO;
return this;
}
}
TTUltimateController.java: (53 lines, 1386 bytes)
public class TTUltimateController extends TTController {
// TODO: Try making it even more Ultimate by adding one more dimension, and use Map<TTBase, TTBase> activeBoards. Just for fun.
private TTBase activeBoard = null;
public TTUltimateController(TTBase board) {
super(board);
}
@Override
public boolean isAllowedPlay(TTBase tile) {
TTBase area = tile.getParent();
if (area == null)
return false;
TTBase game = tile.getParent().getParent();
if (!tile.getWonBy().equals(TTPlayer.NONE))
return false;
if (area.getWonBy().isExactlyOnePlayer())
return false;
if (game.isWon())
return false;
return activeBoard == null || activeBoard == area || activeBoard.getWonBy() != TTPlayer.NONE;
}
@Override
public boolean performPlay(TTBase tile) {
tile.setPlayedBy(currentPlayer);
activeBoard = TicUtils.getDestinationBoard(tile);
nextPlayer();
// Check for win condition on tile and if there is a win, cascade to it's parents
do {
tile.determineWinner();
tile = tile.isWon() ? tile.getParent() : null;
}
while (tile != null);
return true;
}
@Override
protected void onReset() {
this.activeBoard = null;
}
}
TTWinCondition.java: (78 lines, 2026 bytes)
public class TTWinCondition implements Iterable<Winnable> {
private final List<Winnable> winnables;
private final int consecutive;
public TTWinCondition(Winnable... winnables) {
this(Arrays.asList(winnables));
}
public TTWinCondition(List<? extends Winnable> winnables) {
this(winnables, winnables.size());
}
public TTWinCondition(List<? extends Winnable> winnables, int consecutive) {
if (winnables.isEmpty())
throw new IllegalArgumentException("Can't have an empty win condition!");
this.winnables = Collections.unmodifiableList(new ArrayList<Winnable>(winnables));
this.consecutive = consecutive;
}
public int neededForWin(TTPlayer player) {
return winnables.size() - hasCurrently(player);
}
public boolean isWinnable(TTPlayer byPlayer) {
return hasCurrently(byPlayer.next()) == 0;
}
public int hasCurrently(TTPlayer player) {
int i = 0;
for (Winnable winnable : winnables) {
if (winnable.getWonBy().and(player) == player)
i++;
}
return i;
}
public TTPlayer determineWinnerNew() {
TTPlayer winner = TTPlayer.NONE;
int[] consecutivePlayers = new int[TTPlayer.values().length];
for (Winnable winnable : winnables) {
TTPlayer current = winnable.getWonBy();
for (TTPlayer pl : TTPlayer.values()) {
int i = pl.ordinal();
if (pl.and(current) == pl) {
consecutivePlayers[i]++;
}
else consecutivePlayers[i] = 0;
if (consecutivePlayers[i] >= this.consecutive) {
winner = winner.or(pl);
}
}
}
return winner;
}
public boolean hasWinnable(Winnable field) {
return winnables.contains(field);
}
public int size() {
return winnables.size();
}
@Override
public Iterator<Winnable> iterator() {
return new ArrayList<Winnable>(this.winnables).iterator();
}
}
Winnable.java: (7 lines, 93 bytes)
public interface Winnable {
TTPlayer getWonBy();
}
Usage / Test
You can play the game on http://www.zomis.net/ttt . The GUI checks with the controller if a field can be played or not and uses the methods provided by the controller to make a move on a field. The GUI is written using GWT (Google Web Toolkit) which compiles my Java code to JavaScript and obfuscates it for me.
Questions
Things I am quite proud of includes the TTWinCondition class, especially the way TTWinConditions is created.
I am also quite proud of the TTPlayer enum and how it includes both NONE and XO (both), and it's and and or methods.
Things I am not so proud of includes the TTBase class. It is the best thing I could come up with though (and it is probably the most unique way of all the challenge implementations). I really couldn't come up with a more flexible way that would support any number of recursiveness, and at the same time removing code duplication.
This project uses Java 7. It also needs to support GWT so I cannot use String.format.
I'd mostly like comments about how I have designed these classes and interfaces. And if anyone knows a better way to do things than what I have done here, I'd love to hear them.
You may not agree with my naming of classes to start with TT, but I do this to make it easier for me to find my TTT-specific classes when using Eclipse's Ctrl + Shift + T keyboard shortcut.
